Database Reference
In-Depth Information
A
B
C
E
D
F
Abbildung B.2
Moraler Graph zu Abb. B.1(a); die gestrichelte Linie wurde hinzugefugt
Definition B.10 (moraler Graph)
Sei
G
=
V
,
E
ein DAG. Der
morale Graph
(moral graph)
G
m
entsteht aus
G
in zwei Schritten:
•
Sind zwei Knoten u, v Elternknoten eines gemeinsamen Kindknotens, d.h.,
gibt es ein w
pa
(w), und sind diese noch nicht durch eine
Kante verbunden, so fuge eine Kante (u, v)oder(v, u)zu
∈
V
mit u, v
∈
E
hinzu. So entsteht
m
, in dem alle Eltern eines gemeinsamen Kindes
durch eine Kante verbunden sind.
ein (gerichteter) Graph
G
m
gehorige ungerichtete Graph.
•G
m
ist der zu
G
Tatsachlich ware es korrekt und auch angemessen, das englische “moral” mit
“moralisch” zu ubersetzen, also vom “moralischen Graphen” zu sprechen. Denn die
Idee, die der Konstruktion dieses Graphen zugrunde liegt, ist nichts anderes als die-
jenige, eine “Heirat” von Elternpaaren gemeinsamer Kinder - graphentheoretisch(!)
- zu erzwingen. Um einer sachlicheren Darstellung willen ziehen wir es jedoch vor,
das Kunstwort “moraler Graph” zu benutzen. Der kuriose Moralisierungsgedan-
ke darf dennoch als intuitive Beschreibung der Aufgabe dieses Graphen bestehen
bleiben.
Beispiel B.11 (moraler Graph)
Abbildung B.2 zeigt den moralen Graphen zu
Abbildung B.1(a).
Definition B.12 (vollstandiger Graph, leerer Graph)
Ein
ungerichteter
Graph
heißt
vollstandig (complete)
,wennjezweiKnotenaus
V
durch
eine Kante verbunden sind, d.h., wenn gilt (v, w)
G
=
V
,
E
∈E
fur alle v, w
∈
V
.
G
heißt
leerer Graph
, wenn seine Kantenmenge leer ist:
E
=
∅
.
Definition B.13 (Clique)
Sei
G
=
V
,
E
ein ungerichteter Graph. Eine Teilmen-
ge
C
⊆
V
heißt
Clique
von
,wenn
C
eine
maximale vollstandige
Menge ist, d.h.,
wenn jedes Paar verschiedener Knoten aus
C
durch eine Kante aus
G
E
miteinander
