Typy grafů v datové struktuře s příklady

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 dvojicemi vrcholů.

Grafy mohou být více typů v závislosti na poloze uzlů a hran. Zde jsou některé důležité typy grafů:

Režírovaný graf

Okraje orientovaného grafu obsahují šipky, které znamenají směr. Šipka určuje, kam hrana směřuje nebo končí.

Zde je příklad řízeného grafu.

• 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 ukazuje z A do 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 můžeme cestovat opačně mezi dvěma vrcholy.

Zde je jednoduchý příklad neorientovaného grafu.

Ve výše uvedeném grafu

• Můžeme se přesunout z A do 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 okrajích, se nazývá vážený graf. Číselná hodnota obecně představuje náklady na přesun z jednoho vrcholu do druhého. Jak směrovaný, tak neorientovaný graf mohou mít na okrajích závaží.

Zde je příklad váženého grafu (Directed).

• A do B, je tu hrana a váha je 5, což znamená, že přesun z A do B nás bude stát 5.
• Bod do bodu B, ale v tomto grafu nemá B žádnou přímou výhodu oproti bodu A. Nemůžeme tedy cestovat z bodu B do bodu A.
• Pokud se však chceme přesunout z A do F, existuje několik cest. Cesty jsou ADF, ABF. ADF bude stát (10+11) nebo 21.
• Zde bude cesta ABF stát (5+15) nebo 20. Zde přidáváme váhu každé hrany v cestě.

Zde je příklad neorientovaného grafu s váhami:

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. To znamená

• Obecně platí, že neorientovaný graf může mít 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:

Cesta z A do D nás bude stát 17, ale cesta z D do A nás bude stát 12. Nemůžeme tedy přiřadit dvě různé váhy, pokud se jedná o neorientovaný graf.

Nekonečný graf

Graf bude obsahovat nekonečné množství hran a uzlů. Pokud je graf nekonečný a je to také souvislý graf, pak bude obsahovat také nekonečný počet hran. Zde rozšířené hrany znamenají, že k těmto uzlům může být připojeno více hran pomocí hran.

Zde je příklad nekonečného grafu:

Null Graph

Null Graph obsahuje pouze uzly nebo vrcholy, ale bez hran. Pokud je dán graf G = (V, E), kde V jsou vrcholy a E jsou hrany, bude nulový, pokud je počet hran E nulový.

Zde je příklad nulového grafu:

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, když je mezi dvěma vrcholy přítomno více hran nebo 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 řízený nebo neorientovaný.

Zde je příklad multigrafu:

Od B k A jsou dvě hrany. Navíc má vrchol E vlastní smyčku. 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 celkový počet V vrcholů a každý vrchol má přesně V-1 hrany. Potom se tento graf bude nazývat úplný graf. V tomto typu grafu je každý vrchol spojen se všemi ostatními vrcholy pomocí hran.

Zde je příklad úplného grafu s pěti vrcholy:

Na obrázku můžete vidět, ž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á spojený graf, pokud začínáme od uzlu nebo vrcholu a procházíme všechny uzly od počátečního uzlu. K tomu by měla být mezi každou dvojicí uzlů nebo vrcholů alespoň jedna hrana.

Zde je příklad připojeného grafu:

Zde je vysvětlení výše uvedeného „úplného příkladu grafu“ grafu:

• Za předpokladu, že mezi C a F není žádná hrana, nemůžeme cestovat z A do G. Hrana C do F nám však umožňuje cestovat do libovolného uzlu z dané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

O grafu se říká, že je cyklický, pokud je v grafu přítomen jeden nebo více cyklů.

Zde je příklad cyklického grafu:

Zde vrcholy A, B a C tvoří cyklus.

Graf může mít v sobě více cyklů.

Řízený acyklický graf (DAG)

Graf se nazývá řízený acyklický graf nebo DAG, pokud v grafu nejsou žádné cykly. DAG je při tom důležitý Topologické řazení nebo zjištění exekučního příkazu. DAG je také důležitý pro vytváření plánovacích systémů nebo skenování závislosti zdrojů atd. Výše ​​uvedený graf však uvnitř žádný cyklus neobsahuje.

Zde je jednoduchý příklad směrovaného acyklického grafu (DAG):

Graf cyklu

Cyklický graf není stejný jako cyklický graf. V grafu cyklu bude mít každý uzel propojené přesně dvě 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.

Bipartitní graf se musí řídit pravidlem:

• 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.
• Stejná sada Vrcholy by neměly tvořit žádné hrany.

Eulerův graf

Datové struktury grafu jsou považovány za Eulerův graf, pokud mají všechny vrcholy sudý stupeň. Pod pojmem stupeň vrcholů se rozumí počet hran směřujících nebo vycházejících z určitého vrcholu.

Zde je příklad Eulerova grafu:

Všechny vrcholy mají sudé stupně. Vertex A, D, E a H mají dva stupně. Zde má uzel C čtyři stupně, což je sudé.

Hamiltonův graf

Hamilton Graph je Connect Graph, kde můžete navštívit všechny vrcholy z daného vrcholu, aniž byste museli znovu navštěvovat stejný uzel nebo používat stejnou hranu. Tento druh připojeného grafu je známý jako „Hamiltonův graf“. Cesta, kterou navštívíte, abyste ověřili, zda daný graf je Hamiltonův graf nebo ne, se nazývá Hamiltonovská cesta.

Zde je jednoduchý příklad Hamiltonova grafu:

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 ADCHBE. Je také možné najít Hamiltonův cyklus. Hamiltonův cyklus začíná a končí ve stejném vrcholu. Takže Hamiltonův cyklus bude ADCHBEA.