Obwohl es abhängig von der Anzahl der Eckpunkte, der Anzahl der Kanten, der Interkonnektivität und ihrer Gesamtstruktur viele verschiedene Arten von Diagrammen gibt, sind einige dieser gebräuchlichen Diagrammtypen wie folgt:
1. Nulldiagramm
A Nulldiagramm ist ein Graph, in dem es zwischen seinen Eckpunkten keine Kanten gibt. Ein Nullgraph wird auch als leerer Graph bezeichnet.
Beispiel
Ein Nullgraph mit n Ecken wird mit Nn bezeichnet.
2. Trivialer Graph
A triviales Diagramm ist der Graph, der nur einen Knoten hat.
Beispiel
Im obigen Diagramm gibt es nur einen Scheitelpunkt „v“ ohne Kante. Daher handelt es sich um einen trivialen Graphen.
3. Einfaches Diagramm
A einfaches Diagramm ist der ungerichtete Graph mit keine parallelen Kanten Und keine Schleifen .
Ein einfacher Graph mit n Eckpunkten, der Grad jedes Eckpunkts beträgt höchstens n -1.Beispiel
Im obigen Beispiel ist der erste Graph kein einfacher Graph, da er zwei Kanten zwischen den Scheitelpunkten A und B und außerdem eine Schleife hat.
Der zweite Graph ist ein einfacher Graph, da er keine Schleife und keine parallelen Kanten enthält.
4. Ungerichteter Graph
Ein ungerichteter Graph ist ein Graph, dessen Kanten sind nicht gerichtet .
Beispiel
Da es im obigen Diagramm keine gerichteten Kanten gibt, handelt es sich um ein ungerichtetes Diagramm.
5. Gerichteter Graph
A gerichteter Graph ist ein Diagramm, in dem die Kanten sind gerichtet durch Pfeile.
Der gerichtete Graph wird auch als gerichteter Graph bezeichnet Digraphen .
Beispiel
In der obigen Grafik wird jede Kante durch den Pfeil ausgerichtet. Eine gerichtete Kante hat einen Pfeil von A nach B, was bedeutet, dass A mit B in Beziehung steht, B jedoch nicht mit A.
6. Vollständiges Diagramm
Ein Graph, in dem jedes Knotenpaar durch genau eine Kante verbunden ist, heißt vollständige Grafik . Es enthält alle möglichen Kanten.
Ein vollständiger Graph mit n Eckpunkten enthält genau nC2 Kanten und wird durch Kn dargestellt.
Beispiel
Da im obigen Beispiel jeder Scheitelpunkt im Diagramm mit allen verbleibenden Scheitelpunkten durch genau eine Kante verbunden ist, handelt es sich bei beiden Diagrammen um vollständige Diagramme.
7. Verbundener Graph
A verbundener Graph ist ein Graph, in dem wir von jedem Scheitelpunkt zu jedem anderen Scheitelpunkt gelangen können. In einem verbundenen Diagramm existiert zwischen jedem Eckpunktpaar mindestens eine Kante oder ein Pfad.
Beispiel
Im obigen Beispiel können wir von jedem Scheitelpunkt zu jedem anderen Scheitelpunkt übergehen. Das bedeutet, dass es zwischen jedem Eckpunktpaar mindestens einen Pfad gibt, es handelt sich also um einen zusammenhängenden Graphen.
8. Nicht verbundener Graph
A getrenntes Diagramm ist ein Diagramm, in dem zwischen jedem Eckpunktpaar kein Pfad existiert.
Beispiel
Das obige Diagramm besteht aus zwei unabhängigen Komponenten, die nicht miteinander verbunden sind. Da es nicht möglich ist, von den Eckpunkten einer Komponente zu den Eckpunkten anderer Komponenten zu gelangen, handelt es sich um einen nicht zusammenhängenden Graphen.
9. Regelmäßiges Diagramm
A Regelmäßiges Diagramm ist ein Diagramm, in dem der Grad aller Eckpunkte gleich ist.
Wenn der Grad aller Eckpunkte k ist, spricht man von einem k-regulären Graphen.
Beispiel
Im obigen Beispiel haben alle Eckpunkte den Grad 2. Daher werden sie 2- genannt. Regelmäßiges Diagramm .
10. Zyklischer Graph
Ein Graph mit 'n' Eckpunkten (wobei n>=3) und 'n' Kanten, der mit allen seinen Kanten einen Kreis aus 'n' bildet, wird als bezeichnet Zyklusdiagramm .
Ein Graph, der mindestens einen Zyklus enthält, wird als a bezeichnet zyklischer Graph .
Im Zyklusdiagramm beträgt der Grad jedes Scheitelpunkts 2.
Der Zyklusgraph mit n Ecken wird mit Cn bezeichnet.
Wörterbuch c#
Beispiel 1
Im obigen Beispiel haben alle Eckpunkte den Grad 2. Daher handelt es sich bei allen um zyklische Graphen.
Beispiel 2
Da der obige Graph zwei Zyklen enthält, handelt es sich um einen zyklischen Graphen.
11. Azyklischer Graph
Ein Graph, der keinen Zyklus enthält, wird als bezeichnet azyklischer Graph .
Beispiel
Da der obige Graph keinen Zyklus enthält, handelt es sich um einen azyklischen Graphen.
12. Bipartiter Graph
A zweiteiliger Graph ist ein Graph, in dem die Scheitelpunktmenge in zwei Mengen unterteilt werden kann, sodass Kanten nur zwischen Mengen verlaufen, nicht innerhalb dieser.
Ein Graph G (V, E) heißt bipartiter Graph, wenn seine Knotenmenge V(G) in zwei nichtleere disjunkte Teilmengen V1(G) und V2(G) zerlegt werden kann, sodass jede Kante e ∈ E ist (G) hat sein letztes Gelenk in V1(G) und den anderen letzten Punkt in V2(G).
Die Partition V = V1 ∪ V2 wird als Bipartition von G bezeichnet.
Beispiel 1
Beispiel 2
13. Vollständiger bipartiter Graph
A vollständiger zweiteiliger Graph ist ein zweiteiliger Graph, in dem jeder Scheitelpunkt im ersten Satz mit jedem Scheitelpunkt im zweiten Satz durch genau eine Kante verbunden ist.
Ein vollständiger bipartiter Graph ist ein vollständiger bipartiter Graph.
Complete Bipartite graph = Bipartite graph + Complete graph
Beispiel
Der obige Graph ist als K bekannt4,3.
14. Sterndiagramm
Ein Sterngraph ist ein vollständiger zweiteiliger Graph, in dem n-1 Eckpunkte den Grad 1 und ein einzelner Eckpunkt den Grad (n -1) haben. Dies sieht genau wie ein Stern aus, bei dem (n - 1) Scheitelpunkte mit einem einzigen zentralen Scheitelpunkt verbunden sind.
Ein Sterngraph mit n Ecken wird mit S bezeichnetN.
Beispiel
Im obigen Beispiel sind von n Scheitelpunkten alle (n-1) Scheitelpunkte mit einem einzigen Scheitelpunkt verbunden. Es handelt sich also um einen Sterngraphen.
15 Gewichtetes Diagramm
Ein gewichteter Graph ist ein Graph, dessen Kanten mit einigen Gewichten oder Zahlen beschriftet wurden.
Die Länge eines Pfades in einem gewichteten Diagramm ist die Summe der Gewichte aller Kanten im Pfad.
Beispiel
Wenn der Pfad im obigen Diagramm a -> b -> c -> d -> e -> g ist, beträgt die Länge des Pfads 5 + 4 + 5 + 6 + 5 = 25.
16. Multigraph
Ein Graph, in dem es mehrere Kanten zwischen einem beliebigen Scheitelpunktpaar oder Kanten von einem Scheitelpunkt zu sich selbst (Schleife) gibt, wird als a bezeichnet Multi-Graph .
Beispiel
Im obigen Diagramm sind die Scheitelpunktmengen B und C mit zwei Kanten verbunden. Ebenso sind die Scheitelpunktmengen E und F mit drei Kanten verbunden. Daher handelt es sich um einen Multigraphen.
17. Planarer Graph
A planarer Graph ist ein Graph, den wir in einer Ebene so zeichnen können, dass sich keine zwei Kanten davon kreuzen, außer an einem Scheitelpunkt, mit dem sie inzident sind.
Beispiel
Der obige Graph scheint möglicherweise nicht planar zu sein, da sich die Kanten kreuzen. Aber wir können die obige Grafik neu zeichnen.
Die drei Ebenenzeichnungen des obigen Diagramms sind:
Die obigen drei Graphen bestehen nicht aus zwei einander kreuzenden Kanten und daher sind alle obigen Graphen planar.
18. Nichtplanarer Graph
Ein Graph, der kein planarer Graph ist, wird als nichtplanarer Graph bezeichnet. Mit anderen Worten: Ein Graph, der nicht ohne mindestens ein Paar seiner sich kreuzenden Kanten gezeichnet werden kann, wird als nichtplanarer Graph bezeichnet.
Beispiel
Der obige Graph ist ein nichtplanarer Graph.