Information Technology Reference
In-Depth Information
Der Kreis
B
D
F
H
E
des Graphen in Abbildung 23.7 besitzt zwei Sehnen:
D
E
und
F
E
.OffenbarkönnennurKreisemiteinerLängegrößerdreiSehnen
besitzen.
Durch Sehnen werden große Kreise in mehrere kleinere unterteilt. Es wird sich
später als nützlich erweisen, keine sehnenlosen Kreise mit mehr als drei Knoten zu
haben.
Definition 23.36 (Triangulierter Graph)
Ein ungerichteter Graph heißt
trianguliert
ge-
nau dann, wenn jeder einfache Kreis (d. h. ein Pfad, in dem — abgesehen vom Start- und
Endknoten — jeder Knoten höchstens einmal vorkommt) mit mehr als drei Knoten eine Seh-
ne besitzt.
Es ist zu beachten, dass ein triangulierter Graph nicht zwingend aus Dreiecken
bestehen muss. So ist beispielsweise auch der mittlere Graph in Abbildung 23.6 tri-
anguliert; ein Einfügen der Kante
C
E
ist nicht nötig. Andererseits ist nicht je-
der Graph, der aus Dreiecken besteht notwendigerweise auch trianguliert: Abbil-
dung 23.8 zeigt im oberen Teil eine offensichtlich notwendige Triangulierung. Diese
muss jedoch auch auf die Graphen im unteren Teil angewendet werden. Beide sind
äquivalent und besitzen keine Sehne im Kreis
A
B
E
C
.
Definition 23.37 (Maximum Cardinality Search (MCS))
Sei G
=(
V
,
E
)
ein ungerichteter Graph. Eine durch Maximum Cardinality Search erzeugte
Knotenordnung entsteht wie folgt:
1. Wähle einen beliebigen Startknoten aus V und weise ihm die Ordnung 1 zu.
2. Weise die nächsthöhere Ordnungsnummer einem derjenigen Knoten zu, die mit den
meisten bisher schon nummerierten Knoten benachbart sind.
Offensichtlich ist die MCS nicht eindeutig. In Abbildung 23.9 ist ein Beispiel zu
sehen. Knoten
A
bekommt die Nummer 1 zugewiesen, danach muss Knoten
C
die
Nummer 2 bekommen, da er der einzige Nachbar ist. Für Nummer 3 kommen
D
und
F
infrage, da beide mit je einem schon nummerierten Knoten (eben
C
)verbunden
sind. Ohne Beschränkung der Allgemeinheit entscheiden wir uns für
D
als dritten
Knoten in der Ordnung. Nun bekommt
F
zwingend die Nummer 4 zugewiesen, da
er als einziger Knoten im Graph mit zwei schon nummerierten Knoten (
C
und
D
)
verbunden ist. Mit gleichem Argument weist man Knoten
E
die Nummer 5 zu. Für
Nummer 6 besteht wieder die Wahl zwischen zwei Knoten:
B
und
H
.Setzenwir
(
B
)=6, so folgt
(
H
)=7undschließlich
(
G
)=8.
23.2.2 Verbundgraphen
Das bisherige (ungerichtete) Graphenkonzept beschrieb eine algebraische Struktur,
in der einzelne Elemente (die Knoten) untereinander in Relation
8
standen, was durch
die Kantenmenge modelliert wurde. Wir wollen nun dieses Konzept auf
Mengen von
Knoten
ausweiten und somit sog. Verbund- oder Cluster-Graphen definieren. Da wir
8
Tat sächl i ch hande l t es s i ch um e ine Re lat ion im a lgebra i schen S inne , da di e Kant enmenge
E
eine
Te i lmenge von
V
V
ist.
