Čeprav obstaja veliko različnih vrst grafov, odvisno od števila vozlišč, števila robov, medsebojne povezanosti in njihove splošne strukture, je nekaj takih običajnih vrst grafov naslednje:
1. Ničelni graf
A ničelni graf je graf, v katerem med svojimi vozlišči ni robov. Ničelni graf se imenuje tudi prazen graf.
Primer
Ničelni graf z n vozlišči je označen z Nn.
2. Trivialni graf
A trivialni graf je graf, ki ima samo eno vozlišče.
Primer
V zgornjem grafu je samo eno oglišče 'v' brez roba. Zato je trivialen graf.
3. Preprost graf
A preprost graf je neusmerjen graf z brez vzporednih robov in brez zank .
Preprost graf, ki ima n oglišč, je stopnja vsakega oglišča največ n -1.Primer
V zgornjem primeru prvi graf ni preprost graf, ker ima dva robova med točkama A in B ter ima tudi zanko.
Drugi graf je preprost graf, ker ne vsebuje zank in vzporednih robov.
4. Neusmerjeni graf
An neusmerjeni graf je graf, katerega robovi so ni usmerjeno .
Primer
V zgornjem grafu ni usmerjenih robov, zato je neusmerjen graf.
5. Usmerjeni graf
A usmerjeni graf je graf, v katerem je robovi so usmerjeni s puščicami.
Usmerjeni graf je znan tudi kot digrafi .
Primer
V zgornjem grafu je vsak rob usmerjen s puščico. Usmerjen rob ima puščico od A do B, kar pomeni, da je A povezan z B, vendar B ni povezan z A.
6. Dopolnite graf
Imenuje se graf, v katerem je vsak par vozlišč povezan z natanko enim robom celoten graf . Vsebuje vse možne robove.
Celoten graf z n vozlišči vsebuje točno nC2 robov in je predstavljen s Kn.
Primer
Ker je v zgornjem primeru vsako vozlišče v grafu povezano z vsemi preostalimi vozlišči skozi natanko en rob, sta oba grafa popolna grafa.
7. Povezani graf
A povezani graf je graf, v katerem lahko obiščemo katero koli točko v kateri koli drugi točki. V povezanem grafu obstaja vsaj en rob ali pot med vsakim parom vozlišč.
Primer
V zgornjem primeru lahko prečkamo od katere koli točke do katere koli druge točke. To pomeni, da obstaja vsaj ena pot med vsakim parom vozlišč, torej je to povezan graf.
8. Odklopljen graf
A nepovezani graf je graf, v katerem nobena pot ne obstaja med vsakim parom vozlišč.
Primer
Zgornji graf je sestavljen iz dveh neodvisnih komponent, ki nista povezani. Ker ni mogoče obiskati iz oglišč ene komponente v oglišča drugih komponent, je torej nepovezan graf.
9. Redni graf
A Redni graf je graf, v katerem je stopnja vseh vozlišč enaka.
Če je stopnja vseh vozlišč k, se imenuje k-regularni graf.
Primer
V zgornjem primeru imajo vsa oglišča stopnjo 2. Zato se imenujejo 2- Redni graf .
10. Ciklični graf
Graf z 'n' vozlišči (kjer je n>=3) in 'n' robovi, ki tvorijo cikel 'n' z vsemi svojimi robovi, je znan kot ciklični graf .
Graf, ki vsebuje vsaj en cikel, je znan kot a ciklični graf .
V cikličnem grafu je stopnja vsakega vozlišča 2.
Cikelni graf, ki ima n vozlišč, označimo s Cn.
10 1 milijon
Primer 1
V zgornjem primeru imajo vsa oglišča stopnjo 2. Zato so vsi ciklični grafi.
Primer 2
Ker zgornji graf vsebuje dva cikla, je torej cikličen graf.
11. Aciklični graf
Graf, ki v sebi ne vsebuje nobenega cikla, se imenuje aciklični graf .
Primer
Ker zgornji graf ne vsebuje nobenega cikla, je torej acikličen graf.
12. Bipartitni graf
A bipartitni graf je graf, v katerem se lahko množica vozlišč razdeli na dve množici, tako da gredo robovi le med množicami, ne pa znotraj njih.
Graf G (V, E) imenujemo bipartitni graf, če je njegovo množico vozlišč V(G) mogoče razstaviti na dve neprazni disjunktni podmnožici V1(G) in V2(G) tako, da je vsak rob e ∈ E (G) ima svoj zadnji sklep v V1(G) in drugo zadnjo točko v V2(G).
Razdelitev V = V1 ∪ V2 je znana kot biparticija G.
Primer 1
Primer 2
13. Dopolnite dvodelni graf
A popoln bipartitni graf je dvodelni graf, v katerem je vsako vozlišče v prvem nizu povezano z vsakim vozliščem v drugem nizu z natanko enim robom.
Popolni bipartitni graf je dvodelni graf, ki je popoln.
Complete Bipartite graph = Bipartite graph + Complete graph
Primer
Zgornji graf je znan kot K4,3.
14. Zvezdni graf
Zvezdni graf je popoln dvodelni graf, v katerem ima n-1 vozlišč stopnjo 1, posamezna vozlišča pa stopnjo (n -1). To natanko izgleda kot zvezda, kjer je (n - 1) oglišč povezanih z enim samim osrednjim ogliščem.
Zvezdni graf z n vozlišči je označen s Sn.
Primer
V zgornjem primeru so od n oglišč vsa (n-1) oglišča povezana z enim samim ogliščem. Gre torej za zvezdni graf.
15 Uteženi graf
Uteženi graf je graf, katerega robovi so označeni z utežmi ali številkami.
Dolžina poti v uteženem grafu je vsota uteži vseh robov na poti.
Primer
Če je v zgornjem grafu pot a -> b -> c -> d -> e -> g, potem je dolžina poti 5 + 4 + 5 + 6 + 5 = 25.
16. Večgraf
Graf, v katerem obstaja več robov med katerim koli parom vozlišč ali obstajajo robovi od vozlišča do samega sebe (zanka), se imenuje multigraf .
Primer
V zgornjem grafu sta množici vozlišč B in C povezani z dvema robovoma. Podobno sta množici vozlišč E in F povezani s 3 robovi. Zato je multi graf.
17. Planarni graf
A ravninski graf je graf, ki ga lahko narišemo v ravnino tako, da se nobena dva roba ne križata drug drugega, razen v točki, na katero sta incidentna.
Primer
Zgornji graf se morda ne zdi ravninski, ker ima robove, ki se križajo. Lahko pa na novo narišemo zgornji graf.
Tri ravninske risbe zgornjega grafa so:
Zgornji trije grafi niso sestavljeni iz dveh križajočih se robov, zato so vsi zgornji grafi ravninski.
18. Neplanarni graf
Graf, ki ni ravninski graf, se imenuje neravninski graf. Z drugimi besedami, graf, ki ga ni mogoče narisati brez vsaj enega para križajočih se robov, je znan kot neravni graf.
Primer
Zgornji graf je neplanaren graf.