Information Technology Reference
In-Depth Information
A
B
A
B
A
B
C
C
D
C
D
D
Abbildung 23.5: Alle Elternpaare sind bei der Moralisierung zu betrachten. Es kann
hilfreich sein, den Graphen in ein anderes Layout zu bringen, um alle einzufügenden
Kanten zu erkennen. Im linken Graphen ist die Kante
A
D
leicht zu übersehen.
Eine äquivalente Darstellung des Graphen (rechts) zeigt die Situation deutlicher.
A
B
A
B
A
B
E
E
C
D
C
C
D
Induzierter Teilgraph (
W
,
E
W
)
mit
W
= {
A
,
B
,
C
,
E
}
Vo l l s t änd i ge r
(Teil-)Graph
Unvollständiger Graph
Abbildung 23.6: Induzierung zweier Teilgraphen aus dem linken Graphen.
wenn sie einen vollständigen Teilgraphen induziert. W heißt zusätzlich
Clique
genau dann,
wenn sie maximal ist, d. h. wenn es nicht möglich ist, einen Knoten zu W hinzuzufügen ohne
die Vollständigkeit zu verletzen.
Wir werden später den Begriff der Clique aus Gründen der besseren Formulie-
rung auf Teilgraphen anwenden. Gemeint ist dann die Knotenmenge dieses Teilgra-
phen.
Beispiel 23.3 (Cliquen)
Die drei Graphen aus Abbildung 23.6 besitzen die folgenden Cli-
quen:
Links:
{
A
,
B
,
C
,
D
}
und
{
B
,
D
,
E
}
Mitte:
{
A
,
B
,
C
}
und
{
B
,
E
}
Rechts:
{
A
,
B
,
C
,
D
}
In einem Baum (z. B. der Graph in Abbildung 23.3 ohne die Kante
(
B
,
C
)
und ohne Kanten-
richtungen) stellt jede Kante eine Clique dar.
Definition 23.32 (Anordnung, Nummerierung)
Sei G
=(
V
,
E
)
ein (beliebiger) Graph
und eine bijektive Funktion mit
:
V
{
1, . . . ,
|
V
|}
,
