Database Reference
In-Depth Information
Doch nicht nur fur Triangulationen ist die
maximum cardinality search
wichtig.
Auch im Hinblick auf die Cliquen eines Graphen liefert dieses Verfahren nutzliche
Ordnungen. Jede Knoten-Ordnung induziert namlich eine Cliquen-Ordnung, indem
man sich nach dem maximalen Knoten einer jeden Clique richtet.
Beispiel B.25 (Cliquen-Ordnung)
Der triangulierte Graph in Abbildung B.5
besitzt die folgenden Cliquen und die angegebene, von der Knoten-Ordnung indu-
zierte Cliquen-Ordnung:
Clique
max. Knoten
Knoten-Nr.
Cliquen-Ordnung
{
C, D, B
}
B
(3)
1
{
B, D, E
}
E
(4)
2
{
B, E, A
}
A
(5)
3
{
E, F, G
}
F
(7)
5
{
E,D, G
}
G
(6)
4
{
D, H
}
H
(8)
6
Definition B.26 (Separation in ungerichteten Graphen)
G
sei ein
ungerichteter Graph, und
A
,
B
,
C
⊆
V
seien paarweise disjunkte Teilmengen von
V
.
C
separiert
A
und
B
in
=
V
,
E
G
, geschrieben
A
B
|
C
G
wenn jeder Weg zwischen einem Knoten in
A
und einem Knoten in
B
mindestens
einen Knoten aus
C
enthalt (vgl. Abbildung B.6).
A
C
B
Abbildung B.6 C
separiert
A
und
B
