Iako postoji puno različitih tipova grafova ovisno o broju vrhova, broju bridova, međusobnoj povezanosti i njihovoj cjelokupnoj strukturi, neki od takvih uobičajenih tipova grafova su sljedeći:
1. Nul graf
A nulti graf je graf u kojem nema bridova između njegovih vrhova. Nulti graf se još naziva i prazan graf.
Primjer
Nulti graf s n vrhova označava se s Nn.
2. Trivijalni graf
A trivijalni graf je graf koji ima samo jedan vrh.
Primjer
U gornjem grafu postoji samo jedan vrh 'v' bez ikakvog ruba. Stoga je to trivijalan graf.
3. Jednostavni grafikon
A jednostavan graf je neusmjereni graf sa nema paralelnih bridova i bez petlji .
Jednostavan graf koji ima n vrhova, stupanj svakog vrha je najviše n -1.Primjer
U gornjem primjeru, prvi graf nije jednostavan graf jer ima dva brida između vrhova A i B i također ima petlju.
Drugi graf je jednostavan graf jer ne sadrži nikakve petlje i paralelne bridove.
4. Neusmjereni graf
An neusmjereni graf je graf čiji su bridovi nije usmjereno .
Primjer
Budući da u gornjem grafu nema usmjerenih rubova, to je neusmjereni graf.
5. Usmjereni graf
A usmjereni graf je grafikon u kojem se rubovi su usmjereni strijelama.
Usmjereni graf je također poznat kao digrafi .
Primjer
Na gornjem grafikonu, svaki rub je usmjeren strelicom. Usmjereni rub ima strelicu od A do B, znači da je A povezan s B, ali B nije povezan s A.
6. Ispunite grafikon
Graf u kojem je svaki par vrhova spojen točno jednim bridom nazivamo kompletan graf . Sadrži sve moguće rubove.
Kompletan graf s n vrhova sadrži točno nC2 bridova i predstavljen je s Kn.
Primjer
U gornjem primjeru, budući da je svaki vrh u grafu povezan sa svim preostalim vrhovima kroz točno jedan rub, oba su grafa potpuni graf.
7. Povezani graf
A povezani graf je graf u kojem možemo doći od bilo kojeg vrha do bilo kojeg drugog vrha. U povezanom grafu postoji barem jedan brid ili put između svakog para vrhova.
Primjer
U gornjem primjeru, možemo prijeći od bilo kojeg vrha do bilo kojeg drugog vrha. To znači da postoji barem jedan put između svakog para vrhova, stoga je to povezani graf.
8. Isključeni graf
A nepovezani graf je graf u kojem ne postoji niti jedan put između svakog para vrhova.
Primjer
Gornji graf sastoji se od dvije neovisne komponente koje nisu povezane. Budući da nije moguće doći od vrhova jedne komponente do vrhova drugih komponenti, to je nepovezani graf.
9. Regularni graf
A Redovni graf je graf u kojem je stupanj svih vrhova isti.
Ako je stupanj svih vrhova k, tada se zove k-regularni graf.
Primjer
U gornjem primjeru, svi vrhovi imaju stupanj 2. Stoga se nazivaju 2- Redovni graf .
10. Ciklični graf
Graf s 'n' vrhova (gdje je n>=3) i 'n' rubova koji tvore ciklus od 'n' sa svim svojim rubovima poznat je kao ciklusni graf .
Graf koji sadrži barem jedan ciklus poznat je kao a ciklički graf .
U cikličnom grafu stupanj svakog vrha je 2.
Ciklusni graf koji ima n vrhova označava se sa Cn.
java komentari
Primjer 1
U gornjem primjeru, svi vrhovi imaju stupanj 2. Stoga su svi ciklički grafovi.
Primjer 2
Budući da gornji graf sadrži dva ciklusa, on je ciklički graf.
11. Aciklički graf
Graf koji u sebi ne sadrži nijedan ciklus naziva se an aciklički graf .
Primjer
Budući da gornji graf ne sadrži cikluse, on je aciklički graf.
12. Bipartitni graf
A bipartitni graf je graf u kojem se skup vrhova može podijeliti u dva skupa tako da rubovi idu samo između skupova, a ne unutar njih.
Graf G (V, E) naziva se bipartitni graf ako se njegov skup vrhova V(G) može rastaviti na dva neprazna disjunktna podskupa V1(G) i V2(G) na takav način da svaki brid e ∈ E (G) ima zadnji zglob u V1(G), a drugu posljednju točku u V2(G).
Particija V = V1 ∪ V2 je poznata kao biparticija od G.
Primjer 1
Primjer 2
13. Potpuni bipartitni graf
A potpuni bipartitni graf je bipartitni graf u kojem je svaki vrh u prvom skupu spojen sa svakim vrhom u drugom skupu s točno jednim rubom.
Potpuni bipartitni graf je bipartitni graf koji je potpun.
Complete Bipartite graph = Bipartite graph + Complete graph
Primjer
Gornji graf je poznat kao K4,3.
14. Grafikon zvijezda
Zvjezdasti graf je potpuni bipartitni graf u kojem n-1 vrhova ima stupanj 1, a jedan vrh ima stupanj (n -1). Ovo točno izgleda kao zvijezda gdje su (n - 1) vrhovi povezani s jednim središnjim vrhom.
Zvjezdasti graf s n vrhova označava se sa Sn.
Primjer
U gornjem primjeru, od n vrhova, svi (n-1) vrhovi su povezani s jednim vrhom. Dakle, to je zvjezdani graf.
15 Ponderirani grafikon
Ponderirani graf je graf čiji su rubovi označeni nekim težinama ili brojevima.
Duljina puta u ponderiranom grafu je zbroj težina svih bridova na putu.
Primjer
U gornjem grafikonu, ako je put a -> b -> c -> d -> e -> g tada je duljina puta 5 + 4 + 5 + 6 + 5 = 25.
16. Višestruki graf
Graf u kojem postoji više bridova između bilo kojeg para vrhova ili postoje bridovi od vrha do samog sebe (petlja) naziva se višestruki graf .
Primjer
U gornjem grafu, skup vrhova B i C povezani su s dva brida. Slično, skupovi vrhova E i F povezani su s 3 brida. Dakle, radi se o multigrafu.
17. Planarni graf
A planarni graf je graf koji možemo nacrtati u ravnini na takav način da nijedna dva njegova ruba ne sijeku jedan drugoga osim u vrhu na koji su incidentni.
Primjer
Gornji graf se možda neće činiti ravnim jer ima rubove koji se križaju. Ali možemo ponovno nacrtati gornji grafikon.
Tri ravni crteža gornjeg grafa su:
Gornja tri grafa se ne sastoje od dva brida koji se križaju i stoga su svi gornji grafovi planarni.
18. Neplanarni graf
Graf koji nije planaran naziva se neplanaran graf. Drugim riječima, graf koji se ne može nacrtati bez barem jednog para njegovih bridova koji se križaju je poznat kao neplanarni graf.
Primjer
Gornji graf je neplanaran graf.