Graphentheoretische Grundlagen - Methoden Wissensbasierter Systeme - page 506

B Graphentheoretische Grundlagen

Soweit wir sie fur die Behandlung probabilistischer Netzwerke benotigen, stellen wir
hier die graphentheoretischen Grundlagen vor. Neben den grundlegenden Definitio-
nen von gerichteten und ungerichteten Graphen sind dies insbesondere die Konzepte
moraler und triangulierter Graphen, die sog. running intersection property (fortlau-
fende Schnitteigenschaft) sowie Hypergraphen.

B.1 Graphen und Cliquen

Definition B.1 (gerichteter Graph) Ein gerichteter Graph ist ein Paar G =

V , E ,wobei V eine Menge von Ecken (vertices) oder Knoten (nodes) ist und

E⊆ V × V eine Menge von Knotenpaaren (v, w)ist,den Kanten (edges) von G .

Wir werden im Folgenden stets annehmen, dass die Menge V der Knoten eines
Graphen endlich ist. Weiterhin setzen wir voraus, dass E keine Schlingen enthalt,

d.h., fur alle v .

Wahrend Kanten in in einem ungerichteten Graphen oft als zweielementige
Knotenmengen dargestellt werden, fuhrt die folgende Definition ungerichtete Gra-
phen als Spezialfall gerichteter Graphen ein (wie z.B. auch in [90]), so dass wir fur
viele Konzepte dieselbe Notation fur beide Arten von Graphen verwenden konnen.

∈ V ist (v, v) / ∈E

Definition B.2 (ungerichteter Graph) Ein ungerichteter Graph ist ein gerich-
teter Graph G = V , E , in dem die Relation E symmetrisch ist, d.h., fur alle

v, w ∈ V gilt:

(v, w) ∈E ⇒ (w, v) ∈E

als eine Kante des ungerichteten Graphen auf. 1 In
Abbildungen werden wir die Kanten in einem gerichteten Graphen durch Pfeile und
die Kanten in einem ungerichteten Graphen durch Linien zwischen den beteiligten
Knoten darstellen (vgl. Abbildungen B.1 - B.3). Weiterhin treffen wir folgende Ver-
einbarung: Wenn wir davon sprechen, in einem ungerichteten Graphen eine Kante
zwischen den Knoten v und w einzufugen, so meinen wir damit immer das Hin-
zufugen der Kanten (v, w) und (w, v) zur Kantenmenge; das Entfernen einer Kante
zwischen v und w entspricht dem Entfernen der Kanten (v, w) und (w, v).

Wir fassen also { (v, w), (w, v) }

1 Diese Sichtweise einer Kante eines ungerichteten Graphen als die Kombination von ( v, w ) und
( w, v ) entspricht also in eindeutiger Weise der Darstellung {v, w} einer Kante eines ungerichteten
Graphen als zweielementige Menge. Formal kann man die Kanten ( v, w ) und ( w, v ) mit Hilfe
der Aquivalenzrelation ( v, w ) ∼ ( w, v ) identifizieren.