Selvom der er mange forskellige typer grafer afhængigt af antallet af hjørner, antallet af kanter, sammenkobling og deres overordnede struktur, er nogle af sådanne almindelige typer grafer som følger:
1. Nul-graf
EN nul graf er en graf, hvor der ikke er kanter mellem dens hjørner. En nul-graf kaldes også tom graf.
Eksempel
En nulgraf med n toppunkter er angivet med Nn.
2. Trivial graf
EN triviel graf er grafen, som kun har ét toppunkt.
Eksempel
I ovenstående graf er der kun et toppunkt 'v' uden nogen kant. Derfor er det en triviel graf.
3. Simpel graf
EN simpel graf er den urettede graf med ingen parallelle kanter og ingen løkker .
En simpel graf som har n toppunkter, graden af hvert toppunkt er højst n -1.Eksempel
I ovenstående eksempel er First graph ikke en simpel graf, fordi den har to kanter mellem hjørnerne A og B, og den har også en loop.
Anden graf er en simpel graf, fordi den ikke indeholder nogen løkke og parallelle kanter.
4. Udirigeret graf
An urettet graf er en graf, hvis kanter er ikke instrueret .
Eksempel
I ovenstående graf, da der ikke er nogen rettede kanter, er det derfor en urettet graf.
5. Directed Graph
EN rettet graf er en graf, hvori kanter er rettet med pile.
Dirigeret graf er også kendt som digrafer .
Eksempel
I ovenstående graf er hver kant rettet af pilen. En rettet kant har en pil fra A til B, hvilket betyder, at A er relateret til B, men B er ikke relateret til A.
6. Komplet graf
En graf, hvor hvert par af hjørner er forbundet med nøjagtig en kant kaldes komplet graf . Den indeholder alle mulige kanter.
En komplet graf med n hjørner indeholder nøjagtigt nC2 kanter og er repræsenteret ved Kn.
Eksempel
I ovenstående eksempel, da hvert knudepunkt i grafen er forbundet med alle de resterende spidser gennem nøjagtig en kant, er begge grafer derfor komplette grafer.
7. Forbundet graf
EN forbundet graf er en graf, hvor vi kan besøge fra et hvilket som helst toppunkt til ethvert andet toppunkt. I en forbundet graf eksisterer der mindst én kant eller sti mellem hvert par af hjørner.
Eksempel
I ovenstående eksempel kan vi krydse fra et hvilket som helst toppunkt til et hvilket som helst andet toppunkt. Det betyder, at der findes mindst én vej mellem hvert par af hjørner, derfor er det en forbundet graf.
8. Afbrudt graf
EN afbrudt graf er en graf, hvor der ikke findes nogen vej mellem hvert par af hjørner.
Eksempel
Ovenstående graf består af to uafhængige komponenter, som er afbrudt. Da det ikke er muligt at besøge fra hjørnerne af en komponent til hjørnerne af andre komponenter, er det derfor en afbrudt graf.
9. Almindelig graf
EN Almindelig graf er en graf, hvor graden af alle hjørnerne er ens.
Hvis graden af alle hjørnerne er k, så kaldes det k-regulær graf.
Eksempel
I ovenstående eksempel har alle toppunkter grad 2. Derfor kaldes de 2- Almindelig graf .
10. Cyklisk graf
En graf med 'n' hjørner (hvor, n>=3) og 'n' kanter, der danner en cyklus af 'n' med alle dens kanter, er kendt som cyklus graf .
En graf, der indeholder mindst én cyklus, er kendt som en cyklisk graf .
I cyklusgrafen er graden af hvert toppunkt 2.
Cyklusgrafen, som har n toppunkter, er angivet med Cn.
quicksort-algoritme
Eksempel 1
I ovenstående eksempel har alle toppunkter grad 2. Derfor er de alle cykliske grafer.
Eksempel 2
Da ovenstående graf indeholder to cyklusser, er det derfor en cyklisk graf.
11. Acyklisk graf
En graf, der ikke indeholder nogen cyklus, kaldes en acyklisk graf .
Eksempel
Da ovenstående graf ikke indeholder nogen cyklus, er det derfor en acyklisk graf.
12. Todelt Graf
EN todelt graf er en graf, hvor toppunktssættet kan opdeles i to sæt, således at kanter kun går mellem sæt, ikke inden for dem.
En graf G (V, E) kaldes todelt graf, hvis dens toppunktssæt V(G) kan dekomponeres i to ikke-tomme disjunkte undersæt V1(G) og V2(G) på en sådan måde, at hver kant e ∈ E (G) har sit sidste led i V1(G) og et andet sidste punkt i V2(G).
Partitionen V = V1 ∪ V2 er kendt som bipartition af G.
Eksempel 1
Eksempel 2
13. Komplet todelt graf
EN komplet todelt graf er en todelt graf, hvor hvert toppunkt i det første sæt er forbundet med hvert toppunkt i det andet sæt med nøjagtig en kant.
En komplet todelt graf er en todelt graf, som er komplet.
Complete Bipartite graph = Bipartite graph + Complete graph
Eksempel
Ovenstående graf er kendt som K4,3.
14. Stjernegraf
En stjernegraf er en komplet todelt graf, hvor n-1 toppunkter har grad 1 og et enkelt toppunkt har grad (n -1). Dette ligner nøjagtigt en stjerne, hvor (n - 1) toppunkter er forbundet til et enkelt centralt toppunkt.
En stjernegraf med n toppunkter er angivet med Sn.
Eksempel
I ovenstående eksempel, ud af n toppunkter, er alle (n-1) toppunkter forbundet til et enkelt toppunkt. Derfor er det en stjernegraf.
15 Vægtet graf
En vægtet graf er en graf, hvis kanter er blevet mærket med nogle vægte eller tal.
Længden af en sti i en vægtet graf er summen af vægtene af alle kanterne i stien.
Eksempel
I ovenstående graf, hvis stien er a -> b -> c -> d -> e -> g, så er længden af stien 5 + 4 + 5 + 6 + 5 = 25.
16. Multi-graf
En graf, hvor der er flere kanter mellem et vilkårligt par af hjørner, eller der er kanter fra et hjørne til sig selv (løkke), kaldes en multi-graf .
Eksempel
I ovenstående graf er topsæt B og C forbundet med to kanter. På samme måde er topsæt 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 en plan på en sådan måde, at ingen to kanter af den krydser hinanden undtagen ved et toppunkt, hvortil de falder ind.
Eksempel
Ovenstående graf ser måske ikke ud til at være plan, fordi den har kanter, der krydser hinanden. Men vi kan tegne ovenstående graf om.
De tre plantegninger af ovenstående graf er:
Ovenstående tre grafer består ikke af to kanter, der krydser hinanden, og derfor er alle ovenstående grafer plane.
18. Ikke-plan graf
En graf, der ikke er en plan graf, kaldes en ikke-plan graf. Med andre ord er en graf, der ikke kan tegnes uden i det mindste på et par af dens krydsende kanter, kendt som en ikke-plan graf.
Eksempel
Ovenstående graf er en ikke-plan graf.