Graphentheorie - Grundlegende Eigenschaften
Diagramme verfügen über verschiedene Eigenschaften, die zur Charakterisierung von Diagrammen in Abhängigkeit von ihrer Struktur verwendet werden. Diese Eigenschaften werden in spezifischen Begriffen definiert, die sich auf den Bereich der Graphentheorie beziehen. In diesem Kapitel werden einige grundlegende Eigenschaften erläutert, die allen Diagrammen gemeinsam sind.
Abstand zwischen zwei Eckpunkten
Dies ist die Anzahl der Kanten in einem kürzesten Pfad zwischen Scheitelpunkt U und Scheitelpunkt V. Wenn mehrere Pfade zwei Scheitelpunkte verbinden, wird der kürzeste Pfad als Abstand zwischen den beiden Scheitelpunkten betrachtet.
Notation - d (U, V)
Es können beliebig viele Pfade von einem Scheitelpunkt zum anderen vorhanden sein. Unter diesen müssen Sie nur die kürzeste auswählen.
Example
Schauen Sie sich die folgende Grafik an -
Hier beträgt der Abstand vom Scheitelpunkt 'd' zum Scheitelpunkt 'e' oder einfach 'de' 1, da sich zwischen ihnen eine Kante befindet. Es gibt viele Pfade vom Scheitelpunkt 'd' zum Scheitelpunkt 'e' -
- da, ab, sei
- df, fg, ge
- de (Wird für den Abstand zwischen den Eckpunkten berücksichtigt)
- df, fc, ca, ab, be
- da, ac, cf, fg, ge
Exzentrizität eines Scheitelpunkts
Der maximale Abstand zwischen einem Scheitelpunkt und allen anderen Scheitelpunkten wird als Exzentrizität des Scheitelpunkts betrachtet.
Notation - e (V)
Die Entfernung von einem bestimmten Scheitelpunkt zu allen anderen Scheitelpunkten im Diagramm wird genommen, und unter diesen Abständen ist die Exzentrizität die höchste Entfernung.
Example
In der obigen Grafik beträgt die Exzentrizität von 'a' 3.
Der Abstand von 'a' zu 'b' beträgt 1 ('ab'),
von 'a' bis 'c' ist 1 ('ac'),
von 'a' bis 'd' ist 1 ('ad'),
von 'a' bis 'e' ist 2 ('ab' - 'be') oder ('ad' - 'de'),
von 'a' bis 'f' ist 2 ('ac' - 'cf') oder ('ad' - 'df'),
von 'a' bis 'g' ist 3 ('ac' - 'cf' - 'fg') oder ('ad' - 'df' - 'fg').
Die Exzentrizität ist also 3, was ein Maximum vom Scheitelpunkt 'a' aus dem Abstand zwischen 'ag' ist, der maximal ist.
Mit anderen Worten,
e (b) = 3
e (c) = 3
e (d) = 2
e (e) = 3
e (f) = 3
e (g) = 3
Radius eines verbundenen Graphen
Die minimale Exzentrizität aller Scheitelpunkte wird als Radius des Diagramms G betrachtet. Das Minimum unter allen maximalen Abständen zwischen einem Scheitelpunkt und allen anderen Scheitelpunkten wird als Radius des Diagramms G betrachtet.
Notation - r (G)
Von allen Exzentrizitäten der Eckpunkte in einem Diagramm ist der Radius des verbundenen Diagramms das Minimum aller dieser Exzentrizitäten.
Example
In der obigen Grafik ist r (G) = 2, was die minimale Exzentrizität für 'd' ist.
Durchmesser eines Graphen
Die maximale Exzentrizität aller Scheitelpunkte wird als Durchmesser des Graphen G betrachtet. Das Maximum aller Abstände zwischen einem Scheitelpunkt und allen anderen Scheitelpunkten wird als Durchmesser des Graphen G betrachtet.
Notation − d(G) - Von allen Exzentrizitäten der Eckpunkte in einem Diagramm ist der Durchmesser des verbundenen Diagramms das Maximum aller dieser Exzentrizitäten.
Example
In der obigen Grafik ist d (G) = 3; Das ist die maximale Exzentrizität.
Zentraler Punkt
Wenn die Exzentrizität eines Graphen gleich seinem Radius ist, wird er als Mittelpunkt des Graphen bezeichnet. Wenn
e (V) = r (V),
dann ist 'V' der Mittelpunkt des Graphen 'G'.
Example
Im Beispieldiagramm ist 'd' der Mittelpunkt des Diagramms.
e (d) = r (d) = 2
Center
Die Menge aller Mittelpunkte von 'G' wird als Mittelpunkt des Graphen bezeichnet.
Example
Im Beispieldiagramm ist {'d'} die Mitte des Diagramms.
Umfang
Das number of edges in the longest cycle of ‘G’ wird als Umfang von 'G' bezeichnet.
Example
In der Beispielgrafik beträgt der Umfang 6, was wir aus der längsten Zyklus-Acfgeba oder Acfdeba abgeleitet haben.
Umfang
Die Anzahl der Kanten im kürzesten Zyklus von 'G' wird als Umfang bezeichnet.
Notation: g (G).
Example - Im Beispieldiagramm beträgt der Umfang des Diagramms 4, was wir aus dem kürzesten Zyklus acfda oder dfged oder abeda abgeleitet haben.
Summe der Eckpunkte des Satzes
Wenn G = (V, E) ein nicht gerichteter Graph mit Eckpunkten V = {V 1 , V 2 ,… V n } ist, dann
Corollary 1
Wenn G = (V, E) ein gerichteter Graph mit Eckpunkten V = {V 1 , V 2 ,… V n } ist, dann
Corollary 2
In jedem nicht gerichteten Diagramm ist die Anzahl der Scheitelpunkte mit ungeradem Grad gerade.
Corollary 3
Wenn in einem nicht gerichteten Graphen der Grad jedes Scheitelpunkts k ist, dann
Corollary 4
Wenn in einem nicht gerichteten Graphen der Grad jedes Scheitelpunkts mindestens k beträgt, dann
| Corollary 5
Wenn in einem nicht gerichteten Graphen der Grad jedes Scheitelpunkts höchstens k beträgt, dann