Quelle Nummer 335
Rubrik 27 : MATHEMATIK Unterrubrik 27.02 : FACHWISSENSCHAFTLICH
GRAPHENTHEORIE
KLAUS WAGNER
GRAPHENTHEORIE
B-I-HOCHSCHULTASCHENBUECHER 248/248A
BILBLIOGRAPHISCHES INSTITUT MANNHEIM 1970
S. 62-
001 FUNDAMENTALE SÄTZE DER
002 GRAPHENTHEORIE. Mengerscher Satz und
003 verwandte Sätze. Der Mengersche Graphensatz[ 103
004 ]wurde im Jahre 1927 von K. Menger entdeckt. Er
005 ist einer der schönsten und anwendungsreichsten Sätze der
006 Graphentheorie. Ein Beispiel möge den Satz erläutern. Wir
007 deuten G als Verkehrsnetz mit Knotenpunkten (Ecken von G) und
008 Straßen (Kanten von G). Es seien a und b zwei Knotenpunkte
009 von G. Dann sollen in gewissen (möglichst wenigen) von a und b
010 verschiedenen Knotenpunkten von G Kontrollen errichtet werden,
011 und zwar so, daß jeder Weg von a nach b in G durch mindestens
012 eine Kontrollstelle läuft. Dann besagt der Mengersche
013 Satz, daß die Mindestzahl solcher Kontrollen gleich der
014 maximalen Zahl kreuzungsfreier Wege ist, die von a nach b in G
015 gezogen werden können. Es sei G ein (endlicher oder unendlicher)
016 Graph. a und b seien zwei verschiedene Ecken von G. Jeder
017 Weg in G mit den Endpunkten a und b heiße kurz ein (Formel)-Weg.
018 Wir nennen eine Menge von (Formel)-Wegen ein System
019 kreuzungsfreier Wege oder auch kurz kreuzungsfrei, wenn
020 je zwei (verschiedene) Wege dieser Menge außer a und b keine
021 Ecken (also auch keine Kanten) gemeinsam haben. Wir zeigen
022 zunächst: Sind zwei verschiedene Ecken a und b eines
023 Graphen G für jede natürliche Zahl n durch n kreuzungsfreie
024 Wege von G verbunden, so sind sie auch durch ein unendliches
025 System kreuzungsfreier Wege von G verbunden. Beweis:
026 Nach Voraussetzung (Formel) gibt es einen Weg (Formel) von a nach b in
027 G. Wenn wir zeigen können, daß es zu n kreuzungsfreien (Formel)-
028 Wegen (Formel) in G stets noch einen Weg (Formel) von a nach b in G gibt,
029 so daß auch die Wege (Formel) kreuzungsfrei sind, erhalten wir mittels
030 vollständiger Induktion ein unendliches System kreuzungsfreier (Formel)
031 -Wege (Formel) Wir bemerken zunächst, daß der Graph (Formel) endlich
032 ist. Seine Eckenzahl sei m. Nach Voraussetzung gibt es m
033 kreuzungsfreie (Formel)-Wege (Formel) in G. Wir können annehmen, daß
034 jeder von den betrachteten (Formel)-Wegen, außer a und b, noch
035 Ecken enthält. Dann muß aber, da H (nur) m Ecken besitzt
036 und (Formel) gilt, ein (Formel) existieren, das mit H nur die Ecken a und b
037 gemeinsam hat. Setzen wir (Formel), so sind offenbar die Wege (Formel)
038 kreuzungsfrei, womit der Satz bewiesen ist. Wir nennen ein
039 System von n kreuzungsfreien (Formel)-Wegen (in G) maximal,
040 wenn es keine (Formel) kreuzungsfreie (Formel)-Wege in G gibt.
041 Nach existiert zu je zwei verschiedenen Ecken a und b eines
042 Graphen G stets entweder ein unendliches oder ein maximales
043 endliches System kreuzungsfreier (Formel)-Wege in G. Wir
044 verstehen dann unter der Verbindungszahl von a und b (in G),
045 in Zeichen: (Formel) im ersten Fall die uneigentliche Zahl
046 (Formel) (im Sinne von (Formel)) und im zweiten Fall die Anzahl
047 der Wege eines maximalen kreuzungsfreien Systems von (Formel)-Wegen
048 (in G). Dieser Verbindungszahl von a und b stellen wir die
049 folgende Trennungszahl: (Formel) gegenüber. Wir nehmen an,
050 daß a und b zwei verschiedene, nicht benachbarte Ecken von G sind.
051 Es sei T eine Teilmenge der Eckenmenge von G. Wir sagen dann,
052 daß a und b durch T getrennt werden, wenn T weder a
053 noch b enthält und jeder (Formel)-Weg von G die Menge T (in
054 mindestens einer Ecke) trifft. Es ist klar, daß a und b zum
055 Beispiel durch die Menge (Formel) getrennt werden. Ist jedes T, das
056 a und b trennt, unendlich, so setzen wir (Formel). Gibt es dagegen ein
057 endliches T, das a und b trennt, so existiert natürlich auch ein
058 solches T mit einer minimalen Eckenzahl (0 eingeschlossen). Wir
059 nennen dann diese Minimalzahl die Trennungszahl (Formel) von a und b
060 (in G). Wir können nun formulieren: Mengerscher Satz:
061 Sind a und b zwei verschiedene, nicht benachbarte Ecken
062 eines Graphen G, so ist die Verbindungszahl von a und b gleich
063 der Trennungszahl von a und b, in Zeichen: (Formel). Beweis
064 (nach T. Grünwald[ 52 ]): Zunächst bemerken wir,
065 daß der Satz trivial ist, wenn a und b in zwei verschiedenen
066 Komponenten von G liegen, da in diesem Fall (Formel) folgt. Wir
067 können also annehmen, daß a und b durch mindestens einen Weg
068 verbunden sind. Ferner stellen wir fest, daß (Formel) sein muß, da
069 jedes (Formel)-trennende T auf jedem Weg eines jeden kreuzungsfreien
070 Wegsystems je mindestens eine Ecke, also insgesamt mindestens
071 soviele Ecken besitzt, wie das Wegsystem Wege enthält. Man
072 habe nun n kreuzungsfreie (Formel)-Wege: (Formel) in G (Formel). Die Idee
073 des folgenden Beweises ist, daß man entweder a und b durch n
074 Ecken trennen kann, woraus nach (1) und (2) (Formel) folgt und der
075 Beweis vollendet ist, oder aber, daß ein System von (Formel)
076 kreuzungsfreien (Formel)-Wegen in G existiert, woraus mittels
077 Iteration sich entweder einmal mit wachsendem n die Vollendung des
078 Beweises oder nach (Formel) ergibt. Im letzten Fall erhalten wir
079 aus (1) (Formel). Zur Durchführung des Beweises setzen wir: (Formel).
080 Wir sagen von zwei verschiedenen Ecken (Formel) und (Formel) von H, daß
081 (Formel) niedriger als (Formel) oder auch (Formel) höher als (Formel)
082 liegt, in Zeichen: (Formel), wenn (Formel) und (Formel) beide auf demselben (Formel)
083 von (2) liegen und die Ecke (Formel) auf diesem (Formel) von a aus gesehen,
084 hinter der Ecke (Formel) liegt. Ferner bedeute (Formel) immer einen Weg in
085 G, der zwei Ecken (Formel) und (Formel) von H verbinden und sonst ganz
086 außerhalb von H verlaufen soll. Eine Folge von Wegen: (Formel)
087 heiße eine Bh Kette von (Formel) nach (Formel), wenn für jedes (Formel) der
088 Anfangspunkt (Formel) von (Formel) niedriger als der Endpunkt (Formel) von (Formel)
089 liegt, d. h. (Formel) gilt (Figur 21). Sind (Formel) und (Formel) zwei
090 Ecken von H, so sagen wir, daß (Formel) von (Formel) aus erreichbar
091 ist, wenn es eine Kette von (Formel) nach (Formel) gibt. Im folgenden
092 werden wir nur Ketten benötigen, die von (Formel) ausgehen. Wir
093 werden daher von jetzt ab bei den Ketten den Zusatz " von (Formel) aus "
094 fortlassen. Wir unterscheiden dann die beiden Fälle:
095 Die Ecke b ist 1.erreichbar, 2.nicht erreichbar.
096 Behandeln wir zunächst den Fall 2. Existiert auf einem (Formel) von
097 (2) eine von a verschiedene erreichbare Ecke, so gibt es auch eine
098 solche am höchsten auf (Formel) gelegene Ecke (Formel). Ist dagegen keine
099 von a verschiedene Ecke auf (Formel) erreichbar, so bedeute (Formel) die
100 unmittelbar auf den Anfangspunkt a folgende Ecke von (Formel). Wir
101 behaupten, daß a und b durch die Ecken (Formel) getrennt werden. Denn
102 zunächst bemerken wir, daß diese Ecken von a und b verschieden
103 sind, da b nicht erreichbar ist und a und b nicht benachbart sind.
104 Daher wird jeder Weg (Formel) von (2) durch (Formel) in zwei (echte)
105 Wegstücke zerlegt, in ein Anfangsstück (Formel) von a nach (Formel) und
106 ein Endstück (Formel) von (Formel) nach b. Würde ein (Formel)-Weg W keine
107 Ecke von (3) treffen, so gäbe es auf W eine (von a aus gesehen)
108 letzte gemeinsame Ecke (Formel) mit (Formel) und hinter (Formel) eine erste
109 gemeinsame Ecke (Formel) von W mit (Formel). Liegt (Formel) etwa auf (Formel) und (Formel)
110 etwa auf (Formel), so erhielte man aber mittels der Kette von a nach (Formel)
111 und desjenigen Wegstückes von W, das von (Formel) nach (Formel) läuft,
112 eine Kette von a nach (Formel) mit (Formel) im Widerspruch dazu, daß (Formel)
113 die höchste erreichbare Ecke auf (Formel) sein sollte. Damit ist der
114 Fall 2 erledigt. Kommen wir zum Fall 1. Da b erreichbar ist,
115 existiert eine Kette: (Formel) von a nach b (Formel). Wir werden zeigen,
116 daß man die Gliederzahl l der Kette (4) schrittweise auf (Formel)
117 herabdrücken kann. Dann ist aber der Beweis vollendet, da der
118 eine Weg der Kette mit den n kreuzungsfreien Wegen offenbar ein
119 System von (Formel) kreuzungsfreien Wegen bildet. Nehmen wir nun an,
120 daß die Kette (4) mindestens zwei Glieder besitzt. Zunächst
121 stellen wir fest, daß die Gliederzahl der Kette (4) verkleinert
122 werden kann, wenn sich zwei Wege (Formel) und (Formel) in einer inneren Ecke,
123 d. h. in einer von den Endpunkten dieser Wege
124 verschiedenen Ecke treffen. Denn gilt etwa (Formel), so können wir in
125 (Formel) einen Weg (Formel) von (Formel) nach (Formel) finden. Dieser Weg (Formel) könnte
126 in (4) anstelle der Wege (Formel) gesetzt werden, womit die Kette (4)
127 verkürzt wäre. Wir können also annehmen, daß die Wege der
128 Kette (4) kein inneren Ecken gemeinsam haben. Die Wege von (2)
129 seien so numeriert, daß der Endpunkt (Formel) von (Formel) auf (Formel) liegt.
130 Betrachten wir das Anfangsstück (Formel) von (Formel). Wir können weiter
131 annehmen, daß kein Anfangspunkt oder Endpunkt von (Formel)
132 auf (Formel) liegt, da wir sonst wiederum die Kette (4) verkürzen
133 könnten. Nach diesen Vorbemerkungen läßt sich der Beweis nun
134 rasch zu Ende führen. Denn wegen (Formel) liegt (Formel) auf (Formel). Für
135 (Formel) gibt es nach passender Numerierung der Wege von (2) nur zwei
136 Fälle: (Formel) oder (Formel). In dem ersten Fall können wir außerdem
137 (Formel) annehmen, da wir sonst in (4) den Weg (Formel) streichen könnten.
138 Wir ersetzen nun (2) durch: (Formel) und (4) durch: (Formel).
139 Offenbar ist ((Formel)) ein (neues) System n kreuzungsfreier (Formel)-
140 Wege. Ferner erfüllt ((Formel)), wie man mit den Vorbemerkungen
141 leicht prüft, die Bedingungen einer Kette für ((Formel)). Diese
142 Kette ist aber (um ein Glied) kürzer geworden als (4).
143 Hiermit ist der Mengersche Satz bewiesen. Es sei
144 darauf hingewiesen, daß der Mengersch Satz (sogar)
145 allgemein für Graphen mit Mehrfachkanten und Schlingen gilt (vgl.
146 Definition 1), da das Vervielfältigen von Kanten und das
147 Anbringen von Schlingen in einem Graphen auf die Verbindungs
148 zahlen und Trennungszahlen keinen Einfluß haben. Besonders
149 interessant ist eine bestimmte Dualisierung des Menger
150 schen Satzes, die darin besteht, daß man die Kanten von G als
151 Ecken eines neuen Graphen (Formel) auffaßt und zwei Ecken von (Formel)
152 genau dann durch eine Kante (von (Formel)) verbindet, wenn sie (als
153 Kanten von G aufgefaßt) in G benachbart sind. Übrigens heißt
154 (Formel) (nach dem Englischen) der Interchange Graph von G.
155 Sinngemäß ersetzen wir in der Definition der Verbindungszahl das
156 Wort " kreuzungsfrei " durch das Wort " kantendisjunkt " und in
157 der Definition der Trennungszahl " trennende Eckenmenge " durch
158 " trennende Kantenmenge ". In dieser dualen Auffassung versteht
159 man daher unter der Verbindungszahl bzw. Trennungszahl
160 von a und b (in G) die maximale Anzahl von Wegen, die
161 ein System kantendisjunkter (Formel)-Wege von G enthalten
162 kann, in Zeichen: (Formel), beziehungsweise die Minimalzahl von
163 Kanten in G, durch die a und b getrennt werden in dem Sinne,
164 daß jeder (Formel)-Weg mindestens eine dieser Kanten
165 enthält, in Zeichen: (Formel). Dann gilt: Mengerscher
166 Satz (Dualform):. Es seien a und b zwei verschiedene
167 Ecken eines Graphen G (Mehrfachkanten und Schlingen zugelassen).
168 Dann ist die Maximalzahl (0 und (Formel) eingeschlossen)
169 kantendisjunkter (Formel)-Wege von G gleich der Minimalzahl a und b
170 trennender Kanten von G, in Zeichen: (Formel). Beweis:
171 Offenbar können wir voraussetzen, daß G keine Schlingen
172 enthält. Wir betrachten den Interchange-Graphen (Formel) zu G.
173 Man beachte, daß (Formel) keine Mehrfachkanten enthält, auch dann
174 nicht, wenn G solche Kanten besitzen sollte. Man adjungiere noch
175 zwei (neue) Ecken (Formel) und (Formel) zu (Formel) und verbinde (Formel) und
176 entsprechend (Formel) mit denjenigen Ecken von (Formel), die (als Kanten
177 von G aufgefaßt) mit der Ecke a bzw. b inzidieren. Man
178 braucht dann nur auf diesen Graphen und seine Ecken (Formel) und (Formel) den
179 Satz anzuwenden und das Ergebnis sinngemäß auf G zu
180 übertragen, um die obige Behauptung von abzulesen. Im
181 folgenden soll der Mengersche Satz, und zwar und,
182 auf gerichtete Graphen übertragen werden. Wie man aus dem
183 letzten Teil dieses Paragraphen ersehen wird, ist der Satz in
184 diesem Fall für Anwendungen besonders wichtig. Wir müssen zuvor
185 die im Mengerschen Satz für ungerichtete Graphen
186 enthaltenen Begriffe auf gerichtete Graphen sinngemäß übertragen.
187 Wir bezeichnen gerichtete Graphen, um sie besser von den
188 (ungerichteten) Graphen G unterscheiden zu können, mit (Formel). Es
189 sei (Formel) ein gerichteter Graph mit der Eckenmenge E und der
190 (gerichteten) Kantenmenge K. Wir wollen auch zulassen, daß (Formel)
191 Mehrfachkanten enthält. Ist T eine Teilmenge von E, so
192 bezeichnen wir die Menge derjenigen Kanten von (Formel), deren
193 Endpunkte +Spitzen) in T und deren Anfangspunkte in E-T
194 liegen, mit (Formel). Entsprechend sei die Menge derjenigen Kanten
195 von (Formel), deren Anfangspunkte in T und deren Endpunkte in E-
196 T liegen, mit (Formel) bezeichnet. Es sei (Formel) eine Ecke von (Formel).
197 Man versteht dann unter dem Innengrad bzw.
198 Außengrad von (Formel) (in G), in Zeichen (Formel) bzw. (Formel), die
199 Anzahl (0 und (Formel) zugelassen) derjenigen Kanten von (Formel), die (Formel)
200 als Endpunkt (Spitze) bzw. als Anfangspunkt haben, also:
201 (Formel) und (Formel). Offenbar gilt immer: (Formel). Ein Weg ((Formel)) von G
202 heißt eine Bahn von (Formel) (von (Formel) nach (Formel)), wenn der
203 Weg immer im Sinne der orientierten Kanten von (Formel) läuft, das
204 soll heißen, wenn (Formel) stets der Anfangspunkt und (Formel) der Endpunkt
205 der Kante (Formel) ist ((Formel)). Wir definieren als Verbindungszahl:
206 (Formel) bzw. (dual) (Formel) von a nach b in (Formel) die maximale
207 Anzahl kreuzungsfreier bzw. kantendisjunkter Bahnen, die in
208 (Formel) von a nach b gezogen werden können. Entsprechend sagen wir von
209 einer Teilmenge (Formel) der Eckenmenge von (Formel) beziehungsweise von
210 einer Teilmenge (Formel) der Kantenmenge von (Formel), daß sie a und b
211 trennt, wenn jede Bahn von a nach b in (Formel) mindestens eine Ecke
212 bzw. Kante von (Formel) bzw. (Formel) enthält. Es sei darauf
213 hingewiesen, daß hierbei auf die Reihenfolge von a und b wohl zu
214 achten ist. Man versteht und der Trennungszahl: (Formel) bzw.
215 (dual) (Formel) von a nach b in (Formel) die minimale Ecken
216 zahl bzw. Kantenzahl solcher trennenden (Formel) bzw. (Formel).
217 Dann gilt: Mengerscher Satz für gerichtete Graphen:
218 sind a und b zwei verschiedene, durch keine Kante von a
219 nach b verbundene Ecken eines gerichteten Graphen (Formel), so ist die
220 Maximalzahl kreuzungsfreier Bahnen von a nach b in (Formel) gleich der
221 Minimalzahl trennender Ecken von a und b (trennend hier verstanden
222 für alle Bahnen von a nach b), in Zeichen: (Formel). Der
223 Beweis von kann fast wörtlich im Beweis von nachgelesen
224 werden, wenn darin überall das Wort Weg durch das Wort Bahn
225 ersetzt wird. Auch der Satz gilt analog für gerichtete
226 Graphen, wenn diese beiden Wörter miteinander ausgetauscht werden.
227 Wir können daher die nochmalige Nachprüfung des Beweises von
228 auf seine Gültigkeit für dem Leser überlassen.
229 Mengerscher Satz für gerichtet Graphen (Dualform):.
230 Sind a und b zwei verschiedene Ecken eines gerichteten Graphen (Formel),
231 so ist die Maximalzahl kantendisjunkter Bahnen von a nach b in
232 (Formel) gleich der Minimalzahl trennender Kanten von a und b (trennend
233 hier verstanden für alle Bahnen von a nach b), in Zeichen:
234 (Formel). Beweis: Ähnlich wie im Beweis von wenden wir
235 einen Kunstgriff an, indem wir (Formel) zunächst dualisieren. Hierzu
236 bilden wir den folgenden (gerichteten) Interchange-Graphen
237 (Formel) zu (Formel): Man betrachte jede Kante von (Formel) als eine Ecke von
238 (Formel) und verbinde zwei Ecken (Formel) und (Formel) von (Formel) genau dann durch
239 eine Kante von (Formel), und zwar in Richtung von (Formel) nach (Formel), wenn
240 diese Ecken (als Kanten von (Formel) aufgefaßt) in einer Ecke (Formel)
241 (von (Formel)) zusammenstoßen und (Formel) und (Formel) gilt. Wir adjungieren
242 dann noch zwei ' neue) Ecken (Formel) und (Formel) zu (Formel) und ziehen (neue)
243 Kanten von (Formel) aus nach denjenigen Ecken von (Formel), die (als
244 Kanten von (Formel) aufgefaßt) in (Formel) liegen, und entsprechend ziehen
245 wir von allen Ecken von (Formel) aus, die (als Kanten von (Formel)
246 aufgefaßt) in (Formel) liegen, (neue) Kanten nach (Formel). Wendet man
247 auf diesenGraphen den Satz an, so kann man ähnlich wie im
248 Beweis von die Behauptung von ablesen.
Zum Anfang dieser Seite