Information Technology Reference
In-Depth Information
A
B
C
D
Abbildung 23.4: Moralgraph des durch die Kno-
tenmenge
{
E
,
F
,
G
}
aus Abbildung 23.3 induzier-
ten minimalen Vorfahrgraphen. Die durch Mora-
lisierung erzeugten Kanten sind gestrichelt dar-
gestellt.
E
F
G
J
H
K
L
M
Vo r f ah r en
Nachfahren
Nicht-Nachfahren
{
C
,
E
,
F
,
J
,
K
,
L
,
M
}
{
B
,
D
,
G
,
H
}
A
B
{
C
,
D
,
E
,
F
,
J
,
K
,
L
,
M
}
{
A
,
G
,
H
}
C
{
A
,
B
}
{
E
,
F
,
J
,
K
,
L
,
M
}
{
A
,
B
,
D
,
G
,
H
}
{
B
}
{
F
,
J
,
K
,
L
,
M
}
{
A
,
B
,
C
,
E
,
G
,
H
}
D
E
{
A
,
B
,
C
}
{
A
,
B
,
C
,
D
,
F
,
G
,
H
,
J
,
K
,
L
,
M
}
F
{
A
,
B
,
C
,
D
}
{
J
,
K
,
L
,
M
}
{
A
,
B
,
C
,
D
,
E
,
G
,
H
}
{
K
,
M
}
{
A
,
B
,
C
,
D
,
E
,
F
,
H
,
J
,
L
}
G
H
{
L
}
{
A
,
B
,
C
,
D
,
E
,
F
,
G
,
J
,
K
,
M
}
J
{
A
,
B
,
C
,
D
,
F
}
{
L
}
{
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
,
K
,
M
}
{
A
,
B
,
C
,
D
,
F
,
G
}
{
M
}
{
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
,
J
,
L
}
K
L
{
A
,
B
,
C
,
D
,
F
,
H
,
J
}
{
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
,
J
,
K
,
M
}
M
{
A
,
B
,
C
,
D
,
F
,
G
,
K
}
{
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
,
J
,
K
,
L
}
Tabe l l e 23 . 2 : E i gens cha f t en de s Be i sp i e l gr aphen aus Abb i ldung 23 . 3 .
Beispiel 23.2 (Moralisierter minimaler Vorfahrgraph)
Zuerst betrachten wir den
durch die Knotenmenge
{
E
,
F
,
G
}
induzierten minimalen Vorfahrgraphen des Graphen aus
Abbildung 23.3. Dieser ist in Abbildung 23.4 schwarz dargestellt. Die ignorierten Nachfah-
ren der Knoten der induzierenden Menge sind grau schattiert. Nun soll dieser Graph morali-
siert werden. Dazu sind alle unverbundenen Elternknoten mit einer Kante zu verbinden und
danach die Kantenrichtungen zu löschen. Dies betrifft hier die Eltern
{
C
,
D
}
des Knotens F
und die Eltern
{
A
,
B
}
des Knotens C. Es ist zu beachten, dass bei mehr als zwei Eltern ei-
nes Knotens alle möglichen Elternpaare durch eine Kante zu verbinden sind. Abbildung 23.5
verdeutlicht dies. Hier muss die Kante A
Debenfallseingefügtwerden.
Definition 23.30 (Vollständiger Graph)
Ein ungerichteter Graph G
=(
V
,
E
)
heißt
vollständig
genau dann, wenn jedes Paar (verschiedener) Knoten aus V durch eine Kan-
te verbunden ist.
Definition 23.31 (Vollständige Menge, Clique)
Sei G
=(
V
,
E
)
ein ungerichteter Graph. Eine Menge W
Vheißt
vollständig
genau dann,
