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

n Σ i = 1 Grad (V i ) = 2 | E |

Corollary 1

Wenn G = (V, E) ein gerichteter Graph mit Eckpunkten V = {V 1 , V 2 ,… V n } ist, dann

n Σ i = 1 Grad + (V i ) = | E | = n Σ i = 1 Grad - (V i )

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

k | V | = 2 | E |

Corollary 4

Wenn in einem nicht gerichteten Graphen der Grad jedes Scheitelpunkts mindestens k beträgt, dann

k | V | ≤ 2 | E |

| Corollary 5

Wenn in einem nicht gerichteten Graphen der Grad jedes Scheitelpunkts höchstens k beträgt, dann

k | V | ≥ 2 | E |