|
|
|
|
von
Bögen Kette der Länge 
genannt, wenn 
keinen Bogen zweimal enthält
und für 
jeder Bogen 
einen seiner Endpunkte mit dem Bogen
und den anderen mit 
gemeinsam hat.
der
Zielpunkt des Bogens
mit dem Startpunkt des Bogens
übereinstimmt.
| 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 
heißt zusammenhängend,
wenn je zwei Knoten von
durch eine Kette verbunden sind.
2. Stark zusammenhängender Graph: Von einem stark zusammenhängenden
Graphen
spricht man, wenn es in
zu je zwei Knoten 
eine Bahn gibt, die 
mit 
verbindet.
3. Algorithmus von Dantzig
Es sei 
ein bewerteter schlichter gerichteter Graph mit 
für
alle Bögen 
.
Der folgende Algorithmus liefert alle von einem Knoten 
von
aus erreichbaren
Knoten zusammen mit ihren Entfernungen von :
a) Der Knoten
erhält die Markierung 
Es sei 
b) Die Menge der markierten Knoten sei 
c) Ist 
,
dann beende man den Algorithmus.
d) Anderenfalls wähle man einen Bogen 
aus, für den
minimal ist.
Man markiere 
und 
,
setze 
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
zu einem Knoten
des
Graphen finden.
Wird dagegen ein Knoten
von
nicht markiert, dann gibt es keine von
nach
führende Bahn.
Wird
mit 
markiert, dann ist
die Länge einer solchen Bahn.
Eine kürzeste Bahn von
nach
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:
| |||||||||||||||||||||||||||||||||
Hinweis: Für den Fall, daß 
Bögen mit negativen Längen besitzt,
gibt es einen modifizierten Algorithmus zur Ermittlung kürzester Bahnen
(s. Lit. 5.39).
|
|
