Database Reference
In-Depth Information
(a)
(b)
A
A
B
C
B
D
C
D
E
Abbildung B.4
Graphen zu Aufgabe B.18
zu triangulieren, wer-
den ihm Kanten hinzugefugt. Diesen Vorgang bzw. die entsprechende Kantenmenge
nennt man
Fill-in
. Zu seiner Konstruktion nimmt man eine lineare Ordnung α auf
der Knotenmenge
V
an.
Um einen beliebigen ungerichteten Graphen
G
=
V
,
E
Definition B.19 (Fill-in, Fill-in-Graph)
Sei
G
=
V
,
E
ein ungerichteter
Graph, und sei α eine lineare Ordnung auf den Knoten von
G
.
•
Der
Fill-in von
G
bzgl.
α ist die Kantenmenge
F
(α), wobei
(v, w)
und es gibt einen Weg zwischen v und
w, der außer v und w nur Knoten enthalt, die bzgl. der Ordnung
αvund w nachgeordnet sind. D.h., ist u
∈F
(α)gdw.(v, w) /
∈E
∈{
v, w
}
ein Knoten auf
diesem Weg, so gilt v<uund w<ubzgl. α.
•
Der
Fill-in-Graph von
G
bezuglich
α ist der Graph
G
(α)=
V
,
E∪F
(α)
Der Fill-in-Graph wird in der Literatur - ein wenig irrefuhrend - als
Elimina-
tionsgraph
bezeichnet. Diese Namensgebung spielt auf ein Triangulationsverfahren
an, das mittels sukzessiver Knotenelimination arbeitet; vgl. z. B. [168].
Proposition B.20
Sei
G =
V
, E
ein ungerichteter Graph, und sei
α
eine Ord-
nung auf den Knoten von
G
. Der Fill-in-Graph von
G
bezuglich
α
,
G
(α)
,isttrian-
guliert.
Beispiel B.21 (Fill-in, Fill-in-Graph)
Wir betrachten wieder den Graphen aus
Abbildung B.3 und legen die folgende Ordnung auf den Knoten fest:
α
:
C<D<B<E<A<G<F<H
In Abbildung B.5 ist diese Ordnung durch eine Nummerierung der Knoten
angezeigt. Wir bestimmen den Fill-in
F
(α):
