Database Reference
In-Depth Information
Definition B.27 (Zerlegung)
Es sei
ein ungerichteter Graph, und
sei
V
=
A
∪
B
∪
C
mit paarweise disjunkten Teilmengen (
A
,
B
,
C
). Das Tripel
(
A
,
B
,
C
)heißt
Zerlegung (decomposition) von
G
=
V
,
E
G
, wenn gilt:
1.
C
separiert
A
und
B
in G;
2. der durch
C
beschriebene Teilgraph von
G
ist vollstandig.
Sind
A
und
B
beide nichtleer, so wird die Zerlegung (
A
,
B
,
C
)
eigentlich
genannt.
Definition B.28 (Zerlegbarer Graph)
Ein ungerichteter Graph
heißt
zerleg-
bar (decomposable)
, wenn er entweder vollstandig ist, oder wenn er eine eigentliche
Zerlegung (
A
,
B
,
C
) besitzt, fur die jeder der beiden durch
A
∪
C
und
B
∪
C
auf-
gespannten Teilgraphen von
G
G
wieder zerlegbar ist.
Diese rekursive Definition eines zerlegbaren Graphen ist wohldefiniert, da jeder der
genannten Teilgraphen weniger Knoten hat als
.
Zerlegbare Graphen lassen sich leicht charakterisieren:
G
Proposition B.29
Ein ungerichteter Graph
G
ist genau dann zerlegbar, wenn er
trianguliert ist.
Ein Beweis dieses Satzes findet sich z. B. in [45], S. 51.
Auch bei gerichteten Graphen gibt es den Begriff der Separation, hier als
d-
Separation
bezeichnet. Die ursprungliche Definition von Pearl (s. [175], S. 117) baute
explizit auf den Richtungen der Kanten auf. Eine aquivalente Definition fuhrt die d-
Separation auf die Separation im zugehorigen moralen Graphen zuruck und benutzt
daher die Richtungen nur implizit (vgl. [45], S. 72).
Definition B.30 (d-Separation)
Sei
G
d
d
=
V
,
E
ein DAG, seien
A
,
B
,
C
dis-
d
,wenn
C
die beiden Men-
gen
A
und
B
in dem moralen Graphen, der durch die kleinste Vorfahrenmenge
An
(
A
junkte Teilmengen von
V
.
C
d-separiert
A
und
B
in
G
∪
B
∪
C
) aufgespannt wird, separiert.
d
in Abbildung B.7(a).
Beispiel B.31 (d-Separation)
Wir betrachten den DAG
G
Es ist klar, dass A die einelementigen Mengen
{
B
}
und
{
C
}
d-separiert: Die kleinste
Vorfahrenmenge von
selbst, und der entsprechende morale
Graph hat die einfache, in Abbildung B.7(b) gezeigte Form. Hier fuhrt jeder Weg
zwischen B und C uber A.
Die Knotenmenge
{
A, B, C
}
ist
{
A, B, C
}
{
A, D
}
jedoch d-separiert
{
B
}
und
{
C
}
nicht. Die kleinste
Vorfahrenmenge von
ist wieder die Menge selbst. Bei der Moralisie-
rung des Teilgraphen wird jedoch eine Kante zwischen B und C eingefugt, die die
Separationseigenschaft von {A, D} untergrabt (s. Abbildung B.7(c)).
{
A, B, C, D
}
Selbsttestaufgabe B.32 (d-Separation)
Klaren Sie die folgenden beiden Fra-
gen zum DAG in Abbildung B.7(a):
1. d-separiert {B, C} A und D?
2. d-separiert
{
A, E
}
B und C?
