Database Reference
In-Depth Information
A
F
E
B
G
D
C
H
Abbildung B.3
Ungerichteter Graph mit 8 Knoten
verbunden ist, und wenn
C
bzgl. dieser Eigenschaft maximal unter den Teilmengen
von
V
ist, wenn es also keine andere vollstandige Teilmenge von
V
gibt, die
C
echt
enthalt.
Beispiel B.14 (Cliquen)
Abbildung B.3 zeigt einen ungerichteten Graphen mit
Knotenmenge
V
=
{
A, B, C, D, E, F, G, H
}
. Hier gibt es 7 Cliquen:
C
1
=
{
A, B
}
C
2
=
{
B, C
}
C
3
=
{
C, D
}
C
4
=
{
D, H
}
C
5
=
{
D, E, G
}
C
6
=
{
E, F, G
}
C
7
=
{
A, E
}
B.2
Triangulierte Graphen
Definition B.15 (Sehne)
Sei
ein ungerichteter Graph. Eine
Sehne
eines einfachen Weges oder Zyklus' v
0
,v
1
,...,v
n
in
G
=
V
,
E
G
ist eine Kante zwischen zwei
nicht aufeinanderfolgenden Knoten v
i
,v
j
,
|
i
−
j
|
> 1.
Definition B.16 (triangulierter Graph)
Ein ungerichteter Graph heißt
trian-
guliert
, wenn jeder einfache Zyklus der Lange > 3 eine Sehne besitzt.
Beispiel B.17 (Sehne eines Zyklus)
Abbildung B.3 zeigt einen ungerichteten
Graphen. Die Kante
ist eine Sehne des Zyklus E, F,G,D,E der Lange 4.
Dennoch ist dieser Graph nicht trianguliert, denn der Zyklus A, B, C, D, E, A der
Lange 5 besitzt keine Sehne.
{
E, G
}
Selbsttestaufgabe B.18 (triangulierte Graphen)
Entscheiden Sie fur jeden
der beiden Graphen in Abbildung B.4, ob er trianguliert ist.
