Embed Size (px)
Citation preview
Diskrete StrukturenMarcel Erne
Leibniz Universitat HannoverFakultat fur Mathematik und Physik
Vorlesungfur
Studierende des Bachelor-StudiengangesAngewandte InformatikSommersemester 2010
3. Graphentheorie
1
Inhaltsverzeichnis
3 Graphentheorie 33.1 Isomorphie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43.2 Eulersche und Hamiltonsche Wege . . . . . . . . . . . . . . . . . 103.3 Baume und Walder . . . . . . . . . . . . . . . . . . . . . . . . . . 163.4 Mehrfacher Zusammenhang . . . . . . . . . . . . . . . . . . . . . 27
2
3 Graphentheorie
In diesem Kapitel widmen wir uns einigen elementaren, aber reizvollen Themenaus der Theorie der (schlichten) Graphen, also der irreflexiven und symmetri-schen Digraphen (X,S). Die Relation S ist hier eindeutig durch die Menge
ES = {xy = {x, y} | xS y}der Kanten (edges) festgelegt, und umgekehrt gibt es zu jeder Teilmenge E von
P2X = {xy | x, y ∈ X,x 6= y} = {Y ⊆X | |Y | = 2},der Menge aller zweielementigen Teilmengen vonX, genau einen Graphen (X,S)mit E = ES , namlich denjenigen mit der irreflexiven und symmetrischen Rela-tion S = {(x, y) | xy ∈ E}. Deshalb werden wir der gangigen Konvention folgen,auch die Paare (X,E) mit E ⊆ P2X Graphen zu nennen.
Wie der Name schon sagt, lassen sich zumindest alle endlichen Graphen leichtgraphisch veranschaulichen, indem man die Ecken oder Knoten (vertices), alsodie Elemente der Grundmenge X, durch Punkte oder kleine Kreise in der Ebe-ne darstellt und je zwei solche durch eine Linie (Kante) verbindet, wenn dieentsprechenden Ecken des Graphen eine Kante xy bilden. Man sagt in die-sem Fall: x und y inzidieren mit der Kante xy, oder x und y sind adjazent(die deutsche Ubersetzung “benachbart” vermeiden wir, um Verwechslungenmit dem gleichlautenden ordnungstheoretischen Begriff auszuschließen). Im FallX = {x1, ..., xm} ist die zugehorige (symmetrische!) Inzidenz- oder Adjazenz-matrix A = (aij) ∈ {0, 1}m×m gegeben durch
aij = 1 ⇔ xixj ∈ E.
Beachten Sie, dass in der Graphentheorie die gezeichneten Darstellungen eineandere Bedeutung haben als in der Ordnungstheorie: Wahrend dort nur aufstei-gende Kanten vorkommen und stets als von unten nach oben gerichtet angese-hen werden, haben Kanten in der Graphentheorie keine Orientierung, konnenalso stets “in beiden Richtungen (und auch waagerecht) durchlaufen” werden.Trotzdem bestehen enge Verbindungen zwischen beiden Theorien: Indem manPfeilspitzen weglaßt, also die entsprechende Relation symmetrisiert, erhalt man
(1) zu jeder geordneten Menge (X,v)(2) den Vergleichbarkeitsgraphen (X,@s) mit x@s y ⇔ x @ y oder y @ x,(3) den Unvergleichbarkeitsgraphen (X,vcs) mit xvcs y ⇔ x 6v y und y 6v x,(4) den Nachbarschaftsgraphen (X,@∨s) mit x @∨s y ⇔ x@∨y oder y@∨x.
Beispiel 3.1 Die geordnete Menge der Teiler von 12 und ihre Graphen
s1s3s6 s2 s4s12
��
��
JJ]JJ]JJ]
JJ]JJ 6
6���*
���
������
(1)
c1c3c6 c2 c4c12
JJ
JJ
JJ
JJJJ���
���
�����
(2)
c1c3c6 c2 c4c12
���
(3)
c1c3c6 c2 c4c12
JJ
JJ
JJ
(4)
3
3.1 Isomorphie
Von essentieller Bedeutung in der Graphentheorie (und uberhaupt in allen struk-turellen Untersuchungen) ist die Moglichkeit zu entscheiden, wann zwei Struk-turen “im wesentlichen gleich” sind, d.h. durch geeignete Umbenennung ihrerElemente auseinander hervorgehen. Hierzu braucht man den Begriff der Isomor-phie (Gleichgestaltigkeit), den wir in Kapitel 1 schon kennengelernt haben.
Es seien zwei Digraphen (X,R) und (X ′, R′) gegeben. Dann heißt eine Ab-bildung ϕ : X −→X ′
• inzidenz-erhaltend, falls xR y ⇒ ϕ(x)R′ ϕ(y)
• inzidenz-reflektierend, falls xR y ⇐ ϕ(x)R′ ϕ(y)
• Quasi-Einbettung, falls xR y ⇔ ϕ(x)R′ ϕ(y)
fur alle x, y ∈ X gilt. Eine Einbettung ist eine injektive Quasi-Einbettung, undein Isomorphismus eine bijektive Einbettung. Entsprechend ist ein Isomorphis-mus zwischen Graphen (X,E) und (X ′, E′) eine Bijektion ϕ :X −→X ′ mit
xy ∈ E ⇔ ϕ(x)ϕ(y) ∈ E′.
Die Bezeichnungen
ϕ+(R) = {(ϕ(x), ϕ(y)) | xR y} und ϕ−(R′) = {(x, y) ∈ X×X | ϕ(x)R′ϕ(y)}erlauben folgende kurze Charakterisierungen der obigen Eigenschaften:
ϕ ist inzidenz-erhaltend ⇔ R ⊆ ϕ−(R′) ⇔ ϕ+(R) ⊆ R′ϕ ist inzidenz-reflektierend ⇔ R ⊇ ϕ−(R′)ϕ ist eine Quasi-Einbettung ⇔ R = ϕ−(R′)ϕ ist eine Einbettung ⇔ R = ϕ−(R′) und ϕ ist injektivϕ ist ein Isomorphismus ⇔ R = ϕ−(R′) und ϕ ist bijektiv.
Beispiel 3.2 Zwei nicht-isomorphe geordnete MengenWir betrachten die Menge X = {1, 2, 3, 6}, einmal mit der Teilbarkeitsrelation| und einmal mit der gewohnlichen linearen Ordnung ≤; so erhalten wir zweigeordnete Mengen G = (X, |) und G′ = (X,≤). Die Identitat idX ist dann
– inzidenz-erhaltend, aber nicht -reflektierend als Abbildung von G nach G′,
– inzidenz-reflektierend, aber nicht -erhaltend als Abbildung von G′ nach G,
denn es gilt x |y ⇒ x ≤ y fur beliebige naturliche Zahlen x, y, wahrend dieUmkehrung x ≤ y ⇒ x |y fur x = 2 und y = 3 falsch ist.
c1
c3 c6
c2
JJ
JJG
c1c2c3c6
����:
����1
PPPPq
PPPqG′
Beachten Sie, dass es keine inzidenz-erhaltende Bijektion zwischen den bei-den Diagrammen (aufgefaßt als Nachbarschaftsgraphen) gibt!
4
Ein Graph T ist Teilgraph eines Graphen G, wenn sowohl seine Eckenmengeals auch seine Kantenmenge in der von G enthalten ist. Das bedeutet nichtsanderes, als dass die Inklusionsabbildung von T in G (die jede Ecke auf sichselbst abbildet) die Inzidenz erhalt. Ist sie sogar eine Einbettung, so sprichtman von einem induzierten (Teil-)Graphen. Analog bildet man fur Digraphen(X,R) und Teilmengen Y ⊆ X die von R auf Y induzierte Relation
R|Y = R ∩ (Y ×Y )
und nennt G |Y = (Y,R|Y ) einen induzierten Digraphen. Fur einen GraphenG = (X,E) und eine Eckenmenge Y ⊆ X wird der auf X \ Y induzierte ”Rest-graph” mit G−Y bezeichnet. Entsprechend bezeichnet man fur eine Kanten-menge K ⊆ E den Graphen (X,E \K) mit G−K.
Beispiel 3.3 Einige Teilgraphen des vollstandigen Graphen mit 5 Ecken
cc ccc
CC
��
���Z
ZZ�� QQ
���
BBB cc ccc���ZZZ�� QQ
���
BBB
(a)cc ccCC
��
���ZZZ
(b)cc ccCC
��
���
(c)c cc���
BBB
(d)
c c(e)cc ccc
CC
��
���ZZZ�� QQ
(f)
(a) Gleiche Eckenmenge, nicht induziert.(b) Verschiedene Eckenmenge, induziert.(c) Teilgraph, verschiedene Eckenmenge, nicht induziert.(d) eingebettet in (a), (b), (c), aber kein Teilgraph von (a), (b) oder (c).(e) Restgraph nach Entfernen der Knoten aus (d).(f) Restgraph nach Entfernen der Kanten aus (d).
Viele wichtige Eigenschaften von Graphen lassen sich durch Existenz oderAusschluss bestimmter Teilgraphen charakterisieren. Spezielle induzierte Teil-graphen sind die sogenannten n-Ecke. Das sind die induzierten Teilgraphen mitn Ecken, die einen Zykel bilden. Ein Nachbarschaftsgraph ist stets “dreiecks-frei”, d.h. er enthalt keine Dreiecke als Teilgraphen. Kein Vergleichbarkeitsgraphenthalt ein induziertes n-Eck mit einer ungeraden Kantenzahl n > 3. (Warum?)
Im Folgenden darf jeweils das Wort “Graph” durch “Digraph” ersetzt wer-den. Zwei Graphen G und G′ heißen isomorph, in Zeichen G ' G′, falls einIsomorphismus zwischen ihnen existiert. Dies liefert ein Aquivalenzrelation aufjeder Menge von Graphen; denn die Verknupfung zweier Isomorphismen unddie zu einem Isomorphismus inverse Abbildung sind wieder Isomorphismen. DieIsomorphieklassen oder speziell ausgewahlte Vertreter dieser Klassen nennt manauch Isomorphietypen.
Unter einer Symmetrie oder einem Automorphismus eines Graphen G vestehtman einen Isomorphismus zwischen G und sich selbst. Jeder Graph besitzt einentrivialen Automorphismus, namlich die Identitat idX . Die Automorphismen ei-nes festen Graphen G bilden aus dem gleichen Grund wie oben eine Gruppe,die Symmetriegruppe S(G). Offenbar besitzt ein Graph G = (X,E) stets genaudie gleichen Symmetrien wir der komplementare Graph
G = (X,P2X \ E).
5
Da die Summe der beiden Kantenzahlen von G und G bei m Ecken m(m−1)/2ergibt, kann ein Graph nur dann zu seinem Komplement isomorph sein, wennseine Kantenzahl m(m−1)/4 betragt; das ist naturlich nur dann moglich, wennm(m− 1)/2 gerade ist, also z.B. nicht fur m = 10.
Bei der strukturellen Untersuchung eines Graphen G interessieren natur-gemaß zwei Zahlen:
(1) die Anzahl a(G) der Automorphismen (Symmetrien) von G,
(2) die Anzahl i(G) der zu G isomorphen Graphen mit gleicher Eckenmenge.
Nach Satz 1.12 kann man jede dieser beiden Zahlen sofort aus der anderenberechnen:
Satz 3.4 Fur jeden endlichen (Di-)Graphen G mit m Ecken gilt
m! = a(G)i(G).
Wieviele Graphen gibt es auf einer festen Menge von m Ecken? Genau soviele, wie es Teilmengen von P2m gibt, also
212 m(m−1).
Eine erheblich schwierigere Frage ist, wieviele Isomorphietypen von Graphen mitm Ecken es gibt. Wir konnen diese Anzahl g(m) hier nicht allgemein berechnen,notieren aber die ersten Werte:
m 1 2 3 4 5 6g(m) 1 2 4 11 34 156
Fur m = 1, 2, 3 sieht man das sofort, und fur m = 4 und 5 stellen wir in Kurzeeine komplette Liste der Isomorphietypen auf.
Aufgrund von Satz 3.4 gilt allgemein
212 m(m−1)/m! ≤ g(m) ≤ 2
12 m(m−1),
und obwohl m! schnell zu riesigen Zahlen anwachst, sind diese im Verhaltnis zuden Zahlen 2m(m−1)/2 aller Graphen mit m Ecken doch verschwindend klein:
log2(m!) =∑m
k=1 log2(k) ≤ m log2(m)
212 m2(1− 1
m−2 log2 m
m ) ≤ 212 m(m−1)/m! ≤ g(m) ≤ 2
12 m2(1− 1
m ),
log2 g(m) ≈ 12m
2(1− 1m ), und 2 log2 m
m geht ebenso wie 1m gegen 0.
Zwei endliche Graphen sind genau dann zueinander isomorph, wenn sie eineubereinstimmende graphische Darstellung (eventuell mit unterschiedlicher Be-schriftung der Knoten) besitzen. Es ist aber keineswegs immer einfach, von zweiGraphen anhand gegebener Zeichnungen festzustellen, ob sie isomorph sind –denn ein Graph kann sehr verschieden aussehende Darstellungen besitzen.
Beispiel 3.5 Isomorph oder nicht?Von den nachfolgend skizzierten sechs Graphen mit jeweils 10 Knoten sind keinezwei in einer Reihe zueinander isomorph, wahrend je zwei Diagramme in einerSpalte erstaunlicherweise den gleichen Graphen darstellen!
6
cc cccccccc���Z
ZZ���
BBB
BBBB
����
���
QQQ
P �
A�cc cccccccc
BB
��
���
BBB
BBBB
����
���
QQQ
P �
A�cc cccccccc
BB
��
BBBB
����
���
QQQ
P �
A�
c cc cc cc ccc
AAA
���
���
AAA
"""b
bb
"""
bbb
"" bb c cc cc cc ccc
AAA
���
���
AAA"
""b
bb
"" bb c cc cc cc cAAA
���
���
AAAcc
""
""TT TTT
Die beiden Bilder in der ersten Spalte zeigen den Petersen-Graph (P2M,E) mit{x, y} ∈ E ⇔ x ∩ y = ∅ fur eine funfelementige Menge M . Hier ist P2M dieEckenmenge, nicht die Kantenmenge!
Einer von mehreren Isomorphismen zwischen den beiden Petersen-Graphenin Beispiel 3.5 klappt die waagerechte Kante des Drudenfußes nach oben undvertauscht seine beiden “Fußpunkte”. Bei den beiden mittleren Graphen mussman nur die obere waagerechte Kante verschieben. Im dritten Fall (rechts) bildetman das Außenfunfeck im oberen Graphen auf das linke und das Innenfunfeckauf das rechte im unteren Graphen ab (oder umgekehrt).
Sehr muhsam kann der Nachweis werden, dass zwei gegebene Graphen nichtisomorph sind, denn ohne schlaue Ideen musste man bei m Ecken im Prinzip m!Bijektionen testen. Glucklicherweise gibt es aber eine Vielzahl von sogenanntenInvarianten, die bei Isomorphie ubertragen werden. Erweist sich eine dieserInvarianten fur zwei vorgegebene Graphen als verschieden, so ist man sicher, dassdiese nicht isomorph sein konnen – ohne eine einzige Bijektion auszuprobieren!
Die zwei offensichtlichsten Invarianten sind die Eckenzahl und die Kanten-zahl; denn ein Isomorphismus ϕ zwischen zwei Graphen (X,E) und (X ′, E′)liefert nicht nur eine Bijektion zwischen den Ecken, sondern wegen ϕ+(E) = E′
auch eine zwischen den Kanten. Die Komponentenzahl ist eine weitere Invarian-te, da ein Isomorphismus ϕ jeden Weg zwischen x und y auf einen Weg zwischenϕ(x) und ϕ(y) abbildet. Daß diese Zahlen noch nicht sehr weit helfen, zeigendie Graphen in 3.5 (alle haben 10 Ecken, 15 Kanten und eine Komponente).
Eine sehr viel feinere Invariante liefert die sogenannte Gradfolge. Die Zahlder zu einer Ecke x in einem Graphen G adjazenten Ecken nennt man Gradoder Valenz von x und bezeichnet sie mit d(x) oder genauer mit dG(x). Beieiner Ecke x eines Digraphen (X,R) unterscheidet man zwischen der positivenValenz (Anzahl der “hinauslaufenden Pfeile”) d+(x) = |{y : xR y}| und dernegativen Valenz (Anzahl der “hineinlaufenden Pfeile”) d−(x) = |{y : yR x}|.
Die Gradfolge eines endlichen Graphen ist, wie der Name sagt, die Folge dereinzelnen Eckengrade (eventuell mit Wiederholungen), meist in aufsteigenderReihenfolge. Da Isomorphismen die Adjazenz ubertragen, mussen isomorpheGraphen identische Gradfolgen haben. Bei weniger als 5 Ecken kann man anhandder Gradfolgen entscheiden, ob zwei Graphen isomorph sind oder nicht. Dienachste Seite zeigt alle Isomorphietypen von Graphen mit 4 oder 5 Ecken.
7
cc cc 00000
24
cc cc��@@ 6
3333
cc cc 10011
4
cc cc��@@ 5
2233
cc cc 20112
2
cc cc��@@ 4
1223
cc cc 21111
8
cc cc��@@ 4
2222
cc cc@@ 3
02226
cc cc�� 3
1113
cc cc 31122 2
Kantenzahl
Gradfolge
Automorphismen
cc ccc
0
00000120
LLL
cc ccc
CC
��
���Z
ZZ�� QQ
���
BBB
10
44444
cc ccc
��1
0001112
LLL
PPPPPPP
cc ccc
CC
��
���Z
ZZQQ
���
BBB
9
33444
cc ccc��
��2
011118
cc ccc
CC���Z
ZZQQ
���
BBB
8
33334
����
cc ccc
�� QQ2
001124
cc ccc
CC
��
���ZZZ���
BBB
8
23344!!!!!!!
���
BBB
cc ccc��
�� QQ3
011222
cc ccc
CC���Z
ZZ���
BBB
7
22334
���
BBB
aaaaaaaa
cc ccc
�� QQ3
111124
cc ccc
CC
��
���Z
ZZ���
BBB
7
23333!!!!!!!!
aaaaaaaa
cc ccc
�� QQ3
0022212
cc ccc
CC
��
���ZZZ���
BBB
7
22244
���
BBB
cc ccc
���
3
011136
cc ccc
CC
��
���ZZZBBB
7
13334!!!!!!!
���
BBB
cc ccc��
�� QQ4
112222
cc ccc
CC���Z
ZZ���
BBB
6
22233
BBBB
cc ccc
��
ZZZ 4
022228
cc ccc
CC���
���
BBB
6
22224
AAA
``````````````
cc ccc
��
��
QQ4
012232
cc ccc
CC���Z
ZZ���
BBB
6
12234
AAA
���
PPPPPPPPP
cc ccc
���
�� 4
111232
cc ccc
CC���ZZZBBB
6
12333!!!!!!!!
���
cc ccc
�� QQ4
1122212
cc ccc
CC
��
���ZZZ���
BBB
6
22233
���
cc ccc
���
BBB
4
1111424
cc ccc
CC
��
���Z
ZZ 6
03333
cc ccc
CC
��
�� QQ5
22222 10cc ccc
CC
��
�� QQ5
11233 2cc ccc
CC
��
QQ5
12223 2cc ccc���Z
ZZ��
���
BBB
5
12223cc ccc
CC
��
��� 5
02233 4cc cccZZZ�� QQ
���
BBB
5
11224
8
In den beiden Diagrammen ist jeweils ein Paar komplementarer Graphenzu einem “Dominostein” verbunden. Dazu haben wir Kantenzahl, Gradfolgeund die Anzahl a der Symmetrien (Automorphismen) notiert. Im unterenDiagramm der funfeckigen Graphen bedeuten die Verbindungskanten zwischenden einzelnen Dominosteinen, dass die jeweilige obere Halfte des hoheren Stei-nes in die des tieferen einbettbar ist, wahrend es sich bei den unteren (kom-plementaren) Halften naturlich gerade umgekehrt verhalt. Nur der viereckigeGraph in der rechten oberen Ecke und die beiden funfeckigen Graphen in derlinken unteren Ecke sind zu ihrem eigenen Komplement isomorph!
Aus unserer Liste der Graphen mit 5 Ecken entnehmen wir, dass auch dieGradfolgen nicht ausreichen, um nicht-isomorphe Graphen stets zu unterschei-den: Der vorletzte Dominostein in der Liste zeigt zwei nicht-isomorphe, zusam-menhangende und zueinander komplementare Graphen mit 5 Ecken und gleicherGradfolge. Die einzigen weiteren Beispiele von Gradfolgen, zu denen zwei nicht-isomorphe Graphen mit 5 Ecken gehoren, sind (1, 1, 2, 2, 2) in der drittletztenZeile des Diagramms und (2, 2, 2, 3, 3) in der vorletzten Zeile des Diagramms.
Weitere Invarianten sind die Vieleckfolgen (z1, ..., zm), wobei zn die Anzahlder n-Ecke des gegebenen Graphen ist. Speziell ist z1 die Zahl der Ecken, z2die der Kanten und z3 die der Dreiecke. Auch hierin unterscheiden sich die zweikomplementaren Graphen im mittleren Dominostein der untersten Reihe: DieVielecksfolgen lauten (5, 5, 0, 1, 0) und (5, 5, 1, 0, 0), da der linke Graph ein Vier-eck, aber kein Dreieck enthalt, wahrend es bei dem rechten gerade umgekehrtist. An der Anzahl der Vierecke kann man auch die Nicht-Isomorphie der dreioberen Graphen auf Seite 7 (mit gleichvielen Ecken, Kanten und konstanterGradfolge (3,3,...)!) ablesen.
Ein Graph ohne nicht-triviale Symmetrien heißt asymmetrisch oder starr.Gibt es uberhaupt solche Graphen? Nach Definition ist jeder einpunktige Graphtrivialerweise starr, aber die Listen der Graphen mit 4 oder 5 Ecken halten ei-ne weitere kleine Uberraschung bereit: Außer den einpunktigen Graphen gibtkeinen einzigen starren Graphen mit weniger als 6 Ecken. Darf man darausschließen, dass starre Graphen eine Raritat sind? Nein, im Gegenteil! Mit Me-thoden, die wir hier nicht erlautern konnen, laßt sich zeigen, dass der Anteil derstarren Graphen mit m Ecken bei wachsendem m sogar gegen 1 geht, also “fastalle” Graphen starr sind – getreu dem Motto von Donald Knuth:
Don’t trust in small numbers!
Beispiel 3.6 Ein starrer Graph
cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cccc cc
9
3.2 Eulersche und Hamiltonsche Wege
Als alteste Aufgabe der Graphentheorie gilt das von Leonhard Euler stammende
Konigsberger Bruckenproblem
Gibt es einen Rundweg durch die Stadt Konigsberg, bei dem man jede Bruckegenau einmal besucht? (“ Uber sieben Brucken musst du geh’n ...”)
��
����
A
B
C
D
(1)
���
@@@BB
��
BB��
��BB
��BB
cAcBcCcD(2)
���
@@@BB
��
BB��
��BB
��BB
cAcBcCcDrrrr
(3)
Bei graphentheoretischer Reduktion dieses Problems “auf das Wesentliche” bie-ten sich die vier Stadtteile A,B,C,D als Knoten und die sieben Brucken alsKanten an. Es ergibt sich das vereinfachte Diagramm (2). Allerdings haben wires hier offenbar mit Mehrfachkanten, also mit keinem schlichten Graphen zutun. Das spielt aber bei der Losung des Problems keine Rolle: Indem wir aufjede Mehrfachkante (oder sogar auf jede Kante) einen weiteren Knoten setzen,entsteht ein schlichter Graph (3). Nach einigem Probieren kommt man zu derUberzeugung, dass es dennoch keine positive Losung gibt: Stets bleibt man nachein paar Schritten in einem Stadtteil stecken, weil keine weiteren Brucken zurVerfugung stehen, um diesen wieder zu verlassen. Wir fragen daher:
Wieviele zusatzliche Brucken musste man bauen, um einen “Eulerschen Rund-weg” zu ermoglichen?
Es ist naheliegend, dass an jeden Stadtteil eine gerade Anzahl von Bruckenanschließen muss, damit man diesen stets wieder verlassen kann, nachdem mandort gelandet ist. Also bauen wir zwei weitere Brucken:
��
����
A
B
C
D
� �� �� � ��
� ��� �
� � (4)
���
@@@BB
��
BB��
��BB
��BB
cAcBc
C
cD(5)
1 PP��6
5
7
4
@@@
���
2 3
9 8
Und jetzt ist ein Rundweg schnell gefunden. Wurden wir auf eine der beidenzusatzlichen Brucken 1 oder 6 verzichten, so bliebe immerhin noch ein Wegzwischen zwei Endpunkten, bei dem alle Brucken einmal besucht werden.
10
Zur allgemeinen Formulierung und Losung des zuvor beschriebenen Pro-blems nennt man eine Folge K = (x0x1, x1x2, ..., xn−1xn) von paarweise ver-schiedenen Kanten eines Graphen G = (X,E), wobei jeweils die nachste mitder vorherigen einen Endpunkt gemeinsam hat, einen Kantenzug. Eine Folge(x0, ..., xn) von Ecken heißt Eulerscher Weg , falls K = (x0x1, x1x2, ..., xn−1xn)ein Kantenzug mit E = {xi−1xi | i ∈ n} ist, also alle Kanten des Graphen ge-nau einmal “durchlaufen” werden (Ecken durfen mehrfach besucht werden). DerWeg ist offen, falls x0 6= xn. Gilt hingegen x0 = xn, so spricht man von einemEulerschen Rundweg oder einer Euler-Tour des Graphen G.
Beispiel 3.7 Das Haus vom Nikolausist das bekannteste Beispiel eines Graphen, der mehrere Eulersche Wege, aberkeinen Eulerschen Rundweg besitzt.
ca
cec
b cdcc���
@@@
@@��
a e
b d
c
���
@@@
@@
��
Jeder Euler-Weg hat hier die Endpunkte a und e, da dies die einzigen Eckenmit ungeradem Grad sind; zum Beispiel: (a, b, c, d, e, b, d, a, e).
Und nun zum klassischen Satz von Euler (1736):
Satz 3.8 Ein endlicher zusammenhangender Graph besitzt genau dann eineEuler-Tour, wenn jede seiner Ecken einen geraden Grad hat.
Beweis. Die Notwendigkeit dieser Gradbedingung ist offensichtlich, denn beieiner Euler-Tour tritt jede Ecke ebenso oft als Endpunkt wie als Anfangspunkteiner Kante auf.
Um unter der Annahme, alle Eckengrade seien gerade, eine Euler-Tour zukonstruieren, kann man folgendermaßen vorgehen (und dieses Verfahren zu ei-nem exakten Algorithmus ausbauen): Man startet mit einer beliebigen Ecke undbildet durch schrittweises Anhangen von neuen Kanten einen Kantenzug. Lasstsich ein solcher nicht mehr weiter verlangern, so muss der Endpunkt der letztenKante mit der Startecke zusammenfallen (sonst wurde der Endpunkt mit einerungeraden Anzahl von Kanten inzidieren).
Enthalt der so gebildete geschlossene Kantenzug K = (k1, ..., kn) noch nichtalle Kanten des Graphen, so gibt es wegen des Zusammenhangs eine Kante l1,die nicht zu K gehort, aber mit zwei aufeinanderfolgenden Kanten ki und ki+1
eine gemeinsame Ecke besitzt. Da der durch Wegnahme von K entstehendeRestgraph H wieder lauter Ecken geraden Grades hat, konnen wir einen wei-teren geschlossenen Kantenzug L = (l1, ..., lm) in H bilden, der zusammen mitK einen langeren geschlossenen Kantenzug (k1, ..., ki, l1, ..., lm, ki+1, ...kn) liefert.Nach endlich vielen Iterationen dieses Verfahrens hat man alle Kanten des ge-samten Graphen ausgeschopft und damit eine Euler-Tour gefunden. �
11
d l1
d dl4�� d l3AA dl2��dQ
QQ dk6d dk1��dk2
k3��dk4AA d l5��dk5AAk7
��� d
Fur das “Haus vom Nikolaus” und analoge Aufgaben braucht man die “offeneVariante” des Eulerschen Satzes:
Satz 3.9 Ein endlicher zusammenhangender Graph besitzt genau dann einenoffenen Euler-Weg, wenn alle bis auf zwei Ecken einen geraden Grad haben.Diese sind dann die Endpunkte eines jeden Euler-Weges.
Man fuhrt diesen Satz einfach auf den vorigen zuruck, indem man die bei-den Ecken ungeraden Grades mit einer neu hinzugefugten Ecke verbindet undso die Bedingung (a) in Satz 3.8 erfullt. Der erweiterte Graph hat dann einenEulerschen Rundweg, und nach Wegnahme der “Hilfsecke” (und der beiden Ver-bindungskanten) bleibt ein Eulerscher Weg im ursprunglichen Graphen ubrig.
Auf die Zusammenhangsvoraussetzung in Satz 3.8 kann man noch verzich-ten, indem man die einzelnen Komponenten betrachtet. Unter einem Kreis ineinem Graphen versteht man eine Eckenfolge (x0, ..., xn), so dass xi−1xi stetseine Kante ist und xi 6= xj fur alle i < j < n, aber x0 = xn und n ≥ 3 gilt.Alternativ nennt man auch den zugehorigen Kantenzug (x0x1, x1x2, ..., xn−1xn)oder den entsprechenden Teilgraphen einen Kreis.
Satz 3.10 Fur einen endlichen Graphen G sind folgende Aussagen aquivalent:
(a) Der Grad jeder Ecke von G ist gerade.
(b) Die Kantenmenge von G zerfallt in kantendisjunkte Kreise.
(c) Jede Komponente von G besitzt eine Euler-Tour.
Beweis. (a)⇒(b): Induktion nach der Anzahl der Kanten. Gibt es uberhauptkeine Kanten, so ist nichts zu zeigen. Andernfalls findet man ahnlich wie imVerfahren zum Beweis von Satz 3.8 einen Kreis K, und im Restgraphen, derdurch Herausnahme von K entsteht, haben wieder alle Ecken einen geradenGrad. Nach Induktionsannahme kann die Kantenmenge dieses Restgraphen indisjunkte Kreise zerlegt werden. Durch Hinzunahme des Kreises K bekommenwir eine Zerlegung der Kantenmenge von G in Kreise.
(b)⇒(c). Die Kantenmenge einer Komponente Z ist nach (b) disjunkte Verei-nigung von Kreisen (denn jeder Kreis ist zusammenhangend, liegt also ganz ineiner Komponente). Sei Y eine maximale Vereinigung solcher Kreise, die eineEuler-Tour (k1, ..., kn) enthalt. Unter der Annahme, dass Y echt in Z enthaltenist, finden wir wegen des Zusammenhangs von Z eine Kante l1 in Z \ Y , diemit einer Kante ki aus Y einen Endpunkt gemeinsam hat. Diese Kante liegtdann auf einem zu Y kantendisjunkten Kreis L = (l1, ..., lm) von Z. Aber dannware wieder (k1, ..., ki, l1, ..., lm, ki+1, ..., kn) eine Euler-Tour, im Widerspruch zurmaximalen Wahl von Y . Der Schluss (c)⇒(a) ist wie im vorigen Beweis klar. �
12
Stellen wir uns vor, das Bruckenproblem sollte durch eine Rundfahrt per Busgelost werden, und es gabe Brucken, die nur in einer Richtung uberfahren werdendurfen. Fur diese Situation braucht man nur eine allgemeinere Definition vonDigraphen mit Mehrfachkanten. Die Aussagen und ihre Beweise konnen dannnahezu wortlich ubernommen werden.
Man definiert daher einen allgemeinen Digraphen als Quadrupel (X,P, a, e),bestehend aus einer Menge X (von “Ecken” oder “Knoten”), einer Menge P(von “Pfeilen” oder “gerichteten Kanten”) und zwei Funktionen a : P −→X unde : P −→X, die jedem Pfeil p ∈ P einen “Anfangspunkt” a(p) und einen “End-punkt” e(p) zuordnen. Damit hat man alle Spezialfalle (inklusive Mehrfachkan-ten, Schleifen und Richtungen) erfasst. Einen gerichteten Weg definiert mandann zweckmaßigerweise als Folge (p1, ..., pn) von Pfeilen mit e(pi−1) = a(pi)fur 1 < i ≤ n und spricht von einem Kantenzug, falls die Pfeile paarweise ver-schieden sind. Speziell ist ein solcher Kantenzug (p1, ..., pn) ein (gerichteter)Eulerscher Weg , falls er alle Pfeile des Graphen enthalt. Entsprechend definiertman gerichtete Kreise, Pfade und Euler-Touren (bei denen noch e(pn) = a(p1)zu fordern ist). Schließlich erklart man fur jede Ecke x eines allgemeinen Digra-phen die positive Valenz d+(x) als Anzahl der Pfeile p mit Anfangspunkt x, d.h.a(p) = x, und die negative Valenz d−(x) als Anzahl der Pfeile p mit Endpunktx, d.h. e(p) = x. Der Eulersche Satz lautet fur diesen Fall:
Satz 3.11 Fur einen endlichen Digraphen sind folgende Aussagen aquivalent:
(a) Fur jede Ecke von G ist die positive Valenz gleich der negativen Valenz.
(b) Die Kantenmenge von G zerfallt in kantendisjunkte gerichtete Kreise.
(c) Jede Komponente von G besitzt eine gerichtete Euler-Tour.
Der Beweis bleibt, wie schon gesagt, im Wesentlichen der gleiche, man musslediglich statt ungerichteter Kanten Pfeile betrachten.
d l1
�d dl4��� d l3AAK dl2���dQ
QQs dk6d -dk1���dk2
k3���dk4AAU d l5���dk5AAKk7
���+ d
Bei verallgemeinerten (symmetrischen) Graphen hat man statt der beidenFunktionen a und e nur eine Funktion e, die jeder Kante eine zweielementigeMenge (die der beiden “Endknoten”) zuordnet. Der Grad einer Ecke x ist danndie Anzahl aller Kanten k mit x ∈ e(k).
Satz 3.10 und seine gleichlautende Verallgemeinerung auf Graphen mit Mehr-fachkanten laßt sich als Spezialfall von Satz 3.11 interpretieren, indem man ineinem (ungerichteten) Graphen, dessen samtliche Ecken geraden Grad haben,jede Kante so orientiert, dass fur alle Ecken die positive Valenz gleich der nega-tiven Valenz wird. Dass dies moglich ist, folgt aus der ‘ungerichteten’ Version,die zu jeder Komponente eine (ungerichtete) Euler-Tour liefert, entlang der mandie Orientierung der durchlaufenen Kanten definieren kann.
13
Wahrend bei Euler-Touren die Aufgabe darin besteht, jede Kante genau ein-mal zu durchlaufen, soll bei Hamilton-Kreisen jede Ecke des gegebenen Graphengenau einmal besucht werden. Das erste Beispiel fur solche Problemstellungenstammt auch aus alten Zeiten:
Hamilton’s Puzzle (1859) “Around the World”
Auf dem Globus sind 20 Stadte durch kreuzungsfreie Wege so verbunden, dassvon jeder Stadt drei Wege ausgehen und jede von Wegen berandete Flache genaufunf Grenzwege hat. Finde einen Rundweg, auf dem jede Stadt genau einmalbesucht wird!
Die Stadte liegen auf den Ecken eines Dodekaeders (“Zwolf-Flachners”) (1). AusGrunden der Ubersichtlichkeit legen wir die 20 Ecken in die Zeichenebene, indemwir das Dodekaeder von einer der 12 Flachen aus betrachten und die außerenKanten genugend dehnen (2).
����
BBBB
ZZZ
���
�� PP
TT
��
BBBB
����
���
Q
BBBB
����
���
QQQ
PPP���
SSS
���
���
\\\
���PPP
aa !!
TT��(1)
s ss ssc cc ccccccc
d
d
d
dd
BBBBBB
������
��
���
QQQQQ
BB ��
BB ��
�� QQ�� QQ
aa !!
TT��
P
�A
BB����
�
��
BB ��
�� QQ�� QQ
BBBBBB
������
���
��
QQQQQ
TT��(2)
BB����
�
��
BB ��
�� QQ�� QQ
BBBBBB
������
���
��
QQQQQ
TT��(2)
Ein Rundweg durch alle 20 Stadte ist in das Diagramm (2) eingezeichnet.
Dass es 12 Flachen sein mussen, besagt die
Eulersche Polyederformel:Eckenzahl - Kantenzahl + Flachenzahl = 2,
welche fur alle kreuzungsfrei in die Ebene zeichenbaren Graphen gilt und leichtdurch Induktion (z.B. nach Anzahl der Kanten) zu beweisen ist.
Allgemein nennt man eine Eckenfolge (x1, ..., xn) eines endlichen GraphenG = (X,E) einen Pfad, falls je zwei aufeinanderfolgende Ecken durch eine Kanteverbunden sind, d.h. xi−1xi ∈ E fur jedes i ∈ n gilt, und einen Hamilton-Pfad, falls zusatzlich alle Ecken des Graphen genau einmal auftreten. Von einemHamilton-Kreis spricht man, wenn auch noch xnx1 ∈ E erfullt ist. Ein Graphheißt Hamiltonsch, falls er einen Hamilton-Kreis besitzt.
Beispiele 3.12 (1) Jedes m-Eck besitzt 2m Hamilton-Kreise (die alle durchzyklische Vertauschung oder Spiegelung auseinander hervorgehen).
(2) Jeder vollstandige Graph Km = (m,P2m) (auch m-dimensionales Simplexgenannt) mit m ≥ 3 ist Hamiltonsch: Hier ist fur jede Permutation σ der Zahlen1, ...,m die Folge (σ(1), ..., σ(m), σ(1)) ein Hamilton-Kreis. Im m-Simplex gibtes also m! Hamilton-Kreise.
14
cc ccc
CC
��
���Z
ZZ���
BBB
CC
��
cc ccc
CC
��
���Z
ZZ���
BBB
���Z
ZZ���
BBB cc cc
cCC
��
���Z
ZZ���
BBB
CC
��
���
BBB
Beachten Sie, dass ein m-Simplex nur fur ungerades m eine Euler-Tour enthalt!(Warum?)
(3) Die Eckenmenge eines vollstandig bipartiten (“zweigeteilten”) Graphenzerfallt in zwei disjunkte Teilmengen, so dass jede Ecke der einen Menge mit je-der der anderen verbunden ist, aber keine zwei Ecken innerhalb einer der beidenMengen eine Kante bilden. Man bezeichnet einen solchen Graphen mit Km,n,falls die eine Menge m und die andere n Elemente hat. Explizit ist ein solcherGraph bis auf Isomorphie gegeben durch
Km,n = (m+n, {xy | x ∈ m, y ∈ m+n \m} = {m+1, ...,m+n}).
Wahrend Km,n nach Satz 3.8 genau dann eine Euler-Tour besitzt, wenn sowohlm als auch n gerade ist, hat Km,n genau dann einen Hamilton-Kreis, wenn mmit n ubereinstimmt. Ein Hamilton-Pfad existiert auch fur den Fall, dass sichm und n um 1 unterscheiden.
cc c cc@@��
����H
HHH@@
��
K2,3
cc cc cc����HHHH��@@��@@
K3,3
��@@��@@
(4) Alle funf Platonischen Korper besitzen Hamilton-Kreise. Beim Dodekaederhaben wir das zu Beginn dieses Abschnitts gesehen. Hier sind die vier anderen(in die Ebene gelegt und deshalb etwas verzerrt):
c cccTTTT"
"
���� b
b
Tetraeder
���� bb c
ccccc cc
@�
�@
Hexaeder
�@
c ccc ccTTTT
���� A ��� @@
��BB
Oktaeder
�� @@
��BB c c
cc ccT� T� �
QQc c
cc. cpqppc.������
XX�� DD
c
���
```
���
LLL
A\\\
��
��
#
TTTTTT��
Ikosaeder
AA\\\
��
��
#
TTTTTT��
Ikosaeder
Nur das Oktaeder besitzt einen Euler-Weg bzw. eine Euler-Tour!
Leider kennt man im Gegensatz zur Gradbedingung fur Eulersche Graphenkein einfaches Kriterium, das genau die Hamiltonschen Graphen charakterisiert.Allerdings gibt es einige ziemlich gute Bedingungen an die Grade, die in vielenFallen die Existenz eines Hamilton-Kreises sichern. Soviel ist klar: Je mehr Kan-ten ein Graph hat, desto großer ist die Chance, einen Hamilton-Kreis zu finden.Genauer gesagt: Ist G = (X,E) Hamiltonsch, so auch jeder Graph G′ = (X,E′)mit E ⊆ E′. Wir erwahnen hier nur den einpragsamen Satz von Dirac (1952):
Satz 3.13 Ist jede Ecke eines Graphen G = (X,E) mit m ≥ 3 Ecken zu min-destens der Halfte aller Ecken adjazent (d. h. d(x) ≥ m
2 fur alle x ∈ X), so hatG einen Hamilton-Kreis.
15
3.3 Baume und Walder
Was ist die graphentheoretische Abstraktion eines Baumes? Man stellt sich einzusammenhangendes, verzweigtes Gebilde vor, bei dem “nie zwei Aste wiederzusammenwachsen”. Deshalb nennt man einen zusammenhangenden und kreis-freien Graphen (also einen ohne Kreise) einen Baum. Ein Wald ist ein kreisfreierGraph, also eine disjunkte Vereinigung von Baumen (die Kreisfreiheit ubertragtsich offenbar auf die Komponenten, und umgekehrt). Die Komponenten einesWaldes sind genau seine maximalen Baume.
Baume und Walder treten in einer Vielzahl von Anwendungsbereichen auf:nicht nur in der Botanik, sondern auch der Chemie, der Genetik, der Palaonto-logie, der Logik, und naturlich nicht zuletzt in der Informatik. Wir konnen hiernur einen kleinen Ausschnitt der interessanten Theorie der Baume ansprechen.
In einem Graphen nennt man die Knoten vom Grad 1 anschaulich Blatter(oder Endknoten).
Beispiel 3.14 Blatterwald.
d@ r�d r ddd@ r�d r ddd@ r��d r r�� d@�ddd
@ r�d r d@�ddd
@ r�d r r��d
@�dd rd�d ddr@�rd
Das “Abpflucken” von Blattern geht graphentheoretisch folgendermaßen:Fur beliebige Graphen G = (X,E) und jeden Knoten y ∈ X bezeichnet manden auf X \ {y} induzierten Teilgraphen mit G− y. Dann gilt die folgende, furviele Induktionsbeweise nutzliche Beziehung:
Lemma 3.15 Sei G ein Graph und y ein Blatt von G. Genau dann ist G einBaum, wenn G− y ein Baum ist.
Beweis. Bei Wegnahme eines Blattes von einem Baum bleibt offenbar ein kreis-freier zusammenhangender Graph ubrig, wahrend Herausnahme von Knoten miteinem Grad > 1 den Zusammenhang zerstort (sonst hatte G einen Kreis).
Umgekehrt entsteht aus einem Baum G− y durch Hinzufugen von y wiederein Baum, falls y mit genau einem Knoten x vonG−y direkt verbunden wird (derZusammenhang bleibt bestehen, da y dann mit allen Knoten von G − y durcheinen uber x verlaufenden Weg verbunden werden kann, und Kreise konnennicht entstehen, da y nur einen Nachbarn hat). �
Wir kommen nun zu drei weiteren wichtigen Charakterisierungen von Baumen.Dazu nennen wir einen Graphen
• maximal kreisfrei, wenn er keine Kreise besitzt, aber die Hinzunahme einerbeliebigen Kante einen Kreis erzeugt,
• minimal zusammenhangend, wenn er zusammenhangend ist, aber die Weg-nahme einer beliebigen Kante den Zusammenhang zerstort.
16
Satz 3.16 Fur einen Graphen G = (X,E) sind die folgenden vier Aussagenaquivalent:
(a) G ist ein Baum.
(b) Je zwei Knoten von G sind durch genau einen Pfad verbunden.
(c) G ist minimal zusammenhangend.
(d) G ist maximal kreisfrei.
Beweis. (a)⇒(b). Wegen des Zusammenhangs sind je zwei Knoten x und ydurch mindestens einen Pfad verbunden. Waren x und y durch zwei verschiedenePfade (x0, ..., xn) und (y0, ..., yk) verbunden, so ware
(x=x0, x1, ..., xn =y=yk, yk−1, ..., y1, y0 =x)
ein geschlossener Weg, aus dem man einen Kreis herausschneiden konnte.
(b)⇒(c). Naturlich ist G zusammenhangend. Ware fur eine Kante xy der GraphG−xy = (X,E \{xy}) immer noch zusammenhangend, so konnte man x und ydurch einen Pfad (x0, ..., xn) verbinden, in dem die Kante xy nicht vorkommt.
(c)⇒(a). Hatte G einen Kreis, so konnte man aus diesem eine Kante xy entfer-nen und behielte immer noch einen zusammenhangenden Graphen: denn jederWeg (x0, ..., xn), der die Kante xi−1xi = xy benutzt, kann durch einen anderenWeg ersetzt werden, indem die Kante xy durch den Rest des Kreises ausge-tauscht wird, auf dem sie liegt.
(b)⇒(d). Hatte G einen Kreis (x0, ..., xn−1, xn =x0), so waren x0 und xn−1durch die beiden verschiedenen Pfade (x0, ..., xn−1) und (x0, xn−1) verbunden.Aber durch Hinzufugen einer Kante xy entsteht ein Kreis, da x und y schonvorher durch einen Pfad verbunden waren.
(d)⇒(a). Gabe es in G zwei durch keinen Weg verbundene Knoten x und y, soware G + xy = (X,E ∪ {xy}) immer noch kreisfrei, denn ein Kreis (x0, ..., xn)in G+ xy musste die neue Kante xy enthalten, d.h. es ware xi−1xi = xy fur eini, etwa x = xi und y = xi−1 (sonst umgekehrter Durchlauf). Dann ware aber(x=xi, xi+1, ..., xn, x0, x1, ..., xi−1 =y) ein Weg in G zwischen x und y. �
Fur endliche Baume gibt es noch zwei besonders einfache Beschreibungen.Zunachst notieren wir eine Eigenschaft endlicher zusammenhangender Graphen:
Lemma 3.17 Ein endlicher zusammenhangender Graph G mit m Knoten hatmindestens m−1 Kanten.
Beweis. Die Aussage ist richtig fur m = 1. Wir gehen induktiv vor und betracheneinen Pfad maximaler Lange in einem zusammenhangenden Graphen G mit mKnoten, etwa (x0, ..., xn). In G sind je zwei von x0 verschiedene Knoten durchWege verbunden, die x0 nicht enthalten (sonst ware x0 ein “innerer” Punkteines Verbindungsweges, und man konnte den bei x0 beginnenden maximalenPfad verlangern). Deshalb ist G − x0 immer noch zusammenhangend. NachInduktionsannahme hat G − x0 mindestens m − 2 Kanten, also G mindestensm−1 Kanten (denn mindestens eine an x0 hangende Kante kommt ja hinzu). �
17
Satz 3.18 Fur einen endlichen Graphen G mit m Knoten sind aquivalent:(a) G ist ein Baum.(e) G ist zusammenhangend und hat genau m−1 Kanten.(f) G ist kreisfrei und hat genau m−1 Kanten.
Beweis. (a)⇒(e) und (f). Die Entfernung einer Kante xy bewirkt nach Satz 3.16(a)⇒(c) den Zerfall in zwei Komponenten. Jede der beiden Komponenten istnaturlich immer noch kreisfrei, also jeweils ein Baum. Nach Induktionsannahmehaben beide jeweils eine Kante weniger als Knoten. Nach “Restaurieren” derKante xy gilt das dann auch fur den Graphen G.
(e)⇒(a). Hat man eine Kante weniger als Knoten zur Verfugung, so ist Gminimal zusammenhangend, denn ein Graph mit m Knoten und weniger alsm−1 Kanten ist, wie wir sahen, unzusammenhangend.
(f)⇒(a). Jede Komponente ist kreisfrei und zusammenhangend, also einBaum. Nach dem schon Bewiesenen hat sie jeweils eine Kante weniger als Kno-ten. Das geht aber bei insgesamt m−1 Kanten nicht, außer es war uberhauptnur eine einzige Komponente vorhanden (denn fur jede Komponente wird 1abgezogen). Also ist G zusammenhangend und damit ein Baum. �
Das letzte Argument zusammen mit Lemma 3.17 liefert auch noch eine ver-bluffend einfache Charakterisierung endlicher kreisfreier Graphen:
Folgerung 3.19 Die endlichen Walder sind genau diejenigen endlichen Gra-phen, die die folgende “Euler-Gleichung” erfullen:
Anzahl der Knoten = Anzahl der Kanten + Anzahl der Komponenten.
Fassen wir zusammen:
(1) Nach Wegnahme einer Kante aus einem Wald bleibt ein Wald ubrig, dergenau eine Komponente mehr als der ursprungliche hat. Insbesondere zerfalltein Baum nach Wegnahme einer Kante in zwei Baume. Umgekehrt entstehtdurch Verbinden zweier Baume durch eine Kante ein einzelner Baum.
(2) Nach Wegnahme eines Blattes und der damit inzidierenden Kante voneinem Baum (bzw. Wald) bleibt ein Baum (bzw. Wald) ubrig. Umgekehrt wirdaus einem Baum durch Hinzufugen einer Kante zwischen einem schon vorhan-denen und einem neuen Knoten wieder ein Baum.
(3) In allen anderen Fallen bewirkt die Wegnahme eines Knotens und der mitihm inzidierenden Kanten den Zerfall in ebensoviele Komponenten, wie Kantenentfernt wurden. Umgekehrt wird aus einem Wald ein Baum, wenn man je einenKnoten aus den Komponenten mit einem gemeinsamen neuen Knoten verbindet.
d@@ r��r r r�� d@@��@@drd d d
(0)d@@ r��r r r�� d@@��@@drd d d
(1)d@ r��d r r�� d@@ ��drd d
(2)dd r d�� d@@ ��@@drd d d
(3)
18
Die Isomorphietypen von Baumen mit maximal 7 KnotenAutomorphismenzahl a und Anzahl i der isomorphen Kopien
d��d dddd d��
7207
d��d ddddd
24210
dd dddd d
12420
dddddd d
6840
d ddddd d
8630
ddddddd4
1260
dddddd d
22520
ddddddd
6840
dddddd d
15040
d
ddddd d
22520
d ddddd d
22520
16807 = 75
���
d��d dddd1206 �����
���
AAA
XXXXXXXXXX
dd dddd
6120 �����
PPPPPPPP
dddddd
890
��������
QQQQ
XXXXXXXXXX
d dddd d
2360
����������
���
����
BBB
ddddd d
2360 �
��
@@@
d dddd d
2360 1296 = 64
��
d dddd
245
���������
�@@
XXXXXXXX
dddd d
260 �
�@@
dddd d
260 125 = 53
��
@@
dddd
64 �
�@@
dddd
212 16 = 42
��
@@
ddd
23 3 = 31
dd2
1 1 = 2 0
d1
1 1 = 1−1
19
Wahrend bei den zuvor eingefuhrten graphentheoretischen Baumen keineRichtung der Kanten vorgegeben ist, stellt man sich bei einem “echten” Baumvor, dass er “von unten nach oben auseinander wachst”. Dieser Anschauungwird eine ordnungstheoretische Variante des Baumbegriffes gerecht, die wir jetztbetrachten wollen. Wir verstehen unter einem Wurzelbaum eine diskrete geord-nete Menge (X,v) mit einem kleinsten Element w (der Wurzel), so dass keinezwei unvergleichbaren Elemente unter einem gemeinsamen Element liegen, oderandersherum (durch Kontraposition) ausgedruckt:
(Ψ) x v z und y v z ⇒ x v y oder y v x.
Eine diskrete geordnete Menge mit der Eigenschaft (Ψ) nennen wir Wurzelwald,falls jedes Element uber einem minimalen liegt. (Beachten Sie den Unterschiedzwischen minimalen und kleinsten Elementen: Ein kleinstes Element liegt unterallen anderen, wahrend ein minimales nur die Eigenschaft hat, dass kein ande-res darunter liegt!) Ein Wurzelbaum heißt unar (binar, ternar), wenn all seineElemente hochstens einen bzw. zwei bzw. drei obere Nachbarn haben.
Beispiel 3.20 Ein Wurzelwald mit einem unaren, einem binaren und einemternaren Wurzelbaum.
cccc
1
2
3
4
c∅c0 c1c00 c01 c10 c11c000 c001 c010 c011 c100 c101 c110 c111
@@��
AA��
AA��
CC��
CC��
CC��
CC��
c∅HHHH
����
cpco ct
cpoCC�� cot ctoCC ��cpop cpot cott ctop ctotcottocpopo cpott ctoto
Satz 3.21 Eine geordnete Menge ist genau dann ein Wurzelwald, wenn ihreKomponenten Wurzelbaume sind.
Beweis. Sind die Komponenten Wurzelbaume, so ubertragt sich (Ψ) von diesenauf die Gesamtmenge (denn die Voraussetzung x v z und y v z erzwingt, dassx und y in der gleichen Komponente liegen).
Umgekehrt ist jede Komponente B eines Wurzelwaldes zusammenhangendund erfullt (Ψ). Wir wahlen ein minimales y in der geordneten Menge B undbehaupten, dass y unter jedem anderen x ∈ B liegt. Wegen des Zusammenhangsvon B gibt es eine Folge (x=x0, x1, ..., xn =y) minimaler Lange n mit xi−1 @ xi
oder xi @ xi−1 fur jedes i ∈ n. Nun ist xn−1 @ y wegen der Minimalitat von yausgeschlossen; also muss der Fall y @ xn−1 eintreten. Die kleinstmogliche Wahlvon n erzwingt unter der Annahme n > 1 die Beziehung xn−2 @ xn−1 (sonstkonnte man xn−1 wegen der Transitivitat weglassen). Aber nun liefert (Ψ) furxn−2 statt x zusammen mit der Minimalitat von y die Beziehung y v xn−2, undwir konnten xn−1 doch weglassen. Also ist nur n ≤ 1 und y v x moglich. �
cx=x0
cxn =yc
xn−2
c xn−1c ��
@@
��
@@
20
Wurzelbaume und -walder werden vielfach auf den Kopf gestellt (dualisiert). DieDiagrammdarstellung liefert dann ein nach unten verzweigtes Wurzelgeflecht.
c c c cc c cc cc
JJ JJ
JJ JJ
JJ
Wir wollen uns uberlegen, wie die Baume der Graphentheorie mit den Wur-zelbaumen der Ordnungstheorie zusammenhangen. Erinnern wir uns daran, dassder Nachbarschaftsgraph (X,E) einer geordneten Menge (X,v) durch Symme-trisierung der Nachbarschaftsrelation @∨ entsteht, also indem man nur die un-gerichteten Kanten zwischen benachbarten Elementen betrachtet:
E = {xy | x @∨ y}.
Satz 3.22 Der Nachbarschaftsgraph eines Wurzelbaumes (X,v) ist ein Baum,und die Ordnung ist durch diesen Baum und die Wurzel w festgelegt:
(W) x v y ⇔ x liegt auf dem Pfad von w nach y.
Umgekehrt gibt es zu jedem Knoten w eines Baumes B = (X,E) genau einenWurzelbaum mit Wurzel w, dessen Nachbarschaftsgraph B ist, namlich dendurch (W) definierten. Aus jedem Baum mit m Knoten entstehen also genaum Wurzelbaume durch Festlegung der Wurzel.
t@ r�d r drdw
xy
Beweis. Fur einen Wurzelbaum (X,v) ist der Graph (X,E) mit E= {xy|x@∨y}wegen der endlichen Verkettung zusammenhangend. Ware (x0, x1, ..., xn = x0)ein Kreis in (X,E) minimaler Lange, so konnte nicht fur jedes i < n die Bezie-hung xi @∨xi+1 gelten (sonst ware x0 @ xn), also gibt es ein i mit xi−1 @∨xi
und xi+1 @∨xi (wobei x−1 = xn−1 und xn+1 = x1 zu setzen ist). Aber wegender Bedingung (Ψ) ware dann xi−1 mit xi+1 vergleichbar, und xi ware zu einemdieser Elemente nicht benachbart. Also kann (X,E) keine Kreise enthalten.
Nun sei B = (X,E) ein Baum und w ein fest gewahlter Knoten. Wir defi-nieren eine Relation v auf X durch (W) und beachten, dass es nach Satz 3.16stets einen eindeutigen Pfad zwischen w und y gibt. Die Relation v ist offen-bar reflexiv und transitiv. Antisymmetrisch ist sie wegen der Nichtexistenz vonKreisen: Im Falle x @ y @ x gabe es einen geschlossenen Weg durch x und y,und dieser enthielte einen Kreis. Die so entstehende geordnete Menge (X,v) istein Wurzelbaum mit Wurzel w, denn nach Definition gilt w v y fur alle y ∈ X,und im Falle x v z und y v z liegen x und y auf dem Pfad von w nach z,und es folgt x v y oder y v x. Der Nachbarschaftsgraph der Ordnung v ist derursprungliche Baum B (wegen der Eindeutigkeit der verbindenden Pfade). �
21
Aufgrund des letzten Satzes kann man die Wurzelbaume mit “Stamm-baumen” identifizieren; das sind Paare (G,w), die aus einem Baum G und einemfestgewahlten Knoten w bestehen.
Wurzelbaume und Wurzelwalder lassen sich ebenso einfach wie Baume undWalder rekursiv aufbauen, indem man die folgenden beiden Schritte iteriert:
(A) Aus jedem Wurzelwald entsteht durch Hinzufugen eines disjunkten Bau-mes ein neuer Wurzelwald.
(B) Aus jedem Wurzelwald entsteht durch Hinzufugen einer Wurzel, die mitallen Wurzeln der Komponenten verbunden wird, ein Wurzelbaum.
t@ r�d r dd(A) + =t@ r
�d r ddt@ r��d r r�� d@�ddd
t@ r�d r dd(A) + = t@ r�
d r ddt@ r�d r ddt@ r��d r r�� d@�ddd
t@ r�d r dd(B)
+ =
t@ r�d r dd
t@@@ ���
r@ r�d r ddr@ r�d r dd
@@@ t���
Konstruktion (B) kann man noch erweitern, indem man auf jeden Knoteneines Wurzelbaumes einen weiteren Wurzelbaum “aufpfropft”.
Der nachste Satz ist anschaulich einleuchtend, bedarf aber doch eines Beweises:
Satz 3.23 Eine diskrete geordnete Menge ist genau dann ein Wurzelbaum,wenn sie ein kleinstes Element besitzt und jedes andere Element genau einenunteren Nachbarn (“Vorganger”) hat.
Beweis. Ist (X,v) ein Wurzelbaum und (w=x0, ..., xn =y) der eindeutige Pfadvon der Wurzel w nach y, so ist xn−1 der eindeutige untere Nachbar von y.
Hat umgekehrt eine diskrete geordnete Menge (X,v) das kleinste Elementw und die genannte Nachfolge-Eigenschaft, so muss (Ψ) gelten: Zu x v z undy v z finden wir Pfade (z=x0, ..., xk =x) und (z=y0, ..., yn =y) mit xi @∨ xi−1fur i ∈ k und yi @∨ yi−1 fur i ∈ n. Sei i der großte Index mit xi = yi. Im Fallei < k und i < n ware dann auch noch xi+1 @∨ xi und yi+1 @∨ xi erfullt, alsoxi+1 = yi+1 im Widerspruch zur Wahl von i. Also xv xi = y oder yv yi = x. �
Vorsicht! Bei einem dualisierten Baum sind die “Vorganger” Nachfolger!
22
Wir wollen uns nun der Frage zuwenden, wie man Baume und Walder co-dieren, d.h. durch geeignete Zahlenfolgen eindeutig beschreiben kann. Der Ein-fachheit halber nehmen wir dabei an, dass die Knotenmenge m = {1, ...,m} ist.Das naheliegendste Codierungsverfahren wird durch Satz 3.23 geliefert: DieVorgangerfunktion eines Wurzelwaldes ordnet jedem nichtminimalen Knoten sei-nen eindeutigen unteren Nachbarn zu. Die Nachbarschaftsrelation eines Wurzel-baumes ist allerdings dual zur Vorgangerfunktion, also eine Nachfolgerfunktion !Erinnern wir uns daran, dass Funktionen nichts anderes als spezielle Relationensind, namlich solche Relationen F , bei denen zu jedem x hochstens ein y mitxF y existiert, und dass dieses y mit F (x) bezeichnet wird. Der Definitionsbe-reich von F ist dann die Menge aller x, fur die es ein solches y gibt. Irreflexivitatbedeutet fur eine Funktion F , dass sie keinen Fixpunkt hat (also F (x) = x nieauftritt). Weiter ist F genau dann intransitiv, wenn F (x) = F k(x) nur fur k = 1moglich ist. Solche Funktionen beschreiben gerade die Wurzelwalder:
Satz 3.24 Fur eine Relation F ⊆ m×m sind aquivalent:
(a) F ist die Vorgangerfunktion eines Wurzelwaldes mit Knotenmenge m.
(b) F ist eine intransitive Funktion.
(c) F ist eine irreflexive und azyklische Funktion, d.h. x 6= F k(x) fur k ∈ N.
Beweis. (a) ⇔ (b) folgt unmittelbar aus Satz 3.23 und der bekannten Tatsache,dass die endlich veketteten Ordnungen durch Ubergang zu Nachbarschaftsrela-tionen bijektiv den intransitiven Relationen entsprechen.
Die Aquivalenz von (b) und (c) beweist man durch Kontraposition:
(b)⇒(c). Aus k ≥ 1 und x = F k(x) folgt k+1 > 1 und F (x) = F k+1(x).
(c)⇒(b). Aus k+1 > 1 und F (x) = F k+1(x) folgt fur y = F (x): y = F k(y). �
Folgerung 3.25 Man erhalt eine Bijektion zwischen Wurzelwaldern mit Kno-tenmenge m und intransitiven Funktionen von Teilmengen der Menge m nachm, indem man jedem Wurzelwald seine Nachfolgerfunktion zuordnet. Dabei ent-sprechen den Wurzelbaumen diejenigen intransitiven Funktionen, deren Defini-tionsbereich genau ein Element von m (die Wurzel) nicht enthalt.
Beispiel 3.26 Der Vorgangercode des Wurzelwaldes
t5
@ r8�d4 d9 t7
@ r2d3 r1d6
lautet
F =(
1 2 3 4 6 8 92 7 2 8 1 5 8
)Hingegen kann die an der Stelle 2 abgeanderte Funktion
23
F =(
1 2 3 4 6 8 92 6 2 8 1 5 8
)wegen F 3(2) = 2 kein Nachfolgercode eines Wurzelwaldes sein. In der Tatenthalt der zugehorige Digraph einen Zykel:
t5
@R r8�d4?
d9t7
@R r2d3
??
��@Ir1d6
Ein Vorteil der zuvor beschriebenen Codierung ist, dass man den zugehorigenWurzelwald sehr schnell rekonstruieren kann. Allerdings sieht man einer Funk-tion (bzw. der entsprechenden endlichen Folge) nicht immer sofort an, ob sieuberhaupt einen Wurzelwald bzw. -baum beschreibt. Man kann jedoch alle Wur-zelwalder durch einen sehr einfachen Algorithmus gewinnen: Beginnend mit denm Knoten 1, ...,m und der leeren Kantenmenge, fugt man Schritt fur Schritt einenummerierte und gerichtete Kante hinzu. Die einzige zu beachtende Vorschriftist dabei, dass in jedem Schritt die neu anzufugende Kante zwischen zwei ver-schiedenen Komponenten des bis dahin entstandenen Wurzelwaldes verlaufenmuss. Fur die k-te Kante (in Richtung der Vorgangerfunktion) hat man zwarm Moglichkeiten, den Endpunkt zu wahlen, aber nur noch m−k Moglichkeitenbei der Auswahl des Anfangspunktes (denn dieser darf weder zuvor verwendetworden noch Wurzel der Komponente des Endpunktes sein – sonst entsteht einZykel). Insgesamt gibt es also∏m−1
k=1m(m− k) = (m−1)!mm−1
Moglichkeiten der nummerierten Kantenwahl. Am Schluss ist ein Wurzelbaumentstanden, dessen Kanten mit einer Permutation der Zahlen von 1 bis m−1belegt sind. Da es (m− 1)! solche Permutationen gibt, bleiben nach Entfer-nen der Nummerierung der Kanten mm−1 Wurzelbaume. Damit ist der folgendeberuhmte Satz von Cayley (1889) gezeigt:
Satz 3.27 Auf einer festen Menge von m Knoten gibt es genau mm−1 Wur-zelbaume und folglich mm−2 Baume.
Die vielleicht eleganteste Codierung von Baumen geschieht mit Hilfe dessogenannten Prufer-Codes. Die simple, aber wirkungsvolle Grundidee bestehtdarin, schrittweise die Blatter mit den kleinsten Nummern abzupflucken undgleichzeitig die Folge der zum jeweiligen Blatt benachbarten Knoten zu notieren,bis nur noch zwei Knoten ubrigbleiben. (Aufgrund unserer Konvention, m alsKnotenmenge zu nehmen, sind die Nummern die Blatter selbst.)
Satz 3.28 Zu einem gegebenen Baum G = (m,E) definiere man induktiv zweiFolgen (bi | i = 1, ...,m−2) und (ai | i = 1, ...,m−2) durch die Festlegung, dass bidas kleinste Blatt des Baumes Gi = G− {bj | j < i} und ai sein Nachbar in Gi
ist. Auf diese Weise erhalt man eine Bijektion zwischen der Gesamtheit allerBaume mit der Knotenmenge m und der Menge mm−2 aller (m−2)-stelligenFolgen (a1, ..., am−2) mit Werten in m.
24
Dies bestatigt den Satz von Cayley. Die oben konstruierte Folge (a1, ..., am−2)heißt Prufer-Code des Baumes G. Um Satz 3.28 zu begrunden, mussen wiruns vergewissern, dass jede Folge (a1, ..., am−2) in m wirklich als Prufer-Codeeines eindeutig bestimmten Baumes auftritt. Zu diesem Zweck rekonstruierenwir den gesuchten Baum wie folgt. Wir setzen am−1 := am−2 und bestimmen diezugehorigen Blatter rekursiv durch die Vorschrift, dass bi das kleinste Elementder folgenden Restmenge sei:
m \ {b1, ..., bi−1, ai, ai+1, ..., am−1} (i = 1, ...,m−1).
Der letzte Knoten bm ist dann der noch ubrig gebliebene, und die Kanten desBaumes sind die Zweiermengen aibi (i = 1, ...,m−1).
Beispiel 3.29 Wir betrachten die Folge (3, 7, 3, 7, 3) und bauen schrittweiseden zugehorigen Baum mit der Knotenmenge 7 auf:
5 = min(7 \ {1, 2, 3, 4, 7})
bi 1
3
2
7
4
3
5
7
6
3
7
3ai
@ d3d1
7 \ {3, 7}
@ d3d1 d7 2d�
7 \ {1, 3, 7}
@ d3d1 d7 d2�
d4
�
7 \ {1, 2, 3, 7}
@ d3d1 d7d5 d2�
d4
�
7 \ {1, 2, 3, 4, 7}
d6
@ d3d1 d7d5 d2�
d4
�
7 \ {1, 2, 3, 4, 5}
d6
@ d3d1 d7d5 d2�
d4
�
7 \ {1, 2, 3, 4, 5, 6}
“Minimales Abblattern” fuhrt auf die ursprungliche Codierung:
d6
@ t3d1 d7d5 d2�
d4
�@ d
6
d3t7d5 d2�
d4
��
d6
t3d7d5 d�
4� d
6
d3t7d5d6
t3d7 d3d7
Wir wollen noch eine Formel fur die Anzahl aller Baume mit Knotenmengem und fest vorgegebenen Gradzahlen di = dG(i) (i = 1, ..,m) aufstellen. Da dieAnzahl der Kanten m−1 betragt, muss die folgende Gleichung erfullt sein:
(K)∑m
i=1 di = 2m−2 bzw.∑m
i=1(di−1) = m−2.
Dabei ist stets di−1 ≥ 0, weil kein Knoten den Grad 0 hat. Mit der Gleichung(K) laßt sich haufig leicht entscheiden, ob eine gegebene Folge die Gradfolgeeines Baumes sein kann oder nicht. Mit Hilfe eines Induktionsbeweises, den wirhier weglassen (Blatter schrittweise abpflucken!) erhalt man die folgende Formel:
25
Satz 3.30 Zu jeder Folge (k1, ..., km) von ganzen Zahlen ki mit 0≤ki<m und∑mi=1 ki = m−2 gibt es genau(
m−2k1 ... km
)=
(m−2)!k1! · . . . · km!
Baume G mit der Knotenmenge m und den Gradzahlen dG(i) = ki+1 (i ∈ m).
Dieser Multinomialkoeffizient ist zugleich die Anzahl der Zerlegungen der Mengem−2 in (eventuell leere) Teilmengen Mi mit ki Elementen. Bei einem Wurzel-baum mit Wurzel m und Nachfolger m−1 erhalt man eine solche Zerlegung,indem man jedem Knoten außer m die Menge seiner Nachfolger und der Wurzelm die Menge der Vorganger bis auf m−1 zuordnet.
Aus Satz 3.30 ergibt sich ein weiteres Mal die Cayleysche Formel, diesmaldurch Summation uber alle Multinomialkoeffizienten:∑
ki≥0,k1+...+km=m−2
(m−2k1 ... km
)1k1 · . . . · 1km = (1 + ...+ 1)m−2 = mm−2.
Schließlich erwahnen wir ohne Beweis (der einige Tricks der linearen Algebrabenutzt) eine geniale Formel, welche fur einen beliebigen zusammenhangendenGraphen die Anzahl seiner Spannbaume oder Geruste, d.h. aller Teilbaume mitgleicher Knotenmenge, angibt.
Satz 3.31 Fur einen endlichen Graphen G = (m,E) ist die Laplace-MatrixQG = (qij) ∈ Zm×m definiert durch
qii = dG(i), qij = −1 fur ij ∈ E und qij = 0 sonst.
Der Betrag der Determinante jeder Matrix, die durch Streichen der i-ten Zeileund j-ten Spalte von QG entsteht, gibt die Anzahl der Spannbaume von G an.Fur den vollstandigen Graphen G = Km ergibt dies wieder die Zahl mm−2.
Beispiel 3.32 Ein Graph und seine 15 Spannbaume
cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc
QG=
2 −1 −1 0 0 0−1 2 0 −1 0 0−1 0 3 −1 −1 0
0 −1 −1 3 0 −10 0 −1 0 2 −10 0 0 −1 −1 2
, Q11=
2 0 −1 0 00 3 −1 −1 0−1 −1 3 0 −1
0 −1 0 2 −10 0 −1 −1 2
, |detQij |= 15.
26
3.4 Mehrfacher Zusammenhang
Dieser Begriff ist fur die Theorie der Netzwerke, Kommunikations- und Trans-portsysteme (also generell fur die Informatik) von großer Bedeutung, dochkonnen wir hier nur kurz auf einige wenige Aspekte eingehen.
Ein Netzwerk (bestehend aus Knoten und Verbindungen) ist umso stabi-ler, je mehr Verbindungen zur Verfugungen stehen. So wird man sich haufigwunschen, dass durch Ausfall einiger “Stationen” oder “Leitungen” nicht dieKommunikation oder der Transport zusammenbricht. Der graphentheoretischeBegriff, der diese “Robustheit” beschreibt, ist der mehrfache Zusammenhang.Genauer nennt man einen Graphen G = (X,E) k-fach eckenzusammenhangendoder k-zusammenhangend, wenn er mehr als k Ecken hat und nach Herausnahmeeiner beliebigen Menge Y von k−1 Ecken immer noch einen zusammenhangendenGraphen auf der Restmenge X \Y induziert. Entsprechend heißt G k-fach kan-tenzusammenhangend, falls nach Entfernen von je k−1 Kanten immer noch einzusammenhangender Graph ubrigbleibt.
Beispiele 3.33 (1) Ein 2-fach eckenzusammenhangender Graph ist stets auch2-fach kantenzusammenhangend, aber die Umkehrung gilt nicht! Der folgendeGraph ist 2-fach kanten-, aber nicht 2-fach eckenzusammenhangend:
d ddd dJJ
JJ
(2) Baume sind niemals 2-fach zusammenhangend, da es (außer im Extrem-fall von hochstens zwei Ecken) immer einen Knoten gibt, der kein Blatt ist, undnach Entfernen eines solchen Knotens zerfallt der Baum. Aus einem ahnlichenGrund sind Baume auch nie 2-fach kantenzusammenhangend (siehe die Dia-gramme nach 2.21).
(3) Ein n-Eck (mit n > 2) ist stets 2-fach, aber niemals 3-fach ecken- bzw. kan-tenzusammenhangend. Allgemeiner ist jeder Hamiltonsche Graph 2-zusammen-hangend und jeder Eulersche Graph 2-fach kantenzusammenhangend.
c cc cc cc c@@
�� @@
�� cc cc cc c�� @@
�� cc cc cc��
�� c cc cc cc c@@
�� @@
�� c cc cc cc c@@
�� @@
��
(4) Am starksten zusammenhangend sind naturlich die vollstandigen Graphen(Simplexe) Km = (m,P2m). Definitionsgemaß sind sie zwar nicht m-zusammen-hangend (da es nur m Knoten gibt), aber sie sind sowohl (m−1)-ecken- als auch(m−1)-kantenzusammenhangend. Fur den Eckenzusammenhang ist das klar,weil alle induzierten Teilgraphen wieder Simplexe sind. Fur den Kantenzusam-menhang beweisen wir ein starkeres Resultat:
27
Satz 3.34 Jeder Graph mit m Knoten und mindestens
(m−1)(m−2)/2 + k = m(m−1)/2− (m−k−1)
Kanten ist k-fach kantenzusammenhangend.
Nach Herausnahme von m−k−1 Kanten aus einem vollstandigen Graphen Km
bleibt also noch ein k-fach kantenzusammenhangender Graph ubrig.
Beweis. Zerfallt ein Graph mit m > k Knoten nach Entfernen von k−1 Kantenin mindestens zwei Komponenten, von denen eine n Elemente hat, so besitztder Restgraph maximal
n(n−1)/2 + (m−n)(m−n−1)/2 = m(m−1)/2−n(m−n) ≤ (m−1)(m−2)/2
Kanten. Der Ausgangsgraph hat also hochstens (m−1)(m−2)/2 + k−1 Kanten.Durch Kontraposition folgt die Behauptung. �
Beispiel 3.35 Ein 3-fach kantenzusammenhangender Graph, der nach Entfer-nen von drei Kanten zerfallt, also nicht 4-fach kantenzusammenhangend ist:
cc cc��@@ cc cc��@@�� cc cc��@@ cc cc��@@
Im Folgenden konzentriert sich unser Interesse auf 2-fachen Zusammenhang.Deinitionsgemaß ist ein Graph mit mindestens drei Knoten genau dann 2-zusammenhangend, wenn das Entfernen einer beliebigen Ecke den Zusammen-hang nicht zerstort. Solche Graphen besitzen eine naheliegende und einfacheCharakterisierung:
Satz 3.36 Ein Graph ist genau dann 2-zusammenhangend, wenn je zwei seinerEcken auf einem Kreis liegen.
Beweis. Wenn letzteres der Fall ist, kann man eine beliebige Ecke loschen, undes bleibt mindenstens ein Weg zwischen je zwei Ecken des Restgraphen (dasie auf einem Kreis des ursprunglichen Graphen liegen). Die Umkehrung istnicht so einfach zu sehen, man beweist sie zum Beispiel per Induktion uberden Abstand (die Lange eines kurzesten verbindenden Pfades) zwischen zweiEcken x und y. Ist dieser gleich 1, so ist xy eine Kante, und nach Entfernenderselben bleibt ein Pfad zwischen x und y, der zusammen mit xy einen Kreisliefert, auf dem x und y liegen. Ist die Aussage fur alle Eckenpaare vom Abstand< k bewiesen, so findet man fur zwei beliebige Ecken x, y mit Abstand k einenkurzesten Verbindungspfad (x = x0, ..., xk = y). Da x und xk−1 den Abstandk−1 haben, liegen sie nach Induktionsannahme auf einem Kreis K in G. DerRestgraph G− xk−1 ist zusammenhangend und enthalt daher einen Pfad von xnach y. Aus einem Teil dieses Pfades und einem Teil des Kreises K bastelt mannun einen Kreis, der x und y enthalt, gemaß der nachfolgenden Skizze:
28
c ccx cc cxk−1c c
@@
�� @@
��
cyc ccx cc cc c
@@
��
����ccy c ccx cc cxk−1c c
@@
�� @@
��ccy
Man kann alle 2-zusammenhangenden Graphen sukzessive generieren, in-dem man, mit einem Kreis startend, schrittweise neue Pfade anhangt, deren(verschiedene!) Endpunkte in dem jeweils zuletzt konstruierten Graphen liegen,wahrend alle anderen (”inneren”) Ecken des Pfades neu hinzukommen.
Beispiel 3.37 Anfugen von “Ohren”
cc cc c cc cc cc c@@
�� @@
��cc c cc cc cc c@@
�� @@
��cc ccc ccc c
@@
�� @@
�� c cc cc cc c@@
�� @@
��cccc
�� @@
ccc ccc c
@@
�� @@
��
Etwas anders formuliert, hat man folgende Charakterisierung:
Satz 3.38 Ein endlichen Graph ist genau dann 2-zusammenhangend, wenn eraus einem Dreieck durch wiederholtes Hinzufugen von Kanten und Unterteilenvon bereits vorhandenen Kanten (d.h. Einfugen von neuen Ecken auf diesenKanten) hervorgeht.
Zu Satz 3.36 gibt es eine wichtige Verallgemeinerung auf k-fachen Zusam-menhang, den beruhmten Satz von Menger (1927). Zu seiner Formulierung brau-chen wir sogenannte trennende Ecken- bzw. Kantenmengen. Man sagt, eine Teil-menge T von Ecken trennt zwei nicht in T liegende Ecken x und y eines GraphenG = (X,E), falls x und y in dem Restgraph G−T durch keinen Weg verbundenwerden konnen, also in zwei verschiedenen Komponenten liegen. Mit anderenWorten: Jeder x mit y verbindende Weg enthalt eine Ecke aus T . Entsprechendtrennt eine Kantenmenge K die Ecken x und y, falls x und y in verschiedenenKomponenten des Restgraphen G−K liegen. Offenbar sind Ex = {z | xz ∈ E}und Ey = {z | yz ∈ E} stets trennende Eckenmengen fur x und y, sofern x undy nicht adjazent sind. Entsprechend sind {e ∈ E |x ∈ e} und {e ∈ E |y ∈ e}trennende Kantenmengen fur x und y, manchmal sogar die einzigen.
Beispiele 3.39 (1) Ein Graph mit drei von acht zweielementigen trennendenEckenmengen und zwei von funf zweielementigen trennenden Kantenmengen furx und y:
29
cs scc cc c
�� @@
@@
@@
@@
��
@@ ��
@@ ��
x
y
sc ccs cc c
�� @@
@@
@@
@@
��
@@ ��
@@ ��
x
y
sc ccc cs c
�� @@
@@
@@
@@
��
@@ ��
@@ ��
x
y
cc ccc cc c
�� @@
@@
@@
@@
��
@@ ��
@@ ��
x
y
@@@@
@@@@ cc ccc cc c
�� @@
@@
@@
@@
��
@@ ��
@@ ��
x
y
@@@@
@@@@
(2) Ein Graph mit drei von elf trennenden Eckenmengen und zwei von viertrennenden Kantenmengen minimaler Machtigkeit 3 fur x und y:
c ccs sc cc
ccs
�� @@
@@ ��
��@@
@@��
�� @@
@@ ��x
y
c csc cs sc
ccc
�� @@
@@ ��
��@@
@@��
�� @@
@@ ��x
y
s csc cc sc
ccc
�� @@
@@ ��
��@@
@@��
�� @@
@@ ��x
y
c ccc cc cc
ccc
�� @@
@@ ��
��@@
@@��
�� @@
@@ ��x
y
�� @@
c ccc cc cc
ccc
�� @@
@@ ��
��@@
@@��
�� @@
@@ ��x
y
@@ ��
(3) Ein Graph mit einer eindeutigen zweielementigen trennenden Eckenmengeund nur zwei trennenden Kantenmengen minimaler Machtigkeit 3 fur x und y:
c cc cc
css
���
AAAA
AA
���
�� @@
@@ ��x
y
c cc cc
ccc
���
AAAA
AA
���
�� @@
@@ ��x
y
�� @@
c cc cc
ccc
���
AAAA
AA
���
�� @@
@@ ��x
y
@@ ��
Zwei Wege zwischen x und y heißen eckendisjunkt, falls sie außer den End-ecken x und y keinen weiteren gemeinsamen Ecken haben, und kantendisjunkt,falls sie keine gemeinsamen Kanten haben. Die Verallgemeinerung des Satzes3.36 von 2 auf k lautet nun:
Satz 3.40 Fur je zwei nichtadjazente Ecken x und y in einem endlichen Gra-phen G ist die maximale Anzahl eckendisjunkter Wege von x nach y gleich derMinimalzahl trennender Ecken. Analoges gilt fur Kanten statt Ecken.
Beweisidee. Eine trennende Eckenmenge muss naturlich mindestens so viele Ele-mente haben, wie es disjunkte Wege zwischen x und y gibt (sonst konnte mansich auf einem Weg an dieser Trennmenge “vorbeimogeln”). Zu zeigen ist also,dass die Existenz einer x und y trennenden Menge T mit einer Minimalzahl vonk Ecken auch k eckendisjunkte Wege zwischen x und y garantiert. Dies beweistman durch eine raffinierte Induktion uber die Anzahl m der Ecken des Graphen,worauf wir hier aber verzichten wollen.
30
