Soorten grafieken in gegevensstructuur met voorbeelden
Sara Chen
⚡ Slimme samenvatting
Grafen in datastructuren zijn niet-lineaire verzamelingen van knooppunten en verbindingen die, op basis van hun structuur, worden ingedeeld in families zoals gerichte, ongerichte, gewogen, cyclische, acyclische, complete, verbonden, bipartiete, Euler- en Hamilton-grafen.
Een graaf is een niet-lineaire datastructuur die bestaat uit knooppunten en verbindingen. De knooppunten bevatten de informatie of gegevens, en de verbindingen fungeren als een link tussen twee knooppunten.
Grafieken kunnen van verschillende typen zijn, afhankelijk van de positie van de knooppunten en verbindingen. Hieronder volgen enkele belangrijke typen grafieken:
Gerichte grafiek
De randen van een gerichte graaf bevatten pijlen die de richting aangeven. De pijl bepaalt waar de rand naartoe wijst of eindigt. Hier is een voorbeeld van een gerichte graaf.
Gerichte grafiek
- We kunnen van knooppunt A naar D gaan.
- We kunnen echter niet van knooppunt D naar knooppunt A gaan, omdat de verbinding van A naar D wijst.
- Omdat de grafiek geen gewichten heeft, kost het reizen van hoekpunt A naar D hetzelfde als reizen van D naar F.
Ongerichte grafiek
Een ongerichte graaf bevat randen zonder pointers. Dit betekent dat we in beide richtingen tussen twee knooppunten kunnen reizen. Hier is een eenvoudig voorbeeld van een ongerichte graaf.
Ongerichte grafiek
In de bovenstaande grafiek,
- We kunnen van A naar B gaan.
- We kunnen ook van B naar A gaan.
- Randen bevatten geen richtingen.
Het is een voorbeeld van een ongerichte graaf met een eindig aantal knooppunten en randen zonder gewichten.
Gewogen grafiek
Een graaf die gewichten of kosten aan de randen heeft, wordt een gewogen graaf genoemd. De numerieke waarde vertegenwoordigt over het algemeen de verplaatsingskosten van het ene knooppunt naar het andere. Zowel gerichte als ongerichte grafen kunnen gewichten aan hun randen hebben. Hier is een voorbeeld van een gewogen graaf (gericht).
Gerichte grafiek met gewicht
- Van A naar B is er een rand, en het gewicht is 5, wat betekent dat de verplaatsing van A naar B ons 5 kost.
- A wijst naar B, maar in deze grafiek heeft B geen directe verbinding met A. We kunnen dus niet van B naar A reizen.
- Als we echter van A naar F willen, zijn er meerdere paden mogelijk. De paden zijn ADF en ABF. ADF kost (10+11) of 21.
- Hier kost het pad ABF (5+15) of 20. We tellen hier het gewicht van elke rand in het pad bij elkaar op.
Hier is een voorbeeld van een ongerichte graaf met gewichten:
Ongerichte grafiek met gewicht
Hier heeft de rand gewicht maar geen richting. Het betekent dus dat reizen van hoekpunt A naar D 10 euro kost en omgekeerd.
Bidirectionele grafiek
Bidirectionele en ongerichte grafen hebben een gemeenschappelijke eigenschap. Namelijk:
- Een ongerichte graaf heeft doorgaans één verbinding tussen twee knooppunten.
Bijvoorbeeld:
- Hier kost het verplaatsen van A naar D of D naar A 10.
- In een bidirectionele grafiek kunnen we twee randen tussen twee hoekpunten hebben.
Hier is een voorbeeld:
Bidirectionele grafiek
Reizen van A naar D kost ons 17, maar reizen van D naar A kost ons 12. We kunnen dus geen twee verschillende gewichten toekennen als het een ongerichte graaf is.
Oneindige grafiek
De graaf zal een oneindig aantal randen en knooppunten bevatten. Als een graaf oneindig is en tevens een verbonden graaf, dan zal deze ook een oneindig aantal randen bevatten. De uitgebreide randen betekenen hier dat er mogelijk meer randen via verbindingen met deze knooppunten verbonden zijn. Hier is een voorbeeld van een oneindige graaf:
Oneindige grafiek
Nulgrafiek
Een lege graaf bevat alleen knooppunten of vertices, maar geen randen. Gegeven een graaf G = (V, E), waarbij V de vertices en E de randen zijn, is deze leeg als het aantal randen E nul is. Hier is een voorbeeld van een lege graaf:
Nulgrafiek
Triviale grafiek
Een graafdatastructuur wordt als triviaal beschouwd als deze slechts één knooppunt of vertex bevat en geen verbindingen. Hier is een voorbeeld van een triviale graaf:
Multigrafiek
Een graaf wordt een multigraaf genoemd wanneer er meerdere verbindingen (edges) tussen twee knooppunten bestaan, of wanneer een knooppunt een lus bevat. De term "lus" in de grafdatastructuur verwijst naar een verbinding die naar hetzelfde knooppunt wijst. Een multigraaf kan gericht of ongericht zijn. Hier is een voorbeeld van een multigraaf:
Er zijn twee verbindingen van B naar A. Bovendien heeft knooppunt E een zelflus. De bovenstaande graaf is een gerichte graaf zonder gewichten op de verbindingen.
Volledige grafiek
Een graaf is compleet als elk knooppunt gerichte of ongerichte verbindingen heeft met alle andere knooppunten. Stel dat er in totaal V knooppunten zijn en elk knooppunt precies V-1 verbindingen heeft. Dan noemen we deze graaf een complete graaf. In dit type graaf is elk knooppunt via verbindingen verbonden met alle andere knooppunten. Hier is een voorbeeld van een complete graaf met vijf knooppunten:
Op de afbeelding is te zien dat er in totaal vijf knooppunten zijn en dat elk knooppunt precies vier verbindingen heeft.
Verbonden grafiek
Een graaf wordt een verbonden graaf genoemd als we vanuit een knooppunt alle volgende knooppunten kunnen bereiken. Hiervoor moet er minstens één verbinding (edge) zijn tussen elk paar knooppunten. Hier is een voorbeeld van een verbonden graaf:
Hieronder volgt een toelichting op de bovenstaande verbonden grafiek:
- Ervan uitgaande dat er geen verbinding is tussen C en F, kunnen we niet van A naar G reizen. De verbinding tussen C en F stelt ons echter in staat om vanuit een gegeven knooppunt naar elk willekeurig ander knooppunt te reizen.
- Een volledige grafiek is een verbonden grafiek omdat we van een knooppunt naar elk ander knooppunt in de gegeven grafiek kunnen gaan.
Cyclische grafiek
Een grafiek wordt cyclisch genoemd als er een of meer cycli in voorkomen. Hier is een voorbeeld van een cyclische grafiek:
Hier vormen de hoekpunten A, B en C een cyclus. Een graaf kan meerdere cycli bevatten.
Gerichte Acyclische Grafiek (DAG)
Een graaf wordt een gerichte acyclische graaf (DAG) genoemd als er geen cycli in de graaf voorkomen. DAG's zijn belangrijk bij het maken van... Topologische sortering of het bepalen van de uitvoeringsvolgorde. Een DAG is ook belangrijk voor het creëren van planningssystemen of het scannen van afhankelijkheden tussen resources, enzovoort. De bovenstaande grafiek bevat echter geen cycli. Hier is een eenvoudig voorbeeld van een gerichte acyclische graaf (DAG):
Cyclusgrafiek
Een cyclusgrafiek is niet hetzelfde als een cyclische grafiek. In een cyclusgrafiek heeft elk knooppunt precies twee verbonden randen, wat betekent dat elk knooppunt precies twee graden heeft. Hier is een voorbeeld van een cyclusgrafiek:
Bipartiete grafiek
Dit soort Grafieken Bipartiete grafen zijn speciale soorten grafen waarbij de knooppunten aan twee verzamelingen zijn toegewezen. Een bipartiete graaf moet aan de volgende regel voldoen:
- De twee verzamelingen hoekpunten moeten verschillend zijn, wat betekent dat alle hoekpunten in twee groepen of verzamelingen moeten worden verdeeld.
- Hoekpunten uit dezelfde verzameling mogen geen randen vormen.
Euler-grafiek
Een graafdatastructuur wordt een Eulergraaf genoemd als alle knooppunten een even graad hebben. De term 'graad van knooppunten' verwijst naar het aantal verbindingen dat naar een bepaald knooppunt wijst of daarvandaan vertrekt. Hier is een voorbeeld van een Eulergraaf:
Alle hoekpunten hebben een even aantal graden. Hoekpunten A, D, E en H hebben een graad van twee. Knooppunt C heeft een graad van vier, wat een even aantal is.
Hamilton-grafiek
Een Hamilton-graaf is een verbonden graaf, waarbij je alle knooppunten vanuit een gegeven knooppunt kunt bezoeken zonder hetzelfde knooppunt opnieuw te bezoeken of dezelfde kant te gebruiken. Dit type verbonden graaf staat bekend als de "Hamilton-graaf". Het pad dat je volgt om te controleren of een gegeven graaf een Hamilton-graaf is, wordt het Hamiltonpad genoemd. Hier is een eenvoudig voorbeeld van een Hamilton-graaf:
In deze afbeelding kunnen we alle hoekpunten van elk knooppunt in de bovenstaande grafiek bezoeken. Een van de paden kan zijn ADCHBEHet is ook mogelijk om een Hamiltoncyclus te vinden. Een Hamiltoncyclus begint en eindigt bij hetzelfde hoekpunt. De Hamiltoncyclus zal dus zijn... ADCHBEA.
