Database Reference
In-Depth Information
Definition B.3 ((einfacher) Weg, Zyklus)
Sei
G
=
V
,
E
ein Graph (gerichtet
1) zwischen zwei Knoten v, v
∈
V
oder ungerichtet). Ein
Weg (path)
der Lange n(
≥
ist eine Folge von Knoten
v
0
,v
1
,...,v
n
so dass v = v
0
,v
= v
n
gilt und fur jedes i
ist.
Ein Weg v
0
,v
1
,...,v
n
heißt
einfach
, falls alle Knoten paarweise verschieden
sind (außer evtl. v
0
= v
n
), d.h., falls folgende zwei Bedingungen gelten:
∈{
1,...,n
}
(v
i−1
,v
i
)
∈E
•
v
i
= v
j
fur i
= j und 0
≤
i, j
≤
n
−
1 (keine zwei Kanten des Weges haben
denselben Anfangsknoten)
•
v
i
= v
j
fur i
= j und 1
≤
i, j
≤
n (keine zwei Kanten des Weges haben
denselben Endknoten)
Ein
Zyklus (cycle)
der Lange n ist ein Weg v
0
,v
1
,...,v
n−1
,v
n
mit v
0
= v
n
,d.h.
mit identischem Anfangs- und Endpunkt; fur einen ungerichteten Graphen verlan-
gen wir zusatzlich, dass der Weg mindestens drei verschiedene Knoten enthalt.
2
Definition B.4 (Adjazenz, Nachbar)
Zwei Knoten u, v
∈
V
eines ungerichte-
ten Graphen
heißen
adjazent (adjacent)
oder
benachbart
, wenn sie durch
eine Kante verbunden sind. Die Menge der Nachbarn eines Knoten u ist
G
=
V
,
E
nb
(u):=
{
v
∈
V
|
(u, v)
∈E}
Definition B.5 (azyklisch, DAG)
Ein Graph heißt
azyklisch
, wenn er keinen
Zyklus enthalt. Ein gerichteter, azyklischer Graph wird mit dem Kurzel
DAG (di-
rected acyclic graph)
bezeichnet.
Definition B.6 (Elternknoten, Kindknoten)
Sei
G
=
V
,
E
ein DAG, seien
v, w
. v heißt in
diesem Falle
Kindknoten (child) von
w. Die Menge der Elternknoten eines Knotens
v wird mit
pa
(v) bezeichnet:
∈
V
Knoten. w heißt
Elternknoten (parent) von
v,wenn(w, v)
∈E
pa
(v)=
{
w
∈
V
|
(w, v)
∈E}
Der transitive Abschluss dieser Relationen liefert die Begriffe
Vorfahren
und
Nach-
kommen
:
Definition B.7 (Vorfahren, Nachkommen)
Sei
G
=
V
,
E
ein DAG, seien
v, w
∈
V
Knoten. w heißt
Vorfahr (ancestor) von
v und v heißt
Nachkomme (de-
scendant) von
w,wennesin
einen Weg von w nach v gibt. Fur die Menge der
Vorfahren bzw. Nachkommen eines Knoten v fuhren wir die folgenden Bezeichnun-
gen ein:
G
2
Damit ist sichergestellt, dass in einem ungerichteten Graphen nicht schon eine einzelne unge-
richtete Kante ein Zyklus ist.
