Information Technology Reference
In-Depth Information
Pfade, mit ausschließlich gerichteten Kanten, die aber auch entgegen der Kantenrich-
tung verlaufen dürfen, heißen gemischte Pfade und werden entsprechend der Kanten-
richtungen geschrieben. Im linken Graphen von Abbildung 23.2 gibt es z. B. einen
gemischten Pfad F D G E .
Die Tatsache, dass in einem Graphen G der Knoten A über einen gerichteten
Pfad mit dem Knoten B verbunden ist, notieren wir als: A
G
B . Ist der Pfad unge-
G B abgekürzt.
Ein Graph mit ausschließlich ungerichteten Kanten heißt ungerichteter Graph .Ein
Graph mit ausschließlich gerichteten Kanten heißt gerichteter Graph .Manbeachte,
dass die Pfad-Definition 23.19 nicht ausschließt, dass es eine Kante vom letzten zum
ersten Knoten geben könnte. Ist dies der Fall, so unterscheidet man je nach Art des
Graphen — ungerichtet oder gerichtet — nach Zyklen und Kreisen.
richtet, wird dies mit A
Definition 23.20 (Zyklus) Sei G =( V , E ) ein gerichteter Graph. Ein Pfad
= X 1 ··· X k
mit X k X 1 Eheißt Zyklus .
Definition 23.21 (Kreis) Sei G =( V , E ) ein ungerichteter Graph. Ein Pfad
= X 1 ··· X k
mit X k X 1 Eheißt Kreis .
Der Pfad A D F C ist in Abbildung 23.2 ein Zyklus im gerichteten und eine
Kreis im ungerichteten Graphen.
Definition 23.22 (Baum) Ein ungerichteter Graph, in dem jedes Paar von Knoten mit ge-
nau einem Pfad verbunden ist, heißt Baum .
Definition 23.23 (Minimaler spannender Baum)
Sei G =( V , E ) ein ungerichteter Graph und w eine Funktion, die jeder Kante in E ein
Gewicht zuordnet:
w : E IR
Ein Graph G
=( V , E
) heisst minimaler spannender Baum (engl. minimum spanning
tree ), falls gilt:
G ist ein Baum.
E E
e E w ( e )= min
D. h., es gibt keinen anderen Baum über alle Knoten V, der eine kleinere Kantengewichts-
summe hat. 4
4 Woh l abe r kann e s mehre re Bäume mi t j ewe i l s de r g l e i chen mi n ima l en Kan t engewi ch t s summe geben .
Search WWH ::




Custom Search