Ačkoli existuje mnoho různých typů grafů v závislosti na počtu vrcholů, počtu hran, vzájemné propojenosti a jejich celkové struktuře, některé z těchto běžných typů grafů jsou následující:
1. Nulový graf
A nulový graf je graf, ve kterém nejsou žádné hrany mezi jeho vrcholy. Nulový graf se také nazývá prázdný graf.
Příklad
Nulový graf s n vrcholy je označen Nn.
2. Triviální graf
A triviální graf je graf, který má pouze jeden vrchol.
Příklad
Ve výše uvedeném grafu je pouze jeden vrchol 'v' bez jakékoli hrany. Jedná se tedy o triviální graf.
3. Jednoduchý graf
A jednoduchý graf je neorientovaný graf s žádné rovnoběžné hrany a žádné smyčky .
Jednoduchý graf, který má n vrcholů, stupeň každého vrcholu je nejvýše n -1.Příklad
Ve výše uvedeném příkladu není První graf jednoduchý graf, protože má dvě hrany mezi vrcholy A a B a má také smyčku.
Druhý graf je jednoduchý graf, protože neobsahuje žádnou smyčku a rovnoběžné hrany.
4. Neorientovaný graf
An neorientovaný graf je graf, jehož hrany jsou není řízen .
Příklad
Ve výše uvedeném grafu, protože neexistují žádné směrované hrany, je to neorientovaný graf.
5. Režie grafu
A orientovaný graf je graf, ve kterém je hrany směřují pomocí šipek.
Orientovaný graf je také známý jako digrafy .
Příklad
Ve výše uvedeném grafu je každá hrana směrována šipkou. Orientovaná hrana má šipku od A do B, což znamená, že A souvisí s B, ale B nesouvisí s A.
6. Kompletní graf
Nazýváme graf, ve kterém je každá dvojice vrcholů spojena právě jednou hranou kompletní graf . Obsahuje všechny možné hrany.
Úplný graf s n vrcholy obsahuje přesně nC2 hran a je reprezentován Kn.
Příklad
Ve výše uvedeném příkladu, protože každý vrchol v grafu je spojen se všemi zbývajícími vrcholy právě jednou hranou, jsou tedy oba grafy úplným grafem.
7. Připojený graf
A připojený graf je graf, ve kterém můžeme přejít z libovolného vrcholu do kteréhokoli jiného vrcholu. V spojeném grafu existuje mezi každou dvojicí vrcholů alespoň jedna hrana nebo cesta.
Příklad
Ve výše uvedeném příkladu můžeme přejít z libovolného vrcholu do kteréhokoli jiného vrcholu. To znamená, že mezi každou dvojicí vrcholů existuje alespoň jedna cesta, jedná se tedy o souvislý graf.
8. Odpojený graf
A odpojený graf je graf, ve kterém neexistuje žádná cesta mezi každou dvojicí vrcholů.
Příklad
Výše uvedený graf se skládá ze dvou nezávislých složek, které jsou odpojené. Vzhledem k tomu, že není možné přejít z vrcholů jedné složky na vrcholy ostatních složek, jedná se o nesouvislý graf.
9. Pravidelný graf
A Běžný graf je graf, ve kterém je stupeň všech vrcholů stejný.
Pokud je stupeň všech vrcholů k, pak se nazývá k-regulární graf.
Příklad
Ve výše uvedeném příkladu mají všechny vrcholy stupeň 2. Proto se nazývají 2- Běžný graf .
10. Cyklický graf
Graf s 'n' vrcholy (kde, n>=3) a 'n' hranami tvořícími cyklus 'n' se všemi jeho hranami je známý jako graf cyklu .
Graf obsahující alespoň jeden cyklus se nazývá a cyklický graf .
V grafu cyklu je stupeň každého vrcholu 2.
Cyklický graf, který má n vrcholů, označíme Cn.
aritmeticko logická jednotka
Příklad 1
Ve výše uvedeném příkladu mají všechny vrcholy stupeň 2. Všechny jsou tedy cyklické grafy.
Příklad 2
Protože výše uvedený graf obsahuje dva cykly, jedná se o cyklický graf.
11. Acyklický graf
Graf, který neobsahuje žádný cyklus, se nazývá an acyklický graf .
Příklad
Vzhledem k tomu, že výše uvedený graf neobsahuje žádný cyklus, jedná se o acyklický graf.
12. Bipartitní graf
A bipartitní graf je graf, ve kterém lze množinu vrcholů rozdělit na dvě množiny tak, že hrany jdou pouze mezi množinami, nikoli uvnitř nich.
Graf G (V, E) se nazývá bipartitní graf, pokud lze jeho vrcholovou množinu V(G) rozložit na dvě neprázdné disjunktní podmnožiny V1(G) a V2(G) tak, že každá hrana e ∈ E (G) má svůj poslední spoj ve V1(G) a druhý poslední bod ve V2(G).
Oddíl V = V1 ∪ V2 je známý jako bipartition G.
Příklad 1
Příklad 2
13. Kompletní bipartitní graf
A kompletní bipartitní graf je bipartitní graf, ve kterém je každý vrchol v první sadě spojen s každým vrcholem ve druhé sadě právě jednou hranou.
Úplný bipartitní graf je bipartitní graf, který je úplný.
Complete Bipartite graph = Bipartite graph + Complete graph
Příklad
Výše uvedený graf je známý jako K4,3.
14. Hvězdný graf
Hvězdicový graf je úplný bipartitní graf, ve kterém n-1 vrcholů má stupeň 1 a jeden vrchol má stupeň (n-1). Přesně to vypadá jako hvězda, kde (n - 1) vrcholů je spojeno s jedním centrálním vrcholem.
Hvězdný graf s n vrcholy je označen Sn.
Příklad
Ve výše uvedeném příkladu jsou z n vrcholů všechny (n-1) vrcholy připojeny k jedinému vrcholu. Jedná se tedy o hvězdicový graf.
15 Vážený graf
Vážený graf je graf, jehož hrany byly označeny nějakými váhami nebo čísly.
Délka cesty ve váženém grafu je součtem vah všech hran v cestě.
Příklad
Pokud je ve výše uvedeném grafu cesta a -> b -> c -> d -> e -> g, pak je délka cesty 5 + 4 + 5 + 6 + 5 = 25.
16. Multigraf
Graf, ve kterém je více hran mezi libovolným párem vrcholů nebo kde jsou hrany od vrcholu k sobě samému (smyčka), se nazývá multi-graf .
Příklad
Ve výše uvedeném grafu je množina vrcholů B a C spojena dvěma hranami. Podobně vrcholové množiny E a F jsou spojeny 3 hranami. Jedná se tedy o multigraf.
17. Rovinný graf
A rovinný graf je graf, který můžeme nakreslit v rovině takovým způsobem, že se žádné jeho dvě hrany nekříží s výjimkou vrcholu, ke kterému dopadají.
Příklad
Výše uvedený graf se nemusí zdát rovinný, protože má hrany, které se navzájem kříží. Ale můžeme překreslit výše uvedený graf.
Tři rovinné výkresy výše uvedeného grafu jsou:
Výše uvedené tři grafy se neskládají ze dvou hran, které se navzájem kříží, a proto jsou všechny výše uvedené grafy rovinné.
18. Nerovinný graf
Graf, který není rovinným grafem, se nazývá nerovinný graf. Jinými slovy, graf, který nelze nakreslit bez alespoň jedné dvojice jeho křížících se hran, se nazývá nerovinný graf.
Příklad
Výše uvedený graf je nerovinný graf.