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 .