Kurs:Algorithmen und Datenstrukturen (hsrw)/Vorlesung/Definitionen zu Graphen
Definitionen
BearbeitenHier 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
BearbeitenUngerichteter Graph
BearbeitenZwei Knoten heißen adjazent, falls .
Hier heißt v heißt auch Nachbar von w.
Beispiel:
- Knoten 1 und 3 sind adjazent
Gerichteter Graph
BearbeitenZwei 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
BearbeitenUngerichteter Graph
BearbeitenEine Kante ist inzident zu einem Knoten , falls oder .
Gerichteter Graph
BearbeitenEine Kante ist inzident zu einem Knoten , falls oder .
Grad
BearbeitenUngerichteter Graph
BearbeitenDer Grad (engl. degree) eines Knotens ist die Anzahl seiner inzidenten Kanten, das heißt: .
Beispiel:
- Der Grad von Knoten 4 ist 3
Gerichteter Graph
BearbeitenDer 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
Weg
BearbeitenUngerichteter Graph
BearbeitenEin Weg W ist eine Sequenz von Knoten mit für die gilt:
Beispiel:
- (1,3,5,6,3,4) ist ein Weg
Gerichteter Graph
BearbeitenEin (gerichteter) Weg W ist eine Sequenz von Knoten .
Beispiel:
- (1,3,6,5,5,3,1) ist ein (gerichteter) Weg
Pfad
BearbeitenEin 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
Kreis
BearbeitenEin 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
Länge
BearbeitenDie 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
BearbeitenUngerichteter Graph
BearbeitenEin Graph heißt Teilgraph von G, falls .
Beispiel:
- G'=({3,4,6},{{3,4},{4,6}}) ist ein Teilgraph von G
Gerichteter Graph
BearbeitenEin Graph heißt Teilgraph von G, falls und .
Beispiel:
- ist ein Teilgraph von .
Erreichbarkeit
BearbeitenUngerichteter Graph
BearbeitenEin 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
BearbeitenEin 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
BearbeitenUngerichteter Graph
BearbeitenG 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
BearbeitenG 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 .