Typy grafů v datové struktuře s příklady
Sarah Chen
⚡ Chytré shrnutí
Grafy v datových strukturách jsou nelineární soubory vrcholů a hran klasifikované do rodin, jako jsou orientované, neorientované, vážené, cyklické, acyklické, úplné, propojené, bipartitní, Eulerovy a Hamiltonovy grafy založené na struktuře.
Graf je nelineární datová struktura, která se skládá z vrcholů a hran. Vrcholy obsahují informace nebo data a hrany fungují jako spojnice mezi dvojicí vrcholů.
Grafy mohou být různých typů v závislosti na poloze uzlů a hran. Zde jsou některé důležité typy grafů:
Režírovaný graf
Hrany orientovaného grafu obsahují šipky, které označují směr. Šipka určuje, kam hrana směřuje nebo kde končí. Zde je příklad orientovaného grafu.
Režírovaný graf
- Můžeme přejít z uzlu A do D.
- Nemůžeme však přejít z uzlu D do uzlu A, protože hrana směřuje z uzlu A do uzlu D.
- Protože graf nemá váhy, cestování z vrcholu A do D bude stát stejně jako cestování z D do F.
Neorientovaný graf
Neorientovaný graf obsahuje hrany bez ukazatelů. To znamená, že se mezi dvěma vrcholy můžeme pohybovat naopak. Zde je jednoduchý příklad neorientovaného grafu.
Neorientovaný graf
Ve výše uvedeném grafu
- Můžeme se přesunout z bodu A do bodu B.
- Můžeme se také přesunout z B do A.
- Hrany neobsahují žádné směry.
Je to příklad neorientovaného grafu s konečným počtem vrcholů a hran bez vah.
Vážený graf
Graf, který obsahuje váhy nebo náklady na hranách, se nazývá vážený graf. Číselná hodnota obecně představuje náklady na přesun z jednoho vrcholu do druhého. Váhy na hranách mohou mít jak orientované, tak neorientované grafy. Zde je příklad váženého grafu (orientovaného).
Orientovaný graf s váhou
- Z bodu A do bodu B je hrana a váha je 5, což znamená, že přesun z bodu A do bodu B nás bude stát 5.
- Bod A ukazuje na bod B, ale v tomto grafu nemá bod B přímou výhodu nad bodem A. Nemůžeme se tedy dostat z bodu B do bodu A.
- Pokud se ale chceme přesunout z bodu A do bodu F, existuje více cest. Těmito cestami jsou ADF a ABF. ADF bude stát (10+11) neboli 21.
- Zde bude cesta ABF stát (5+15) neboli 20. Zde přidáváme váhu každé hrany v cestě.
Zde je příklad neorientovaného grafu s váhami:
Neorientovaný graf s váhou
Zde má hrana váhu, ale žádný směr. To znamená, že cestování z vrcholu A do D bude stát 10 a naopak.
Obousměrný graf
Obousměrné a neorientované grafy mají společnou vlastnost. A to:
- Neorientovaný graf může mít obecně jednu hranu mezi dvěma vrcholy.
Například:
- Zde bude přesun z A do D nebo D do A stát 10.
- V obousměrném grafu můžeme mít dvě hrany mezi dvěma vrcholy.
Zde je příklad:
Obousměrný graf
Cesta z bodu A do bodu D nás bude stát 17, ale cesta z bodu D do bodu A nás bude stát 12. Takže nemůžeme přiřadit dvě různé váhy, pokud se jedná o neorientovaný graf.
Nekonečný graf
Graf bude obsahovat nekonečný počet hran a uzlů. Pokud je graf nekonečný a zároveň souvislý, bude obsahovat i nekonečný počet hran. Rozšířené hrany zde znamenají, že k těmto uzlům může být prostřednictvím hran připojeno více hran. Zde je příklad nekonečného grafu:
Nekonečný graf
Null Graph
Nulový graf obsahuje pouze uzly nebo vrcholy, ale nemá žádné hrany. Pokud je dán graf G = (V, E), kde V jsou vrcholy a E jsou hrany, bude nulový, pokud je počet hran E nula. Zde je příklad nulového grafu:
Null Graph
Triviální graf
Datová struktura grafu je považována za triviální, pokud je přítomen pouze jeden vrchol nebo uzel bez hran. Zde je příklad triviálního grafu:
Více grafů
Graf se nazývá multigraf, pokud se mezi dvěma vrcholy nachází více hran nebo pokud má vrchol smyčku. Termín „smyčka“ v datové struktuře grafu znamená hranu směřující ke stejnému uzlu nebo vrcholu. Multigraf může být orientovaný nebo neorientovaný. Zde je příklad multigrafu:
Z B do A vedou dvě hrany. Vrchol E má navíc smyčku po sobě. Výše uvedený graf je orientovaný graf bez vah na hranách.
Kompletní graf
Graf je úplný, pokud má každý vrchol orientované nebo neorientované hrany se všemi ostatními vrcholy. Předpokládejme, že existuje celkem V vrcholů a každý vrchol má přesně V-1 hran. Pak se tento graf bude nazývat úplný graf. V tomto typu grafu je každý vrchol propojen se všemi ostatními vrcholy pomocí hran. Zde je příklad úplného grafu s pěti vrcholy:
Na obrázku vidíte, že celkový počet uzlů je pět a všechny uzly mají přesně čtyři hrany.
Připojený graf
Graf se nazývá propojený graf, pokud začínáme v uzlu nebo vrcholu a můžeme se z něj dostat ke všem uzlům. K tomu je nutné, aby mezi každou dvojicí uzlů nebo vrcholů byla alespoň jedna hrana. Zde je příklad propojeného grafu:
Zde je vysvětlení výše uvedeného propojeného grafu:
- Za předpokladu, že mezi C a F není hrana, nemůžeme se dostat z A do G. Hrana C do F nám však umožňuje dostat se z daného uzlu do libovolného uzlu.
- Kompletní graf je spojený graf, protože se můžeme přesunout z uzlu do kteréhokoli jiného uzlu v daném grafu.
Cyklický graf
Graf se nazývá cyklický, pokud se v něm nachází jeden nebo více cyklů. Zde je příklad cyklického grafu:
Vrcholy A, B a C zde tvoří cyklus. Graf může mít uvnitř více cyklů.
Řízený acyklický graf (DAG)
Graf se nazývá orientovaný acyklický graf neboli DAG, pokud uvnitř grafu nejsou žádné cykly. DAG je důležitý při provádění Topologické řazení nebo nalezení pořadí provádění. DAG je také důležitý pro vytváření systémů plánování nebo skenování závislostí zdrojů atd. Výše uvedený graf však neobsahuje žádný cyklus uvnitř. Zde je jednoduchý příklad orientovaného acyklického grafu (DAG):
Graf cyklu
Cyklický graf není totéž co cyklický graf. V cyklickém grafu bude mít každý uzel přesně dvě spojené hrany, což znamená, že každý uzel bude mít přesně dva stupně. Zde je příklad cyklického grafu:
Bipartitní graf
Tyto druhy Grafy jsou speciální druhy grafů, kde jsou vrcholy přiřazeny dvěma množinám. Dvoudílný graf musí splňovat pravidlo:
- Dvě sady vrcholů by měly být odlišné, což znamená, že všechny vrcholy musí být rozděleny do dvou skupin nebo sad.
- Vrcholy stejné množiny by neměly tvořit žádné hrany.
Eulerův graf
Datová struktura Graf se považuje za Eulerův graf, pokud všechny vrcholy mají sudý stupeň. Pojem stupeň vrcholů znamená počet hran směřujících k danému vrcholu nebo z něj vycházejících. Zde je příklad Eulerova grafu:
Všechny vrcholy mají sudé stupně. Vrcholy A, D, E a H mají dva stupně. Zde má uzel C čtyři stupně, což je sudé.
Hamiltonův graf
Hamiltonův graf je propojený graf, kde můžete navštívit všechny vrcholy z daného vrcholu, aniž byste museli znovu navštívit stejný uzel nebo použít stejnou hranu. Tento typ propojeného grafu je známý jako „Hamiltonův graf“. Cesta, kterou navštívíte, abyste ověřili, zda je daný graf Hamiltonovým grafem, se nazývá Hamiltonova cesta. Zde je jednoduchý příklad grafu Hamiltonu:
Na tomto obrázku můžeme navštívit všechny vrcholy z libovolného uzlu ve výše uvedeném grafu. Jedna z cest může být ADCHBEJe také možné najít Hamiltonův cyklus. Hamiltonův cyklus začíná a končí ve stejném vrcholu. Hamiltonův cyklus tedy bude ADCHBEA.
