Database Reference
In-Depth Information
(a)
(b)
A
A
B
C
B
C
D
E
D
E
Abbildung B.11
Schnittgraph
H
s
(a) und Fill-in-Graph (b) zum Hypergraphen in Ab-
bildung B.10(a)
H
s
wird nun durch Einfugen von Kanten aufgefullt. Hier-
bei geht man von einer MCS-Ordnung bzw. -Nummerierung der Knoten aus und
verbindet die Menge
Der Schnittgraph
aller “kleineren” Nachbarn eines
jeden Knoten v
j
zu einem vollstandigen Graphen. Sind
C
1
,...,
C
q
die Cliquen des
Fill-in-Graphen von
{
v
i
|
(v
i
,v
j
)
∈E
s
,i < j
}
ein uberdeckender Hyper-
baum zu H.DerHyperbaumH
schließlich bietet eine gute Grundlage fur e
ziente
Berechnungen.
H
s
,soist
H
=
V
,
{
C
1
,...,
C
q
}
Beispiel B.46 ( Uberdeckender Hyperbaum)
Wir setzen die Beispiele B.41
und
B.45
fort
und
gehen
von
der
alphabetischen
Ordnung
der
Kno-
ten
A, B, C, D, E
aus.
Der
Schnittgraph
H
s
von
H
=
{
A, B, C, D, E
}
,
{{
A, B, C
ist in Abbildung B.11(a) zu sehen.
Die kleineren Nachbarn der Knoten sind
}
,
{
B, D, E
}
,
{
C, E
}
,
{
D, E
}}
Knoten
kleinere Nachbarn
A
−−
B
A
C
A, B
D
B
E
B, C, D
Um den Schnittgraphen zu vervollstandigen, muss also noch die Kante (C, D)ein-
gefugt werden (s. Abbildung B.11(b)). Ein uberdeckender Hyperbaum zu
H
ist dann
H
=
V
,
{{
A, B, C
}
,
{
B, C, D, E
}}
.
Selbsttestaufgabe B.47 (uberdeckender Hyperbaum)
Geben Sie eine Ord-
nung der Knoten des Hypergraphen H aus Beispiel B.41, fur die der Schnittgraph
H
s
(s. Abbildung B.11(a)) nicht mehr vervollstandigt werden muss. Wie sieht der
zugehorige uberdeckende Hyperbaum aus?
