Aj keď existuje veľa rôznych typov grafov v závislosti od počtu vrcholov, počtu hrán, vzájomnej prepojenosti a ich celkovej štruktúry, niektoré z takýchto bežných typov grafov sú nasledovné:
1. Nulový graf
A nulový graf je graf, v ktorom medzi jeho vrcholmi nie sú žiadne hrany. Nulový graf sa tiež nazýva prázdny graf.
Príklad
Nulový graf s n vrcholmi je označený Nn.
2. Triviálny graf
A triviálny graf je graf, ktorý má iba jeden vrchol.
Príklad
Vo vyššie uvedenom grafe je len jeden vrchol 'v' bez akejkoľvek hrany. Ide teda o triviálny graf.
3. Jednoduchý graf
A jednoduchý graf je neorientovaný graf s žiadne paralelné hrany a žiadne slučky .
Jednoduchý graf, ktorý má n vrcholov, pričom stupeň každého vrcholu je najviac n -1.Príklad
Vo vyššie uvedenom príklade nie je Prvý graf jednoduchý graf, pretože má dve hrany medzi vrcholmi A a B a má tiež slučku.
Druhý graf je jednoduchý graf, pretože neobsahuje žiadnu slučku a rovnobežné hrany.
4. Neorientovaný graf
An neorientovaný graf je graf, ktorého hrany sú neriadený .
Príklad
Vo vyššie uvedenom grafe, pretože neexistujú žiadne smerované hrany, je to neorientovaný graf.
5. Riadený graf
A orientovaný graf je graf, v ktorom je hrany sú nasmerované šípkami.
Orientovaný graf je tiež známy ako digrafy .
Príklad
Vo vyššie uvedenom grafe je každá hrana nasmerovaná šípkou. Smerovaná hrana má šípku od A do B, čo znamená, že A súvisí s B, ale B nesúvisí s A.
6. Kompletný graf
Nazýva sa graf, v ktorom je každá dvojica vrcholov spojená práve jednou hranou kompletný graf . Obsahuje všetky možné hrany.
Kompletný graf s n vrcholmi obsahuje presne nC2 hrán a je reprezentovaný Kn.
Príklad
Vo vyššie uvedenom príklade, keďže každý vrchol v grafe je spojený so všetkými zvyšnými vrcholmi presne jednou hranou, oba grafy sú úplným grafom.
7. Pripojený graf
A spojený graf je graf, v ktorom môžeme prejsť z ktoréhokoľvek vrcholu do akéhokoľvek iného vrcholu. V prepojenom grafe existuje medzi každým párom vrcholov aspoň jedna hrana alebo cesta.
Príklad
Vo vyššie uvedenom príklade môžeme prejsť z ktoréhokoľvek vrcholu do akéhokoľvek iného vrcholu. Znamená to, že medzi každým párom vrcholov existuje aspoň jedna cesta, preto ide o súvislý graf.
8. Odpojený graf
A odpojený graf je graf, v ktorom medzi každým párom vrcholov neexistuje žiadna cesta.
Príklad
Vyššie uvedený graf pozostáva z dvoch nezávislých komponentov, ktoré sú odpojené. Keďže nie je možné prejsť z vrcholov jedného komponentu na vrcholy iných komponentov, ide o nesúvislý graf.
9. Pravidelný graf
A Pravidelný graf je graf, v ktorom je stupeň všetkých vrcholov rovnaký.
Ak je stupeň všetkých vrcholov k, potom sa nazýva k-regulárny graf.
Príklad
Vo vyššie uvedenom príklade majú všetky vrcholy stupeň 2. Preto sa nazývajú 2- Pravidelný graf .
10. Cyklický graf
Graf s 'n' vrcholmi (kde, n>=3) a 'n' hranami tvoriacimi cyklus 'n' so všetkými jeho hranami je známy ako graf cyklu .
Graf obsahujúci aspoň jeden cyklus je známy ako a cyklický graf .
V grafe cyklu je stupeň každého vrcholu 2.
Graf cyklu, ktorý má n vrcholov, označíme Cn.
čo je mac os
Príklad 1
Vo vyššie uvedenom príklade majú všetky vrcholy stupeň 2. Preto sú všetky cyklické grafy.
Príklad 2
Keďže vyššie uvedený graf obsahuje dva cykly, ide o cyklický graf.
11. Acyklický graf
Graf, ktorý neobsahuje žiadny cyklus, sa nazýva an acyklický graf .
Príklad
Keďže vyššie uvedený graf neobsahuje žiadny cyklus, ide o acyklický graf.
12. Bipartitný graf
A bipartitný graf je graf, v ktorom je možné množinu vrcholov rozdeliť na dve množiny tak, že hrany idú iba medzi množinami, nie v rámci nich.
Graf G (V, E) sa nazýva bipartitný graf, ak jeho vrcholovú množinu V(G) možno rozložiť na dve neprázdne disjunktné podmnožiny V1(G) a V2(G) tak, že každá hrana e ∈ E (G) má svoj posledný spoj vo V1(G) a druhý posledný bod vo V2(G).
Rozdelenie V = V1 ∪ V2 je známe ako bipartícia G.
Príklad 1
Príklad 2
13. Vyplňte bipartitný graf
A úplný bipartitný graf je bipartitný graf, v ktorom je každý vrchol v prvej množine spojený s každým vrcholom v druhej množine práve jednou hranou.
Kompletný bipartitný graf je bipartitný graf, ktorý je úplný.
Complete Bipartite graph = Bipartite graph + Complete graph
Príklad
Vyššie uvedený graf je známy ako K4,3.
14. Hviezdny graf
Hviezdny graf je úplný bipartitný graf, v ktorom n-1 vrcholov má stupeň 1 a jeden vrchol má stupeň (n-1). Presne to vyzerá ako hviezda, kde (n - 1) vrcholov je spojených s jedným centrálnym vrcholom.
Hviezdny graf s n vrcholmi je označený Sn.
Príklad
Vo vyššie uvedenom príklade sú z n vrcholov všetky (n-1) vrcholy spojené s jedným vrcholom. Ide teda o hviezdicový graf.
15 Vážený graf
Vážený graf je graf, ktorého okraje boli označené nejakými váhami alebo číslami.
Dĺžka cesty vo váženom grafe je súčtom váh všetkých hrán v ceste.
Príklad
Ak je vo vyššie uvedenom grafe cesta a -> b -> c -> d -> e -> g, potom je dĺžka cesty 5 + 4 + 5 + 6 + 5 = 25.
16. Multigraf
Graf, v ktorom je viacero hrán medzi ľubovoľnou dvojicou vrcholov alebo sú hrany od vrcholu k sebe samému (slučka), sa nazýva multi - graf .
Príklad
Vo vyššie uvedenom grafe sú množiny vrcholov B a C spojené dvoma hranami. Podobne množiny vrcholov E a F sú spojené 3 hranami. Ide teda o multigraf.
17. Rovinný graf
A rovinný graf je graf, ktorý môžeme nakresliť v rovine takým spôsobom, že sa žiadne jeho dve hrany neprekrížia, s výnimkou vrcholu, ku ktorému dopadajú.
Príklad
Vyššie uvedený graf sa nemusí zdať rovinný, pretože má hrany, ktoré sa navzájom križujú. Ale môžeme prekresliť vyššie uvedený graf.
Tri rovinné výkresy vyššie uvedeného grafu sú:
Vyššie uvedené tri grafy sa neskladajú z dvoch hrán, ktoré sa navzájom križujú, a preto sú všetky vyššie uvedené grafy rovinné.
18. Nerovinný graf
Graf, ktorý nie je rovinným grafom, sa nazýva nerovinný graf. Inými slovami, graf, ktorý nemožno nakresliť bez aspoň jedného páru jeho krížiacich sa hrán, je známy ako nerovinný graf.
Príklad
Vyššie uvedený graf je nerovinný graf.