Information Technology Reference
In-Depth Information
vier Algorithmen vorstellen, die eine konstruktive Verbindung zwischen Verteilun-
gen und deren Zerlegbarkeit bezüglich eines Graphen herstellen:
Algorithmus 24.1 (Zerlegung durch einen ungerichteten, triangulierten Graphen)
Eingabe:
ungerichteter, triangulierter Graph G
=(
V
,
E
)
Ausgabe:
Zerlegung einer Verteilung p
V
mit G als Unabhängigkeitskarte
1. Bestimme alle Cliquen von G.
2. Bestimme eine Cliquenordnung C
1
,...,
C
r
mit Running Intersection Property .
(Vergleiche Definition 23.39)
3. Bestimme die Mengen S
j
=
C
j
(
C
1
···
C
j
1
)
und R
j
=
C
j
\
S
j
.
4. Gib
a
1
dom
(
A
1
)
:
···
a
n
dom
(
A
n
)
:
p
V
A
i
S
j
=
C
j
C
P
A
i
=
a
i
A
i
=
a
i
A
i
=
a
i
A
i
V
A
i
R
j
zurück.
Beispiel 24.4 (Illustration von Algorithmus 24.1)
Betrachten wir erneut den ungerich-
teten, triangulierten Graphen in Abbildung 24.3. Die folgende Cliquenordnung besitzt die
Running Intersection Property, weshalb wir die folgenden Residual- und Separatormengen
2
ablesen können:
i
i
R
i
S
i
1
{
B
,
C
,
E
,
G
}
B
,
C
,
E
,
G
}
{
A
,
B
,
C
}
{
A
}
{
B
,
C
}
2
{
C
,
F
,
G
}
{
F
}
{
C
,
G
}
3
{
B
,
D
}
{
D
}
{
B
}
4
{
F
,
G
,
H
}
{
H
}
{
F
,
G
}
5
Dies führt dann anhand des Algorithmus 24.1 zu folgender Zerlegungsformel (aus Gründen
der Übersichtlichkeit sparen wir uns hier die Allquantisierung über die jeweiligen Wertebe-
reiche):
p
V
(
A
,
B
,
C
,
D
,
E
,
F
,
G
,
H
)
=
P
(
R
1
|
S
1
)
·
P
(
R
2
|
S
2
)
·
P
(
R
3
|
S
3
)
·
P
(
R
4
|
S
4
)
·
P
(
R
5
|
S
5
)
=
P
(
B
,
C
,
E
,
G
)
·
P
(
A
|
B
,
C
)
·
P
(
F
|
C
,
G
)
·
P
(
D
|
B
)
·
P
(
H
|
F
,
G
)
=
P
(
B
,
C
,
E
,
G
)
1
·
P
(
A
,
B
,
C
)
P
(
B
,
C
)
·
P
(
F
,
C
,
G
)
P
(
C
,
G
)
·
P
(
D
,
B
)
P
(
B
)
·
P
(
H
,
F
,
G
)
P
(
F
,
G
)
=
P
(
C
1
)
1
·
P
(
C
2
)
P
(
S
2
)
·
P
(
C
3
)
P
(
S
3
)
·
P
(
C
4
)
P
(
S
4
)
·
P
(
C
5
)
P
(
S
5
)
2
Siehe Definition 23.41 auf Seite 376.
