Information Technology Reference
In-Depth Information
nur Begriffe einführen, die später von Bedeutung sind, verzichten wir auf eine all-
gemeine Beschreibung dieser Konzepte und verweisen den interessierten Leser bei-
spielsweise auf [Castillo u. a. 1997]. Anstelle beliebige Teilmengen von
V
als neue
Knoten zuzulassen, beschränken wir uns auf die Cliquen eines Graphen.
Definition 23.38 (Verbundgraph, Join-Graph)
Sei G
=
V
,
E
)
ein ungerichteter
Graph und
C = {
C
1
,...,
C
p
}
seine Cliquen. Dann heißt G
=(C
,
E
)
Ve r bundg r aph
oder
Join-Graph
,wenninE
ausschließlich Kanten zwischen nicht-disjunkten Knoten existieren,
d. h. wenn gilt:
(
C
i
,
C
j
)
E
C
i
C
j
=
Folglich können wir aus einem gegebenen ungerichteten Graphen den zugehörigen
Ve r bundg r aphen gene r i e r en : Zue r s t we rden d i e C l i quen b e s t immt und dana c h un -
tereinander verbunden, wenn sie einen nichtleeren Schnitt besitzen. Abbildung 23.10
zeigt ein Beispiel. Der ungerichtete Graph auf der linken Seite besitzt sechs Cliquen:
{
A
,
C
}
,
{
C
,
D
,
F
}
,
{
B
,
D
}
,
{
B
,
E
}
,
{
G
,
F
}
und
{
E
,
F
,
H
}
.DiesebildendieKnotendes
Ve r bundg r aphen au f de r r e c h t en S e i t e . Di e s i e b en Kan t en f o l gen aus den we c hs e l s e i -
tigen Schnittbeziehungen.
Wir werden später Verbundgraphen verwenden, um Erkenntnisse über bestimm-
te Attribute (welche offensichtlich den Elementen von
V
entsprechen werden) allen
anderen Attributen mitzuteilen. Der Algorithmus dieser Evidenzpropagation benö-
tigt jedoch eine Spezialform eines Verbundgraphen. Zum einen muss sichergestellt
sein, dass Informationen auf genau einem Pfad zwischen Cliquen ausgetauscht wer-
den. Zum anderenmüssen Änderungen eines Attributs in einer Clique allen anderen
Cliquen, die dieses Attribut ebenfalls enthalten, mitzuteilen sein. Die erste Forde-
rung lässt sich durch das Verwenden von Verbundbäumen erreichen, also Verbund-
graphen mit Baumstruktur. Da in einem Baum zwischen je zwei Knoten exakt ein
Pfad existiert, ist dieser auch der Pfad für die durchzuführende Evidenzpropagati-
on. Die zweite Forderung lässt sich graphentheoretisch folgendermaßen formulieren:
Besitzen zwei beliebige Cliquen gemeinsame Attribute, so müssen diese Attribute
auch in allen Cliquen des sie verbindenden Pfades enthalten sein. Auf diese Weise
entsteht keine „Lücke“, die die Evidenzpropagation blockieren würde. Diese gefor-
derte Eigenschaft ist als sog. Running Intersection Property bekannt.
Definition 23.39 (Running Intersection Property (RIP))
Sei G
=(
V
,
E
)
ein ungerichteter Graph mit r Cliquen. Eine Ordnung dieser Cliquen hat die
Running Intersection Property, falls es für jedes j
>
1
ein i
<
jgibt,fürdasdieBedingung
C
j
C
1
···
C
j
1
C
i
erfüllt ist.
Bevor wir die Running Intersection Property illustrieren, benötigen wir noch die
Definition für einen Verbundbaum.
Definition 23.40 (Verbundbaum)
Ein Verbundgraph mit Baumstruktur, dessen Cliquen
die Running Intersection Property erfüllen, heißt
Ve r bundbaum
.
