imported>Ulanwp: Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert

2026-02-25T09:30:10Z

Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert

Neue Seite

{{SEITENTITEL:d-Separation}}

'''d-Separation''' ist ein Begriff aus der [[Graphentheorie]] und beschreibt eine Eigenschaft von [[Knoten (Graphentheorie)|Knotenmengen]] in [[Gerichteter Graph|gerichteten Graphen]]. Das ''d'' ist die Abkürzung für das englische directed, was gerichtet bedeutet.<ref>{{cite journal |first=Dan |last=Geiger |coauthors=Thomas Verma, [[Judea Pearl]] |date=1990 |title=Identifying independence in Bayesian Networks |journal=Networks |volume=20 |pages=507–534 |url=https://ftp.cs.ucla.edu/pub/stat_ser/r116.pdf |access-date=2011-10-06 |language=en}}</ref> Analog kann man auch die [[u-Separation]] definieren, also die Separation in ungerichteten Graphen.

== Definition ==
Seien <math>X</math> und <math>Y</math> zwei nichtleere [[disjunkt]]e Knotenmengen eines Graphen und <math>Z</math> eine beliebige Knotenmenge. Dann heißt <math>X</math> ''d-separiert'' von <math>Y</math> gegeben <math>Z</math>, wenn für jeden ungerichteten [[Weg (Graphentheorie)|Pfad]] von <math>X</math> nach <math>Y</math> gilt, dass er durch <math>Z</math> blockiert ist.
Ein Pfad heißt blockiert durch <math>Z</math> falls:
* es gibt ein <math> z \in Z </math>, das durch eine eingehende sowie eine ausgehende Kante auf dem Pfad liegt oder
* es gibt ein <math> z \in Z </math>, das durch zwei ausgehende Kanten auf dem Pfad liegt oder
* es gibt ein <math> z \notin Z </math>, das durch zwei eingehende Kanten auf dem Pfad liegt und von dem kein Nachfolger in <math> Z </math> enthalten ist.

== Algorithmus ==
Ein effizientes Verfahren, um alle d-separierten Knoten zu finden, ist der [[Bayes-Ball-Algorithmus]].

== Anwendungen ==
[[Bayessches Netz|Bayessche Netze]] sind Modelle für die [[Gemeinsame Verteilung von Zufallsvariablen|gemeinsame Verteilung]] einer Menge von [[Zufallsvariable]]n.
Sie stellen [[Stochastisch unabhängige Zufallsvariablen|Abhängigkeiten]] durch gerichtete Kanten in einem Graphen dar, wobei die Knoten den Zufallsvariablen entsprechen. Man kann zeigen, dass in Bayesschen Netzen die [[Stochastisch unabhängige Zufallsvariablen|Unabhängigkeit]] von Zufallsvariablen mit der d-Separiertheit der Knoten zusammenhängt.

== Einzelnachweise ==
<references />

{{SORTIERUNG:Dseparation}}
[[Kategorie:Graphentheorie]]

D-Separation - Versionsgeschichte

imported>Ulanwp: Fehlenden Sprachparameter eingefügt; 1 Datumsparameter konvertiert