Information Technology Reference
In-Depth Information
A
B
1
6
i
adj
(
v
i
) {
v
1
,...,
v
i
1
}
{
C
}
=
1
{
A
,
D
,
F
}{
A
}
= {
A
}
2
3
{
C
,
B
,
E
,
F
}{
A
,
C
}
= {
C
}
C
D
E
2
3
5
4
{
G
,
C
,
D
,
E
,
H
}{
A
,
C
,
D
}
= {
C
,
D
}
5
{
B
,
D
,
F
,
H
}{
A
,
C
,
D
,
F
}
= {
D
,
F
}
6
{
D
,
E
}{
A
,
C
,
D
,
F
,
E
}
= {
D
,
E
}
7
{
F
,
E
}{
A
,
C
,
D
,
F
,
E
,
B
}
= {
F
,
E
}
G
F
H
8
{
F
}{
A
,
C
,
D
,
F
,
E
,
B
,
H
}
= {
F
}
8
4
7
=
A
,
C
,
D
,
F
,
E
,
B
,
H
,
G
Abbildung 23.7:
ist eine perfekte Ordnung.
dann nennt man eine
Anordnung
bzw.
Nummerierung
.
Definition 23.33 (Topologische Ordnung)
Sei eine Anordnung auf einem gerichteten,
azyklischen Graphen G
=(
V
,
E
)
,dannheißt
topologische Ordnung
,fallsgilt:
A
V
:
B
descs
(
A
)
:
(
A
)
<
(
B
)
Ein gerichteter, azyklischer Graph kann mehrere topologische Ordnungen haben.
Definition 23.34 (Perfekte Ordnung)
Sei G
=(
V
,
E
)
ein ungerichteter Graph mit
nKnotenund
=
v
1
,...,
v
n
eine totale Ordnung auf V. Dann heißt
perfekt
,wenndie
Mengen
adj
(
v
i
) {
v
1
,...,
v
i
1
}
,
i
=
1, . . . ,
n
vollständig sind.
Ein ungerichteter Graph kann mehrere oder aber auch keine perfekte Knotenord-
nung besitzen.
Abbildung 23.7 zeigt einen ungerichteten Graphen und eine Knotenanordnung
,
die bezüglich des Graphen perfekt ist. Die Tabelle zeigt für jeden Knoten der Ord-
nung das Perfektheitskriterium. Die Schnitte in der rechten Spalte zeigen, dass für
alle Knoten das Kriterium aus Definition 23.34 erfüllt ist: Die zweielementigen Men-
gen entsprechen Kanten, die alle imGraphen enthalten sind; die einelementigen und
die leere Menge sind trivialerweise vollständig.
Definition 23.35 (Sehne eines Kreises (engl.
chord
))
Eine Sehne eines Kreises ist eine
Kante zwischen zwei Knoten des Kreises, die jedoch selbst nicht im Kreis enthalten ist.
