Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Definitionen zu Graphen




Definitionen

Bearbeiten

Hier werden allgemeine Definitionen bezüglich der Graphen behandelt. Dazu werden immer wieder Beispiele gebracht, die sich auf folgende Graphen beziehen. Dabei gilt je nach Beispiel G=(V,E) entweder für den ungerichteten oder den gerichteten Graphen.

   


Adjazenz

Bearbeiten

Ungerichteter Graph

Bearbeiten

Zwei Knoten   heißen adjazent, falls  .

Hier heißt v heißt auch Nachbar von w.

Beispiel:

  • Knoten 1 und 3 sind adjazent

Gerichteter Graph

Bearbeiten

Zwei Knoten   heißen adjazent, falls   oder  .

Für   heißt w Nachfolger von v und v Vorgänger von w.

Beispiele:

  • Knoten 1 ist Vorgänger zu Knoten 3
  • Knoten 4 ist Nachfolger zu Knoten 6

Inzidenz

Bearbeiten

Ungerichteter Graph

Bearbeiten

Eine Kante   ist inzident zu einem Knoten  , falls   oder  .

Gerichteter Graph

Bearbeiten

Eine Kante   ist inzident zu einem Knoten  , falls   oder  .

Ungerichteter Graph

Bearbeiten

Der Grad (engl. degree) eines Knotens   ist die Anzahl seiner inzidenten Kanten, das heißt:  .

Beispiel:

  • Der Grad von Knoten 4 ist 3

Gerichteter Graph

Bearbeiten

Der Eingangsgrad (engl. in-degree) eines Knotens   ist die Anzahl seiner Vorgänger:  .

Der Ausgangsgrad (engl. out-degree) eines Knotens   ist die Anzahl seiner Nachfolger:  .

Beispiele:

  • Der Eingangsgrad von Knoten 3 ist 2
  • Der Ausgangsgrad von Knoten 3 ist 3

Ungerichteter Graph

Bearbeiten

Ein Weg W ist eine Sequenz von Knoten   mit   für die gilt:  

Beispiel:

  • (1,3,5,6,3,4) ist ein Weg

Gerichteter Graph

Bearbeiten

Ein (gerichteter) Weg W ist eine Sequenz von Knoten  .

Beispiel:

  • (1,3,6,5,5,3,1) ist ein (gerichteter) Weg

Ein Weg W heißt Pfad, falls zusätzlich gilt  . Das heißt, der Weg enthält keine doppelten Knoten. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

  • (1,4,6,5) ist ein Pfad

Ein Weg P heißt Kreis, falls  . Dazu ist ein Kreis K elementar, falls  . Der Kreis enthält also keine doppelten Knoten bis auf den Anfangs- und den Endpunkt. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

  • (1,3,4,6,3,4,1) ist ein Kreis
  • (3,4,6,3) ist ein elementarer Kreis

Die Länge eines Weges ist die Anzahl der durchlaufenen Kanten. Die Länge eines Pfades ist also n-1. Diese Definition gilt sowohl für ungerichtete als auch gerichtete Graphen.

Beispiel:

  • Die Länge von (3,4,6,3,4,1) ist 4
  • Die Länge von (1,3,6) ist 2

Teilgraph

Bearbeiten

Ungerichteter Graph

Bearbeiten

Ein Graph   heißt Teilgraph von G, falls  .

Beispiel:

  • G'=({3,4,6},{{3,4},{4,6}}) ist ein Teilgraph von G

Gerichteter Graph

Bearbeiten

Ein Graph   heißt Teilgraph von G, falls   und  .

Beispiel:

  •   ist ein Teilgraph von  .

Erreichbarkeit

Bearbeiten

Ungerichteter Graph

Bearbeiten

Ein Knoten   heißt erreichbar von einem Knoten  , falls ein Weg   existiert mit   und  .

Beispiele:

  • Knoten 6 ist erreichbar von Knoten 1
  • Knoten 7 ist nicht erreichbar von Knoten 1

Gerichteter Graph

Bearbeiten

Ein Knoten   heißt erreichbar von einem Knoten  , falls ein Weg   existiert mit   und  .

Beispiele:

  • Knoten 6 ist erreichbar von Knoten 1
  • Knoten 5 ist nicht erreichbar von Knoten 2

Zusammenhang

Bearbeiten

Ungerichteter Graph

Bearbeiten

G heißt (einfach) zusammenhängend, falls für alle   gilt, dass w von v erreichbar ist

Ein Teilgraph   von G heißt Zusammenhangskomponente von G, falls G' zusammenhängend ist und kein Teilgraph   von G existert mit  .

Beispiele:

  • G ist nicht zusammenhängend
  • Der Teilgraph   ist eine Zusammenhangskomponente von G
  • Der Teilgraph   ist eine Zusammenhangskomponente von G

Gerichteter Graph

Bearbeiten

G heißt (stark) zusammenhängend, falls für alle   gilt, dass w von v und v von w erreichbar ist.

Ein Teilgraph   von G heißt starke Zusammenhangskomponente von G, falls   stark zusammenhängend ist und kein Teilgraph   von G existiert mit  .

Beispiel:

  • Der Teilgraph   mit   und   ist eine starke Zusammenhangskomponente von  .