Information Technology Reference
In-Depth Information
A
B
A
B
C
D
E
C
D
E
F
G
F
G
Abbildung 23.2: Die Adjazenzmengen des Knotens
D
für den gerichteten und unge-
richteten Fall sind grau unterlegt. Der geschlossene Pfad
A
D
F
C
stellt einen
Zyklus bzw. einen Kreis dar.
Definition 23.17 (Ungerichtete Kante)
Sei G
=(
V
,
E
)
ein Graph. Zwei Paare
(
A
,
B
)
und
(
B
,
A
)
aus E stellen eine einzige
ungerichtete Kante
zwischen den Knoten A und B
dar, wenn gilt:
(
A
,
B
)
E
(
B
,
A
)
E
Eine solche Kante notieren wir mit A
BoderB
A.
Definition 23.18 (Adjazenzmenge)
Sei G
=(
V
,
E
)
ein Graph. Die Menge der Knoten,
die über eine Kante von einem gegebenem Knoten A erreichbar sind, heißt
Adjazenzmenge
von A:
adj(
A
)={
B
V
| (
A
,
B
)
E
}
Definition 23.19 (Pfad)
Sei G
=(
V
,
E
)
ein Graph. Eine Folge von r paarweise verschie-
denen Knoten
=
A
i
1
,...,
A
i
r
heißt
Pfad
von A
i
nach A
j
,fallsgilt:
•
A
i
1
=
A
i
•
A
i
r
=
A
j
(
A
i
k
,
A
i
k
+1
)
Eoder
(
A
i
k
+1
,
A
i
k
)
E,
1
k
<
r
•
Die symmetrische Formulierung des letzten Punktes erlaubt auch Pfade entgegen die Kan-
tenrichtung, was später eine Rolle spielen wird. Ein Pfad mit ausschließlich ungerichteten
Kanten heißt
ungerichteter Pfad
und wird mit
=
A
i
1
···
A
i
r
notiert, während Pfade mit ausschließlich gerichteten Kanten, die zusätzlich ausschließlich
in Kantenrichtung verlaufen, als
gerichtete Pfade
bezeichnet werden und folgendermaßen
geschrieben werden:
=
A
i
1
···
A
i
r
