Das Kefk Network Wiki befindet sich im Testbetrieb.
D-Separation
Aus Kefk.
D-Separiertheit ist ein Begriff aus der Graphentheorie und beschreibt eine Eigenschaften von Knotenmengen in gerichteten Graphen. Das d ist die Abkürzung für das englische directed, was gerichtet bedeutet. Analog kann man auch die U-Separation definieren, also die Separierung in ungerichteten Graphen.
Definition
Seien X und Y zwei nichtleere disjunkte Knotenmengen, und Z eine beliebige Knotenmenge. Dann heißt X d-separiert von Y gegeben Z, wenn für jeden Pfad von X nach Y gilt, dass er durch Z blockiert ist.
Ein Pfad 
heißt blockiert durch Z falls:
- es gibt ein
, das durch eine eingehende sowie eine ausgehende Kante auf dem Pfad liegt oder
- es gibt ein , das durch zwei ausgehende Kanten auf dem Pfad liegt oder
- es gibt ein
, das durch zwei eingehende Kanten auf dem Pfad liegt und von dem kein Nachfolger in Z enthalten ist.
Algorithmus
Ein effizientes Verfahren, um alle d-separierten Knoten zu finden, ist der Bayes-Ball-Algorithmus.
Anwendungen
Die d-Separation wird etwa bei Bayesschen Netzen benötigt. Dort kann gezeigt werden, dass die Unabhängigkeit von Zufallsvariablen mit der d-Separiertheit der Knoten zusammenhängt.
