Database Reference
In-Depth Information
(a)
(b)
A
A
B
C
B
E
C
D
D
F
E
Abbildung B.1
DAG mit 6 Knoten (a) und ein gerichteter Graph, der kein DAG ist (b)
an
(v)=
}
de
(v)={u ∈
V
| u ist Nachkomme von v}
{
u
∈
V
|
u ist Vorfahre von v
Eine
Vorfahrenmenge (ancestral set)
ist eine Menge
A
⊆
V
, die abgeschlossen ist
bzgl. der Vorfahrenrelation, d.h.
an
(v)
⊆
A
fur alle v
∈
A
.Fur eine Knotenmenge
W
⊆
V
bezeichnet
An
(
W
)=
W
∪
an
(w)
w∈
W
die kleinste Vorfahrenmenge, die
W
enthalt. Weiterhin bezeichne
nd
(v)=
V
)
die Menge aller Knoten, die von v verschieden und auch keine Nachkommen von v
sind (
non-descendants
).
−
(
de
(v)
∪{
v
}
Beispiel B.8 (gerichtete Graphen, DAG)
Abbildung B.1(a) zeigt einen DAG
mit 6 Knoten. Der Graph in Abbildung B.1(b) ist gerichtet, aber kein DAG, da er
den Zyklus B, D, E, C, B enthalt. Fur den Graphen in Abbildung B.1(a) ist
pa
(B)=
{
A
}
und
de
(B)=
{
D, E, F
}
.
Aus einem gerichteten Graphen entsteht auf einfache Weise ein ungerichteter
Graph durch Ignorieren der Richtungen:
Definition B.9 (ungerichteter Graph eines gerichteten Graphen)
Sei G =
V
,
d
G
E
ein gerichteter Graph. Der
zu
G
gehorige (ungerichtete) Graph
ist der
G
=
Graph
V
,
E
mit
d
d
}
Die folgende Definition dient dazu, beim Ubergang von einem gerichteten Gra-
phen zu einem ungerichteten Graphen die Information, die in den Richtungen der
Kanten steckt, nicht vollig aufzugeben. Dabei wird nicht einfach der zu einem DAG
gehorige ungerichtete Graph als Ausgangspunkt genommen, sondern ein modifizier-
ter Graph.
E
=
E
∪{
(w, v)
|
(v, w)
∈E
