Bahnen in gerichteten Graphen

1. Bogenfolgen

1. Kette:

In gerichteten Graphen wird eine Folge von Bögen Kette der Länge s genannt, wenn F keinen Bogen zweimal enthält und für jeder Bogen e_i einen seiner Endpunkte mit dem Bogen e_i-1 und den anderen mit e_i+1 gemeinsam hat.

2. Bahn:

Eine Kette heißt Bahn, wenn für der Zielpunkt des Bogens e_i mit dem Startpunkt des Bogens e_i+1 übereinstimmt.

3. Elementare Bahn:

Ketten bzw. Bahnen, die jeden Knoten des Graphen höchstens einmal durchlaufen, sind elementare Ketten bzw. elementare Bahnen.

4. Zyklus:

Eine geschlossene Kette wird Zyklus genannt.

5. Kreis:

Eine geschlossene Bahn, in der jeder Knoten Endpunkt genau zweier Bögen ist, heißt Kreis.

Beispiel

In den folgenden Abbildungen sind Beispiele für die verschiedenen Bogenfolgen dargestellt.

2. Zusammenhängende und stark zusammenhängende Graphen

1. Zusammenhängender Graph:

Ein gerichteter Graph G heißt zusammenhängend, wenn je zwei Knoten von G durch eine Kette verbunden sind.

2. Stark zusammenhngender Graph:

Von einem stark zusammenhängenden Graphen G spricht man, wenn es in G zu je zwei Knoten v,w eine Bahn gibt, die v mit w verbindet.

3. Algorithmus von Dantzig

Es sei G =(V,E,f) ein bewerteter schlichter gerichteter Graph mit f(e)>0 für alle Bögen . Der folgende Algorithmus liefert alle von einem Knoten v₁ von G aus erreichbaren Knoten zusammen mit ihren Entfernungen von v₁:

1. Der Knoten v₁ erhält die Markierung Es sei
2. Die Menge der markierten Knoten sei
3. Ist , dann beende man den Algorithmus.
4. Anderenfalls wähle man einen Bogen e^*=(x^*,y^*) aus, für den t(x^*)+f(e^*) minimal ist. Man markiere e^* und y^*, setze t(y^*)=t(x^*)+f(e^*) sowie und wiederhole b) mit

Sind alle Bögen mit 1 bewertet, dann kann man gemäß des Problemes des kürzesten Weges mit Hilfe der Adjazenzmatrix die Länge einer kürzesten Bahn von einem Knoten v zu einem Knoten w des Graphen finden.
Wird dagegen ein Knoten v von G nicht markiert, dann gibt es keine von v₁ nach v führende Bahn.
Wird v mit t(v) markiert, dann ist t(v) die Länge einer solchen Bahn. Eine kürzeste Bahn von v₁ nach v liegt in dem von allen markierten Knoten und Bögen gebildeten Baum, dem Entfernungsbaum bezüglich

Beispiel

Im Graphen der folgenden Abbildung bilden die grün gezeichneten Bögen einen Entfernungsbaum bezüglich des Knotens

Die Längen der kürzesten Bahnen sind:

von v1 nach v3:		von v1 nach v6:
von v1 nach v7:		von v1 nach v8:
von v1 nach v9:		von v1 nach v14:
von v1 nach v2:		von v1 nach v5:
von v1 nach v10:		von v1 nach v12:
von v1 nach v4:		von v1 nach v13:
von v1 nach v11:

Hinweis: Für den Fall, daß G=(V,E,f) Bögen mit negativen Längen besitzt, gibt es einen modifizierten Algorithmus zur Ermittlung kürzester Bahnen (s. Lit. [5.46]).