Selv om det er mange forskjellige typer grafer avhengig av antall toppunkter, antall kanter, sammenkoblinger og deres generelle struktur, er noen av slike vanlige typer grafer som følger:
1. Null graf
EN null graf er en graf der det ikke er noen kanter mellom toppene. En nullgraf kalles også tom graf.
Eksempel
En nullgraf med n toppunkter er betegnet med Nn.
2. Triviell graf
EN triviell graf er grafen som bare har ett toppunkt.
Eksempel
I grafen ovenfor er det bare ett toppunkt 'v' uten noen kant. Derfor er det en triviell graf.
3. Enkel graf
EN enkel graf er den urettede grafen med ingen parallelle kanter og ingen løkker .
En enkel graf som har n toppunkter, graden av hvert toppunkt er maksimalt n -1.Eksempel
I eksemplet ovenfor er første graf ikke en enkel graf fordi den har to kanter mellom toppunktene A og B, og den har også en løkke.
Den andre grafen er en enkel graf fordi den ikke inneholder noen sløyfe og parallelle kanter.
4. Udirigert graf
An urettet graf er en graf hvis kanter er ikke regissert .
Eksempel
Siden det ikke er noen rettede kanter i grafen ovenfor, er det derfor en urettet graf.
5. Regissert graf
EN rettet graf er en graf der kantene er rettet med piler.
Rettet graf er også kjent som digrafer .
Eksempel
I grafen ovenfor er hver kant rettet av pilen. En rettet kant har en pil fra A til B, betyr at A er relatert til B, men B er ikke relatert til A.
6. Fullfør graf
En graf der hvert par av hjørner er forbundet med nøyaktig én kant kalles komplett graf . Den inneholder alle mulige kanter.
En komplett graf med n toppunkter inneholder nøyaktig nC2-kanter og er representert ved Kn.
Eksempel
I eksemplet ovenfor, siden hvert toppunkt i grafen er forbundet med alle de gjenværende toppunktene gjennom nøyaktig én kant, er derfor begge grafene komplette grafer.
7. Tilkoblet graf
EN tilkoblet graf er en graf der vi kan gå fra et hvilket som helst toppunkt til et hvilket som helst annet toppunkt. I en tilkoblet graf eksisterer det minst én kant eller bane mellom hvert par av hjørner.
Eksempel
I eksemplet ovenfor kan vi gå fra et hvilket som helst toppunkt til et hvilket som helst annet toppunkt. Det betyr at det eksisterer minst én bane mellom hvert par av hjørner, derfor er det en sammenkoblet graf.
8. Frakoblet graf
EN frakoblet graf er en graf der det ikke finnes noen bane mellom hvert par av hjørner.
Eksempel
Grafen ovenfor består av to uavhengige komponenter som er frakoblet. Siden det ikke er mulig å gå fra toppunktene til en komponent til toppunktene til andre komponenter, er det derfor en frakoblet graf.
9. Vanlig graf
EN Vanlig graf er en graf der graden av alle toppunktene er like.
Hvis graden av alle toppunktene er k, kalles det k-regulær graf.
Eksempel
I eksemplet ovenfor har alle toppunktene grad 2. Derfor kalles de 2- Vanlig graf .
10. Syklisk graf
En graf med 'n' hjørner (hvor, n>=3) og 'n' kanter som danner en syklus av 'n' med alle kantene er kjent som syklusgraf .
En graf som inneholder minst én syklus er kjent som en syklisk graf .
I syklusgrafen er graden av hvert toppunkt 2.
Syklusgrafen som har n toppunkter er betegnet med Cn.
quicksort-algoritme
Eksempel 1
I eksemplet ovenfor har alle toppunktene grad 2. Derfor er de alle sykliske grafer.
Eksempel 2
Siden grafen ovenfor inneholder to sykluser, er den derfor en syklisk graf.
11. Asyklisk graf
En graf som ikke inneholder noen syklus kalles en asyklisk graf .
Eksempel
Siden grafen ovenfor ikke inneholder noen syklus, er den derfor en asyklisk graf.
12. Todelt graf
EN todelt graf er en graf der toppunktsettet kan deles inn i to sett slik at kantene bare går mellom settene, ikke innenfor dem.
En graf G (V, E) kalles todelt graf hvis toppunktsettet V(G) kan dekomponeres i to ikke-tomme disjunkte delsett V1(G) og V2(G) på en slik måte at hver kant e ∈ E (G) har sitt siste ledd i V1(G) og et annet siste punkt i V2(G).
Partisjonen V = V1 ∪ V2 er kjent som bipartisjon av G.
Eksempel 1
Eksempel 2
13. Fullfør todelt graf
EN komplett todelt graf er en todelt graf der hvert toppunkt i det første settet er forbundet med hvert toppunkt i det andre settet med nøyaktig én kant.
En komplett todelt graf er en todelt graf som er komplett.
Complete Bipartite graph = Bipartite graph + Complete graph
Eksempel
Grafen ovenfor er kjent som K4,3.
14. Stjernegraf
En stjernegraf er en komplett todelt graf der n-1 toppunkter har grad 1 og et enkelt toppunkt har grad (n -1). Dette ser nøyaktig ut som en stjerne der (n - 1) toppunkter er koblet til et enkelt sentralt toppunkt.
En stjernegraf med n toppunkter er merket med Sn.
Eksempel
I eksemplet ovenfor, av n toppunkter, er alle (n-1) toppunktene koblet til et enkelt toppunkt. Derfor er det en stjernegraf.
15 Vektet graf
En vektet graf er en graf hvis kanter er merket med noen vekter eller tall.
Lengden på en bane i en vektet graf er summen av vektene til alle kantene i banen.
Eksempel
I grafen ovenfor, hvis banen er a -> b -> c -> d -> e -> g, er lengden på banen 5 + 4 + 5 + 6 + 5 = 25.
16. Multigraf
En graf der det er flere kanter mellom et hvilket som helst par av toppunkter eller det er kanter fra et toppunkt til seg selv (løkke) kalles en multi - graf .
Eksempel
I grafen ovenfor er toppunktsettet B og C forbundet med to kanter. Tilsvarende er toppunktsettene E og F forbundet med 3 kanter. Derfor er det en multigraf.
17. Plan graf
EN plan graf er en graf som vi kan tegne i et plan på en slik måte at ingen to kanter av det krysser hverandre bortsett fra ved et toppunkt som de faller inn i.
Eksempel
Grafen ovenfor ser kanskje ikke ut til å være plan fordi den har kanter som krysser hverandre. Men vi kan tegne grafen ovenfor på nytt.
De tre plantegningene av grafen ovenfor er:
De tre grafene ovenfor består ikke av to kanter som krysser hverandre, og derfor er alle grafene ovenfor plane.
18. Ikke-plan graf
En graf som ikke er en plan graf kalles en ikke-plan graf. Med andre ord, en graf som ikke kan tegnes uten i det minste på par av dens kryssende kanter er kjent som en ikke-plan graf.
Eksempel
Grafen ovenfor er en ikke-plan graf.