Database Reference
In-Depth Information
Der Verbindungsgraph zu dem Hypergraphen aus Beispiel B.41 ist in Abbildung
B.10(b) zu sehen.
Wie bei den Cliquenbaumen spielt auch bei allgemeinen Hypergraphen die
Baumeigenschaft eine wichtige Rolle fur gute Berechnungseigenschaften.
Definition B.43 (Hyperbaum)
Ein Hypergraph
heißt
azyklisch
oder
Hyperbaum
, wenn es eine (lineare) Anordnung seiner Hyperkanten gibt, die die RIP
(s. Definition B.35) besitzt.
H
=
V
,
E
Bei der Uberprufung der Baumeigenschaft eines Hypergraphen
E
kann man sich auf Anordnungen beschranken, die durch eine Variante des
maximum
cardinality search
entstanden sind:
H
=
V
,
•
Man ordnet einer beliebigen Hyperkante
E
den Index 1 zu und nummeriert
die Knoten in
E
in beliebiger, aufsteigender Reihenfolge.
∈E
•
Als nachste Hyperkante wahlt man nun sukzessive jeweils eine derjenigen Hy-
perkanten aus, die eine Maximalzahl bereits nummerierter Knoten enthalt.
Die noch nicht nummerierten Knoten der neuen Hyperkante werden weiter in
aufsteigender Reihenfolge nummeriert.
Es gilt der folgende Satz von Tarjan und Yannakakis [228]:
Proposition B.44
Ein Hypergraph
ist genau dann ein Hyperbaum,
wenn jede MCS-Nummerierung der Hyperkanten von
H
=
V
,
E
H
die RIP besitzt.
Beispiel B.45 (Hyperbaum)
Wir wenden die
maximum cardinality search
auf
den Hypergraphen aus Beispiel B.41 an und erhalten (z. B.) die folgende Anordnung
der Hyperkanten:
E
1
=
{
A, B, C
}
,
E
2
=
{
B, D, E
}
,
E
3
=
{
D, E
}
,
E
4
=
{
C, E
}
wobei die Knoten dem Alphabet entsprechend geordnet werden: A<B<C<D<
E. Diese Ordnung besitzt nicht die RIP, da
E
4
∩
(
E
1
∪
E
2
∪
E
3
)=
{
C, E
}
in keiner der Hyperkanten
E
1
,
E
2
,
E
3
enthalten ist. Der Hypergraph in Abbildung
B.10(a) ist also kein Hyperbaum.
Aus einem beliebigen Hypergraphen
H
=
V
,
E
kann man durch eine Fill-
gewinnen. Uberdeckend
H
=
E
in-Technik einen uberdeckenden Hyperbaum
V
,
Teilmenge einer Hyperkante
E
∈E
bedeutet, dass jede Hyperkante
E
∈E
ist. Zu
diesem Zweck betrachtet man den
Schnittgraphen (cut graph)
H
s
=
V
,
E
s
von
H
mit
(v, w)
∈E
s
gdw.
∃
E
∈E
mit v, w
∈
E
Zwei Knoten aus V werden im Schnittgraphen
H
s
also genau dann durch eine
(normale) Kante verbunden, wenn es eine Hyperkante von
H
gibt, in der beide
liegen.
