Information Technology Reference
In-Depth Information
werden. Ab jetzt werden wir unter Pfaden immer gemischte Pfade verstehen, also
solche, in denen man auch entgegen den Kantenrichtungen laufen darf. Es seien
wieder drei disjunkte Teilmengen
X
,
Y
und
Z
der Knotenmenge eines gerichteten
Graphen gegeben. Wir verwenden die gleichen Überlegungen wie bei der obigen Be-
schreibung der u-Separation, nur werden wir das Kriterium für einen blockierenden
Knoten modifizieren. Erneut seien die Mengen
X
und
Y
d-separiert
10
genau dann,
wenn jeder Pfad eines Knotens aus
X
zu einem Knoten in
Y
blockiert ist. Ein Pfad ist
genau dann blockiert, wenn er mindestens einen blockierenden Knoten enthält. Ein
Knoten ist blockierend, falls seine Kantenrichtungen
entlang des Pfades
•
seriell oder divergierend sind und der Knoten selbst in
Z
liegt, oder
• konvergierend sind und weder der Knoten selbst, noch einer seiner Nachfah-
ren in
Z
liegt.
Die vier möglichen Kantenrichtungen an einem Knoten sind wie folgt in zwei Grup-
pen unterteilt:
seriell
seriell
divergierend
konvergierend
Der Typ eines Knotens (also seriell, konvergierend oder divergierend) hängt je-
weils vom konkreten Pfad ab, in dem er sich befindet. In Abbildung 23.15 ist der
Knoten
E
im Pfad
C
E
G
seriell, während er im Pfad
C
E
D
konvergie-
rend und schließlich im Pfad
F
E
G
divergierend ist.
Definition 23.43 (d-Separation, d-Trennung)
Sei G
=(
V
,
E
)
ein gerichteter Graph
und X, Y und Z drei disjunkte Teilmengen von V. X und Y werden in G durch Z ge-
nau dann
d-separiert
,wenneskeinenPfadeinesKnotensinXzueinemKnoteninYgibt,
entlang dem folgende beiden Kriterien erfüllt sind:
1. Jeder Knoten mit konvergierenden Kanten ist in Z oder hat einen Nachfahren in Z.
2. Jeder andere Knoten ist nicht in Z.
Dies wird als
X
G
Y
|
notiert. Ein Pfad, der die beiden obigen Kriterien erfüllt heißt
aktiv
,ansonsten(durchZ)
blockiert
.
Man beachte die beiden äquivalenten aber wechselseitig negierten Definitionen
der d-Separation. Die erste Beschreibung definiert die Blockiertheit eines Pfades und
fordert für eine d-Separaion ausschließlich blockierte Pfade. Die zweite Definition
beschreibt d-Separation als die Abwesenheit jeglicher aktiver Pfade. Wir geben hier
beide Varianten an, da sie beide in der Literatur zu finden sind.
10
Das
d
steht für
d
irected.
