Database Reference
In-Depth Information
5
7
4
3
6
2
1
8
Abbildung B.5
Triangulierter Graph mit nummerierten Knoten
(α), da die Knoten durch den Weg B, A, E, D miteinander
verbunden sind und B, D < A, E sind. Ebenso ist (B, E)
Es ist (B, D)
∈F
∈F
(α). Dies sind die
einzigen beiden Kanten in
(α). Abbildung B.5 zeigt den Fill-in-Graphen, wobei die
Kanten des Fill-ins gestrichelt eingezeichnet sind. Der Fill-in-Graph ist offensichtlich
trianguliert.
F
Selbsttestaufgabe B.22 (Fill-in)
Warum enthalt im obigen Beispiel B.21 die
Menge
F
(α)nichtdieKante(A, D)?
Fill-in und Fill-in-Graph eines ungerichteten Graphen hangen entscheidend von
der gewahlten Ordnung α auf den Knoten ab. Dabei ware eine Ordnung optimal, die
bei einem bereits triangulierten Graphen zu einem leeren Fill-in fuhrt, so dass der
Graph mit seinem Fill-in-Graphen ubereinstimmt. Eine solche Ordnung kann durch
die sog.
maximum cardinality search (Maximalzahl-Suche, MCS)
gefunden werden:
Einem beliebigen Knoten wird die Zahl 1 zugewiesen, und der jeweils nachste Kno-
tenwirdsoausgewahlt, dass er zu der großtmoglichen Zahl bereits nummerierter
Knoten adjazent ist. Gibt es dabei mehrere Moglichkeiten, so wird eine davon aus-
gewahlt.
Selbsttestaufgabe B.23 (maximum cardinality search)
Handelt es sich bei
der Ordnung der Knoten in Abbildung B.5 um eine Ordnung nach dem MCS-
Kriterium (bzgl. des nicht-triangulierten Graphen aus Abbildung B.3)?
Proposition B.24
Sei
ein ungerichteter Graph, und es sei
α
eine
Ordnung auf den Knoten
V
.Ist
α
aus einer MCS entstanden und ist
G
=
V
,
E
G
bereits
trianguliert, so ist
G
(α)=
G
.
Verwendet man also zur Bestimmung einer Ordnung α die MCS, so lasst sich
das obige Triangulationsverfahren auch als Testverfahren benutzen.
