Chociaż istnieje wiele różnych typów grafów, w zależności od liczby wierzchołków, liczby krawędzi, wzajemnych powiązań i ich ogólnej struktury, niektóre z takich powszechnych typów wykresów są następujące:
1. Wykres zerowy
A wykres zerowy to graf, w którym pomiędzy wierzchołkami nie ma krawędzi. Wykres zerowy nazywany jest także wykresem pustym.
Przykład
Graf zerowy z n wierzchołkami jest oznaczony przez Nn.
2. Trywialny wykres
A banalny wykres to graf, który ma tylko jeden wierzchołek.
Przykład
Na powyższym wykresie jest tylko jeden wierzchołek „v” bez żadnej krawędzi. Dlatego jest to trywialny wykres.
3. Prosty wykres
A prosty wykres jest grafem nieskierowanym z brak krawędzi równoległych I żadnych pętli .
Graf prosty, który ma n wierzchołków, stopień każdego wierzchołka wynosi co najwyżej n -1.Przykład
W powyższym przykładzie Pierwszy wykres nie jest prostym wykresem, ponieważ ma dwie krawędzie pomiędzy wierzchołkami A i B, a także posiada pętlę.
Wykres drugi jest grafem prostym, ponieważ nie zawiera pętli ani krawędzi równoległych.
4. Graf nieskierowany
Jakiś graf nieskierowany to graf, którego krawędzie są nie skierowany .
Przykład
Ponieważ na powyższym grafie nie ma krawędzi skierowanych, jest to graf nieskierowany.
5. Graf skierowany
A Kierowany wykres to wykres, w którym krawędzie są skierowane strzałkami.
Graf skierowany jest również nazywany dwuznaki .
Przykład
Na powyższym wykresie każda krawędź jest skierowana strzałką. Krawędź skierowana ma strzałkę biegnącą od A do B, co oznacza, że A jest powiązane z B, ale B nie jest powiązane z A.
6. Pełny wykres
Graf, w którym każda para wierzchołków jest połączona dokładnie jedną krawędzią, nazywamy grafem kompletny wykres . Zawiera wszystkie możliwe krawędzie.
Kompletny graf z n wierzchołkami zawiera dokładnie nC2 krawędzi i jest reprezentowany przez Kn.
Przykład
W powyższym przykładzie, ponieważ każdy wierzchołek grafu jest połączony ze wszystkimi pozostałymi wierzchołkami dokładnie jedną krawędzią, oba wykresy są grafami pełnymi.
7. Połączony wykres
A połączony wykres to graf, w którym możemy przejść z dowolnego wierzchołka do dowolnego innego wierzchołka. W grafie połączonym pomiędzy każdą parą wierzchołków istnieje co najmniej jedna krawędź lub ścieżka.
Przykład
W powyższym przykładzie możemy przejść z dowolnego wierzchołka do dowolnego innego wierzchołka. Oznacza to, że pomiędzy każdą parą wierzchołków istnieje co najmniej jedna ścieżka, dlatego jest to graf spójny.
8. Odłączony wykres
A odłączony wykres to graf, w którym nie istnieje żadna ścieżka pomiędzy każdą parą wierzchołków.
Przykład
Powyższy wykres składa się z dwóch niezależnych od siebie składowych. Ponieważ nie jest możliwe przejście od wierzchołków jednego komponentu do wierzchołków innych komponentów, jest to graf rozłączony.
9. Regularny wykres
A Zwykły wykres to graf, w którym stopień wszystkich wierzchołków jest taki sam.
Jeśli stopień wszystkich wierzchołków wynosi k, wówczas nazywa się to grafem k-regularnym.
Przykład
W powyższym przykładzie wszystkie wierzchołki mają stopień 2. Dlatego nazywane są 2- Zwykły wykres .
10. Wykres cykliczny
Wykres z „n” wierzchołkami (gdzie n>=3) i „n” krawędziami tworzącymi cykl „n” ze wszystkimi jego krawędziami jest znany jako wykres cyklu .
Wykres zawierający co najmniej jeden cykl nazywa się a wykres cykliczny .
Na wykresie cyklicznym stopień każdego wierzchołka wynosi 2.
Graf cykliczny mający n wierzchołków jest oznaczony przez Cn.
co to jest const w Javie
Przykład 1
W powyższym przykładzie wszystkie wierzchołki mają stopień 2. Zatem wszystkie są grafami cyklicznymi.
Przykład 2
Ponieważ powyższy wykres zawiera dwa cykle, jest to zatem wykres cykliczny.
11. Wykres acykliczny
Graf niezawierający żadnego cyklu nazywamy grafem wykres acykliczny .
Przykład
Ponieważ powyższy graf nie zawiera żadnego cyklu, jest to graf acykliczny.
12. Wykres dwudzielny
A wykres dwudzielny to graf, w którym zbiór wierzchołków można podzielić na dwa zbiory w taki sposób, że krawędzie przechodzą tylko pomiędzy zbiorami, a nie wewnątrz nich.
Graf G (V, E) nazywa się grafem dwudzielnym, jeśli jego zbiór wierzchołków V(G) można rozłożyć na dwa niepuste rozłączne podzbiory V1(G) i V2(G) w taki sposób, że każda krawędź e ∈ E (G) ma ostatnie połączenie w V1(G) i ostatni punkt w V2(G).
Podział V = V1 ∪ V2 jest znany jako dwupodział G.
Przykład 1
Przykład 2
13. Kompletny wykres dwudzielny
A kompletny graf dwudzielny jest grafem dwudzielnym, w którym każdy wierzchołek pierwszego zbioru jest połączony z każdym wierzchołkiem drugiego zbioru dokładnie jedną krawędzią.
Kompletny graf dwudzielny to graf dwudzielny, który jest kompletny.
Complete Bipartite graph = Bipartite graph + Complete graph
Przykład
Powyższy wykres jest znany jako K4,3.
14. Wykres gwiazdowy
Wykres gwiazdowy to kompletny graf dwudzielny, w którym n-1 wierzchołków ma stopień 1, a pojedynczy wierzchołek ma stopień (n -1). To dokładnie wygląda jak gwiazda, w której (n - 1) wierzchołków jest połączonych z jednym centralnym wierzchołkiem.
Graf gwiazdy z n wierzchołkami jest oznaczony przez SN.
Przykład
W powyższym przykładzie spośród n wierzchołków wszystkie (n-1) wierzchołków są połączone z jednym wierzchołkiem. Jest to zatem wykres gwiazdowy.
15 Wykres ważony
Wykres ważony to wykres, którego krawędzie zostały oznaczone pewnymi wagami lub liczbami.
Długość ścieżki na grafie ważonym to suma wag wszystkich krawędzi tej ścieżki.
Przykład
Na powyższym wykresie, jeśli ścieżka to a -> b -> c -> d -> e -> g, wówczas długość ścieżki wynosi 5 + 4 + 5 + 6 + 5 = 25.
16. Multigraf
Graf, w którym istnieje wiele krawędzi pomiędzy dowolną parą wierzchołków lub istnieją krawędzie od wierzchołka do niego samego (pętla), nazywa się grafem multi - wykres .
Przykład
Na powyższym wykresie zbiory wierzchołków B i C są połączone dwiema krawędziami. Podobnie zbiory wierzchołków E i F są połączone 3 krawędziami. Jest to zatem wykres multi.
17. Wykres planarny
A wykres planarny to graf, który możemy narysować na płaszczyźnie w taki sposób, że żadne dwie jego krawędzie nie przecinają się, z wyjątkiem wierzchołka, z którym są incydentne.
Przykład
Powyższy wykres może nie wydawać się planarny, ponieważ ma krawędzie przecinające się. Możemy jednak przerysować powyższy wykres.
Trzy płaskie rysunki powyższego wykresu to:
Powyższe trzy wykresy nie składają się z dwóch przecinających się krawędzi, dlatego wszystkie powyższe wykresy są planarne.
18. Wykres nieplanarny
Wykres, który nie jest grafem planarnym, nazywa się grafem niepłaskim. Innymi słowy, wykres, którego nie można narysować bez przynajmniej pary przecinających się krawędzi, nazywany jest grafem nieplanarnym.
Przykład
Powyższy wykres jest wykresem niepłaskim.