Database Reference
In-Depth Information
(b)
(a)
AB
C
A
B
C
BD
E
CE
D
E
DE
Abbildung B.10
Hypergraph (a) und zugehoriger Verbindungsgraph (b)
B.4
Hypergraphen
Hypergraphen sind verallgemeinerte Graphen, deren Kanten mehr als zwei Knoten
verbinden konnen.
Definition B.40 (Hypergraph, Hyperkante)
Sei
V
eine (endliche) Menge von
Knoten und
E
=
{
E
1
,...,
E
m
}
,
∅
=
E
i
⊆
V
, 1
≤
i
≤
m, eine Menge von Teilmen-
gen
3
von
V
mit
V
=
m
i=1
∪
E
i
. Dann heißt
H
=
V
,
E
Hypergraph
. Die Elemente
von
werden
Hyperkanten
genannt.
Ein Hypergraph heißt
reduziert
, wenn keine Hyperkante echt in einer anderen
Hyperkante enthalten ist.
E
Beispiel B.41 (Hypergraph)
Abbildung
B.10(a)
zeigt
einen
Hypergraphen
mit der Knotenmenge
V
=
{
A, B, C, D, E
}
und den Hyperkanten
E
=
{{
A, B, C
}
,
{
B, D, E
}
,
{
C, E
}
,
{
D, E
}}
. Der Hypergraph ist nicht reduziert, da die
Hyperkante
{
D, E
}
in der Hyperkante
{
B, D, E
}
enthalten ist.
Hyperkanten, die einen nichtleeren Schnitt besitzen, schaffen Verbindungen
zwischen den beteiligten Knoten:
Definition B.42 (Verbindungsgraph)
Sei
H
=
V
,
E
ein Hypergraph. Der
H
zugeordnete
Verbindungsgraph (junction graph)
J(
H
) ist ein ungerichteter Graph
mit den Hyperkanten
als Knoten. Zwei solcher Knoten sind genau dann durch eine
Kante verbunden, wenn die zugehorigen Hyperkanten nichtleeren Schnitt besitzen.
3
Auch die Menge der Hyperkanten wird - wie die Menge der Kanten bei Graphen - mit
E
be-
zeichnet; diese Bezeichnungsweise ist konsistent, da sich ein ungerichteter Graph (ohne isolierte
Knoten) auch als Hypergraph mit
|
E
|
=2fur alle (Hyper)Kanten
E
auffassen lasst.
E
