Information Technology Reference
In-Depth Information
Die letzte Zeile dieser Gleichung zeigt eine alternative Schreibweise der Zerlegung ohne Be-
dingungen (da diese einfach durch ihre Definition ersetzt wurden). Für eine allgemeine Cli-
quenmenge
C
mit RIP gilt dann (in der ausführlichen Schreibweise):
a
1
dom
(
A
1
)
:
···
a
n
dom
(
A
n
)
:
r
j
=1
P
A
i
=
a
i
A
i
C
j
p
V
A
i
=
a
i
=
r
j
=2
P
V
A
i
A
i
=
a
i
A
i
S
j
Der Startindex
2
im Nenner soll die Wahrscheinlichkeit über die formal leere Separatormen-
ge S
1
vermeiden. Die eben gezeigte alternative Zerlegungsformel werden wir bei Verbund-
bäumen nutzen. Sie Separatormengen sind gerade die Schnittmengen der im Verbundbaum
benachbarten Cliquen. Da es in einem ungerichteten Baum mit n Knoten genau n
1
Kan-
ten gibt, erklärt sich auch das „Fehlen“ einer Separatormenge.
Algorithmus 24.2 (Zerlegung durch einen gerichteten, azyklischen Graphen)
Eingabe:
gerichteter, azyklischer Graph G
=(
V
,
E
)
Ausgabe:
Zerlegung einer Verteilung p
V
mit G als Unabhängigkeitskarte
1. Bestimme die Elternmengen
pa
G
(
A
i
)
.
2. Gib
a
1
dom
(
A
1
)
:
···
a
n
dom
(
A
n
)
:
p
V
A
j
=
A
i
V
P
A
i
=
a
i
A
i
=
a
i
A
j
=
a
j
A
i
V
pa
G
(
A
i
)
zurück.
Dieser Algorithmus entspricht im Wesentlichen der Definition 24.8. Im Gegensatz
zur Zerlegung anhand eines ungerichteten Graphen, wo die Cliquen-Potentiale noch
geeignet gefunden werden mussten, ist hier die Festlegung der Faktoren klar. Bei-
spiel 24.3 dient auch hier als Illustration.
Algorithmus 24.3 (Minimale unger. Unabh.karte einer strikt pos. Verteilung)
Eingabe:
Eine strikt positive Verteilung p
V
über einer
Menge V
= {
A
1
,...,
A
n
}
von Attributen.
Minimale ungerichtete Unabhängigkeitskarte G
=(
V
,
E
)
von p
V
.
Ausgabe:
1.
Beginne mit G
=(
V
,
E
)
als vollständig verbundenen Graphen, d. h. E
=
V
V.
2.
Für jede Kante
(
A
,
B
)
Eberechne:
a
dom(
A
)
A
i
=
a
i
=
A
i
=
a
i
p
V
\{
A
}
p
V
V
A
i
V
\{
A
}
A
i
b
dom(
B
)
A
i
=
a
i
=
A
i
=
a
i
p
V
\{
B
}
p
V
V
A
i
V
\{
B
}
A
i
