Information Technology Reference
In-Depth Information
Beispiel 23.4
Machen wir uns diese Konzepte anhand der Graphen in Abbildung 23.11 klar.
Abbildung 23.12 zeigt alle Residual- und Separatormengen der Cliquen auf. Ebenso finden
sich die per Formel 23.1 ableitbaren u-Separationen.
Einen beliebigen Verbundgraphen eine Baumstruktur zu geben gestaltet sich sehr
einfach, da lediglich hinreichend viele Kanten weggelassen werden müssen. Die Fra-
ge ist nur, ob man immer auch die RIP erhalten kann. Dies ist nicht so, wie man in
Abbildung 23.10 nachvollziehen kann. Zwei Kanten müssen entfernt werden, um ei-
ne Baumstruktur zu erreichen. Allerdings erfüllt keiner der so zu erreichenden Bäu-
me die RIP. Werden beispielsweise die Kanten
CDF
EFH
und
BD
BE
entfernt,
so enthalten die Cliquen
BD
und
BE
beide das Attribut
B
,diesgiltjedochnichtfür
die Cliquen des Pfades, der sie verbindet.
Die Frage, ob es eine strukturelle Eigenschaft eines Verbundgraphen (oder sei-
nes zugrunde liegenden ungerichteten Graphen) gibt, die einen Verbundbaum ga-
rantiert, wurde in [Jensen 1988] positiv beantwortet: Ein ungerichteter Graph
G
hat
einen Verbundbaum genau dann, wenn
G
trianguliert ist. Leider ist die Definition
der Running Intersection Property nicht konstruktiv, d. h. sie liefert zwar ein Kriteri-
um, mit dem man bei einer gegebenen Cliquenordnung entscheiden kann, ob diese
die RIP erfüllt oder nicht. Allerdings liefert sie keinen Algorithmus, mit dem man
eine solche Cliquenordnung finden könnte. Zur Lösung des Problems machen wir
uns folgenden Zusammenhang zunutze: Besitzt ein ungerichteter Graph eine perfek-
te Ordnung und ordnet man seine Cliquen aufsteigend nach der jeweils größten per-
fekten Zahl ihrer Knoten, so erfüllt diese Cliquenordnung die RIP. Die in Tabelle 23.3
überprüfte Cliquenordnung wurde aus der perfekten Ordnung aus Abbildung 23.7
generiert. Tabelle 23.4 illustriert diese Zuweisung.
Wir haben nun das Problem des Findens einer Cliquenordnung auf das Problem
des Findens einer perfekten Knotenordnung reduziert, was auf den ersten Blick we-
nig sinnvoll erscheint, da es mehr Knoten als Cliquen gibt. Ziel ist es also, eine per-
fekte Ordnung auf den Knoten des ungerichteten Graphen zu finden (dies ist für
allgemeine Graphen nicht gesichert). Hier hilft uns folgender Zusammenhang: Die
Knoten eines ungerichteten Graphen besitzen mindestens eine perfekte Ordnung ge-
nau dann, wenn der Graph trianguliert ist.
Als letzter Baustein dieser Kette fehlt noch die Konstruktion einer solchen per-
fekten Ordnung. Hierzu nutzen wir folgende Aussage: Eine durch Maximum Cardi-
nality Search auf einem triangulierten Graphen erzeugte Knotenordnung ist perfekt.
Fassen wir diese Schlusskette noch einmal zusammen:
Cliquenordnung
nach der jeweils
größten perfek-
ten Knotenzahl
erfüllt RIP
Ungerichteter,
triangulierter
Graph
G
=(
V
,
E
)
Durch MCS auf
V
gefundene Knoten-
ordnung ist perfekt
Ve r bundbaum
nach der RIP
aufbauen
23.2.3 Separationen
Ein Ziel graphischer Modelle ist es, möglichst viele der in einer hochdimensiona-
len Wahrscheinlichkeitsverteilung gültigen (bedingten) Unabhängigkeiten in einem
