Transcription
Elemente der GraphentheorieSchnupperkurs Sommersemester 2015Prof. Dr. Andreas KirschInstitut für Angewandte und Numerische MathematikKarlsruher Institut für Technologie (KIT)5. Mai 2015Literaturliste über Graphentheorie (nur deutsch)M. Aigner: Graphentheorie. Teubner Studienbuch, 1984.G. Biess: Graphentheorie. Verlag Harri Deutsch, 1979.R. Bodendiek, R. Lang: Lehrbuch der Graphentheorie, Band 1. Spektrum Akad. Verlag,1995.J. Clark, D.A. Holton: Graphentheorie. Spektrum Akad. Verlag, 1994.R. Diestel: Graphentheorie. Springer, 2000.W. Dörfler, J. Mühlbacher: Graphentheorie für Informatiker. Sammlung Göschen, de Gruyter Verlag 1973.F. Harary: Graphentheorie. Oldenbourg Verlag, 1974.G. Nägler, F. Stopp: Graphen und Anwendungen. Teubner Verlagsgesellschaft, 1996.K. Neumann: Operations Research Verfahren Bd. III (Graphentheorie, Netzplantechnik).Karl Hauser Verlag, 1975.H. Noltemeier: Graphentheorie. deGruyter Lehrbuch, 1976.L. Volkmann: Graphen und Digraphen. Springer Verlag Wien, New York, 1991.R.J. Wilson: Enführung in die Graphentheorie. Vandenhoeck & Ruprecht, 1972.1
Inhaltsverzeichnis1 Einführung32 Eulersche Wege83 Graphen und Matrizen152
1EinführungIn dieser Schnuppervorlesung werden wir nicht nur Elemente der Graphentheorie besprechen, sondern auch typische Vorgehensweisen der höheren“ Mathematik kennenlernen.”Dabei kommen streng mathematisch formulierte Definitionen und Sätze vor, Bezeichnungen und das Führen von Beweisen.Wir beginnen zunächst mit einigen Beispielen für Graphen.Beispiele 1.1(a) In einer Hockeyliga gibt es acht Mannschaften, die wir mit S, T, U, V, W, X, Y und Zbezeichnen. Nach einigen Wochen der Saison haben die folgenden Spiele stattgefunden:S hat gegen X und Z gespielt,T hat gegen W, X und Z gespielt,U hat gegen Y und Z gespielt,V hat gegen W und Y gespielt,W hat gegen T, V und Y gespielt,X hat gegen S und T gespielt,Y hat gegen U, V und W gespielt undZ hat gegen S, T und U gespielt.Wir können diese Situation durch das folgende Diagramm veranschaulichen, wobei dieMannschaften durch (große) Punkte dargestellt werden und zwei solcher Punkte durcheine Linie verbunden sind, wenn die zugehörigen Mannschaften gegeneinander gespielthaben.S Z Y T U V HHHH HHX W(b) Es seien n Gäste zu einem Festessen eingeladen. Der Gastgeber möchte vermeiden,dass Gäste nebeneinander sitzen, die sich nicht mögen. (Wir stellen uns dies an einemrunden Tisch vor.)3
P2P1 XXX P1 HHH HHP H HH 5 H PP2 H6 H H BB H P7PH10 B BB BB P8P9 BB B@@ B P3 @XXX P3 @ @ @P9 @ @@ @@@ P8 H @ PH @5 HH@ @H H P7P4P4P6Hier werden zwei Personen genau dann verbunden, wenn es keine Bedenken gibt, sie nebeneinander zu setzen. Die Ausgangsfrage ist äquivalent zur Frage, ob es einen geschlossenenKantenzug in diesem Graphen gibt, der alle Personen genau einmal durchläuft“. Ver”suchen Sie es bei den obigen Beispielen! (Links geht’s, rechts nicht!) Solche Kantenzügeheißen geschlossene Hamiltonsche Wege. Beim folgenden sogenannten Petersenschen Graphen gibt es auch keinen geschlossenen Hamiltonschen Weg wie wir nochsehen werden.P1 H HH P6 HHH P5 H A P2 HP10 ABBHH P7 HH A BH H A B HH A P9 B P8 HA HB@ @ B P3P4(c) Das folgende Beispiel des Königsberger Brückenproblems wird allgemein als derUrsprung der Graphentheorie angesehen. Leonard Euler veröffentlichte 1736 eine Arbeit,die dieses alte Problem löste:Die Stadt Königsberg in Ostpreußen wird von dem Fluss Pregel durchflossen, verzweigtund bildet eine Insel (den Kneiphof). Im folgenden Bild sehen Sie links einen alten Stadtplan von Königsberg mit siebeb Brücken. Es war nun die Frage, ob es möglich ist, einenWeg durch Königsberg zu finden, der jede Brücke genau einmal überquert. Rechts istdie Situation in einen Graphen übersetzt worden. Die vier Stadtgebiete“ R1 , R2 , R3 ,”R4 werden durch Ecken eines Graphen repräsentiert, die sieben Brücken b1 , . . . , b7 durchverbindende Kanten:4
R4 b1 b3b2R3 b5b7 R2b6 b4%R1Wir können uns schnell überlegen, dass so ein Weg nicht möglich ist: Angenommen, esgäbe einen solchen Weg. Betrachten wir dann z.B. das Gebiet R1 . Es ist über 3 Brückenmit den anderen Gebieten verbunden. Da alle Brücken genau einmal durchlaufen werden,muss R1 Start- oder Endpunkt des Weges sein! Genau das gleiche Argument gilt für alleanderen Gebiete, und offenbar können nicht alle Start- oder Zielpunkt sein. Daher gibt eskeinen solchen Weg.Bezogen auf den Graphen stellt sich hier also die Frage, ob es einen Weg gibt, der irgendwobeginnt und jede Kante dieses Graphen genau einmal durchläuft. Graphen, bei denendies möglich ist heißen Eulersche Graphen. Mit diesen werden wir uns im nächstenAbschnitt näher beschäftigen.(d) Bei einem Färbungsproblem ist eine Landkarte“ gegeben und es wird nach der”minimalen Anzahl der Farben gefragt, mit denen man die Länder färben kann, so dassaneinanderstoßende Länder unterschiedliche Farben haben müssen. Aneinanderstoßend“”bedeutet hier, dass sie eine echte Grenze (nicht nur einen Grenzpunkt) gemeinsam habenmüssen. Bei den folgende drei Beispielen reichen 3 Farben (numeriert mit 1, 2 und 3):123233211Bei den folgenden reichen 3 nicht, aber vier:52 1 3
1234132342Wie können wir diesen Landkarten einen Graphen zuordnen, und wie sieht das Färbungsproblem dort aus?Jedes Land entspricht einer Ecke des Graphen, und zwei Ecken des Graphen sind genaudann durch eine Kante verbunden, wenn sie eine gemeinsame Grenze haben. Dem letztenBeispiel entspricht der Graph(Man überlege sich selbst, welche Ecken hier welchem Land entsprechen.) Das Färbungsproblem geht also über in das Problem, mit möglichst wenig Farben die Ecken so zufärben, dass aneinanderstoßende Ecken ungleiche Farbe haben.Wenn man jemandem z.B. am Telefon einen Graphen schildern möchte, ist die graphische Form ungeeignet. Auch im Rechner benötigt man die Darstellung eines Graphen ingeeigneter Form. Wir brauchen eine streng mathematische Definition. Bevor wir diestun, wiederholen wir einige elementare Begriffe der Mengenlehre:Eine Menge kann explizit durch auflisten ihrer Elemente oder durch eine charakterisierende Beschreibung angegeben werden, z.B. M {4, 2, } oder M {A : A Dreieck}.Eine besondere Menge ist die sogenannte leere Menge, die kein einziges Element hat.Sie wird mit bezeichnet.Schreibweise: Wir schreiben x M , wenn x ein Element aus M ist, anderenfalls x 6 M .6
Als Beispiele können wir die folgenden Zahlbereiche nennen:N {1, 2, 3, . . .} {n : n natürliche Zahl}Z {. . . , 2, 1, 0, 1, 2, . . .} {n : n ganze Zahl}aQ { : a, b Z, b 6 0} {x : x rationale Zahl}bR {x : x reelle Zahl}Beziehungen zwischen Mengen:Zwei Mengen A und B heißen gleich, wenn sie dieselben Elemente haben.Eine Menge A heißt Teilmenge von einer Menge B, wenn jedes Element von A in Bliegt, in Zeichen: A B oder B A. Hier lassen wir ausdrücklich A B zu, also istA A.Durchschnitt, Vereinigung und (Mengen-)Differenz sind erklärt durchA BA BA\B {x : x A und x B}{x : x A oder x B}{x A : x 6 B}Durchschnitt von A und BVereinigung von A und BDifferenz oder Restmengeund erfüllen unter anderem folgende Eigenschaften.A A A,A B B A , A B B A (Kommutativgesetze) ,(A B) C A (B C) , (A B) C A (B C) (Assoziativgesetze) ,A (B C) (A B) (A C) , A (B C) (A B) (A C) (Distributivgesetze) .Ist eine (nichtleere) Menge A gegeben, so kann man damit die Menge aller Teilmengenbetrachten. Dies Menge wird Potenzmenge genannt und mit P(A) bezeichnet, also P(A) B : B A .Ist etwa A {1, 2, a}, so istP(A) , {1}, {2}, {a}, {1, 2}, {1, a}, {2, a}, A .Wir benötige die Teilmenge P2 (A) aller zwei-elementigen Teilmengen von A, im Beispiel: P2 (A) {1, 2}, {1, a}, {2, a} .Zur exakten mathematischen Definition brauchen wir noch den Funktionsvorschrift:Seien D und W Mengen. Eine Funktion (oder Abbildung) ist eine Vorschrift, die jedemx D genau ein y W zuordnet. Wir schreiben f : D W und y f (x). Die MengeD heißt Definitionsmenge von f . Die Menge W Wertemenge von f . Wir schreibenf : D Wx 7 f (x)Die Mengef (D) f (x) W : x Dheißt Bild von D unter f .7
Definition 1.2 Ein Graph besteht aus einer endlichen Eckenmenge E und einer endlichen Kantenmenge K, sowie einer Angabe, welche zwei Ecken {ê, ẽ} zur Kante k Kgehören. (Wobei ê 6 ẽ gefordert wird. Wir lassen also keine Schleifen zu.) Mathematischbefriedigender formuliert bedeutet dies, dass es eine Abbildung Ψ : K P2 (E) von Kin die Menge aller zweielementigen Teilmengen von E geben muss. Wir benutzen also dasSymbol P2 (E) für die Menge aller Teilmengen von E, die aus genau 2 Elementen besteht.Durch die Abbildung Ψ wird also jeder Kante die Menge der beiden Endpunkte zugeordnet– die verschieden sein müssen!Beispiel 1.3(a) Ein Graph kann etwa so aussehen: e5e2e4S' kS k42Sk1k3S e6&% e3e1 E {e1 , . . . , e6 },Hier istK {k1 , . . . , k4 }mit der Zuordnung Ψ : k1 {e2 , e3 }, k2 {e3 , e4 }, k3 {e3 , e4 }, k4 {e5 , e6 }.(b) Das folgende Bild stellt keinen Graph in unserem Sinne dar, da k2 nur einen Endpunktbesitzt.k2m k12 Eulersche WegeDefinitionen und BezeichnungenEin Weg ist eine Sequenz W (e1 k1 e2 k2 . . . en kn en 1 ), wobei wir abwechselnd Ecken undKanten nebeneinander schreiben (beginnend und endend mit je einer Ecke), wobei wirdarauf achten müssen, dass alle Kanten verschieden sind – nicht aber die Ecken! Mit derAbbildung Ψ können wir das so ausdrücken:1. ψ(kj ) {ej , ej 1 } für alle j 1, . . . , n, und2. ki 6 kj für alle i 6 j .8
Die Anzahl n der Kanten wird Länge des Weges genannt. Die Ecken e1 und en 1 heißenEndpunkte von W .Der Graph heißt zusammenhängend, wenn es zu jedem Paar ê, ẽ E einen WegW (e1 k1 . . . en kn en 1 ) gibt mit e1 ê und en 1 ẽ.Der Weg heißt geschlossen (oder Kreis oder Zyklus), wenn e1 en 1 , andernfalls offen.Ein (offener bzw. geschlossener) Weg W (e1 k1 . . . kn en 1 ) heißt ein (offener bzw. geschlossener) Eulerscher Weg, wenn unter den k1 , . . . , kn alle Kanten aus K vorkommen,d.h. wenn K {k1 , . . . , kn }. Der Graph heißt Eulerscher Graph, wenn es überhaupteinen geschlossenen Eulerschen Weg gibt.Ein Weg (e1 k1 . . . kn en 1 ) heißt ein Hamiltonscher Weg, wenn(i) alle ei verschieden sind (bis auf eventuell e1 en 1 ) und(ii) E {e1 , . . . , en 1 }, d.h. wenn unter den ei alle Ecken des Graphen (genau einmal)vorkommen.Der Grad einer Ecke ist die Anzahl der anstoßenden Kanten. Wir schreiben hierfür d(e)(d für degree“).”Zu jeder Ecke e können wir dann die Menge Z(e) der Ecken betrachten, die mit e durcheinen Weg verbunden sind. Diese Eckenmenge heißt die zu e gehörige Zusammenhangskomponente oder auch Erreichbarkeitsmenge.Offensichtlich zerfällt die Eckenmenge E in eine endliche Anzahl von Zusammenhangskomponenten. Der folgende Graph besteht aus drei Komponenten. B PPP BP P BPP B PP B B B BB Ein Unterschied der Mathematik zu den Naturwissenschaften oder gar Geisteswissenschaften ist, dass wir hier, ausgehend von den präzisen Definitionen, Aussagen beweisen können. Wir wissen dann 100prozentig, dass eine Aussage richtig ist – vorausgesetztnatürlich, dass wir die Schlussfolgerungen der Logik akzeptieren. Wir wollen dafür einigeBeispiele bringen:Satz 2.1 Für jeden Graphen G mit n Eckenmenge E {e1 , . . . , en } und m Kanten gilt:nXd(ei ) 2m .i 19
Hier haben wir das in derPMathematik und allen Natur- und Ingenieurwissenschaftenbenutzte Summensymbolbenutzt. Haben wir Zahlen (oder andere Größen, die durchnummeriert werden), wie etwa x1 , x2 , . . . , x20 , so schreiben wir20Xxi x1 x2 · · · x20 .i 1Der Summationsindex“ i in”20Pbeginnt also bei 1 und wird hochgezählt bis 20. (Eri 1kann auch ein anderer Buchstabe als i sein, oft j, k oder n.) Damit ist alsonPd(ei ) einei 1Kurzform von d(e1 ) d(e2 ) · · · d(en ).Beweis: Jede Kante berührt zwei Ecken, wird also beim Zählen der Grade sowohl beidem einen wie auch bei dem anderen Eckpunkt mitgezählt.Etwas genauer könnte man so diskutieren: In Gedanken belegen wir jede Kante miteiner Richtung (so etwas heißt gerichteter Graph). Dann hat jede Kante genau einenAnfangspunkt und genau einen Endpunkt. d (e) sei die Anzahl der aus der Ecke ehinauslaufenden“ Kanten, d (e) die der in e hineinlaufenden“ Kanten. Natürlich ist””nPd(e) d (e) d (e). Außerdem istd (ei ) als Summe aller aus allen Ecken hinauslaui 1fenden Kanten genau die Anzahl m aller Kanten. (Jede Kante muss irgendwo hinauslaufennPund kann auch nicht aus mehr als einer Ecke hinauslaufen.) Daher istd (ei ) m. Genauso istnPi 1d (ei ) m undnPi 1d(ei ) nPd (ei ) i 1nPi 1d (ei ) 2m.2i 1Folgerung:In jedem Graphen gibt es eine gerade Anzahl von Ecken mit ungeradem Grad.nPBeweis: Aus dem Satz 2.1 erkennen wir, dassd(ei ) eine gerade Zahl ist, nämlich 2m.i 1Nummerieren wir jetzt die Ecken so, dass e1 , . . . , ep die Ecken mit ungeradem Grad undep 1 , . . . , en die mit geradem Grad sind, so istpXd(ei ) 2m i 1nXd(ei ) ,i p 1als Differenz zweier gerader Zahlen ebenfalls gerade. Links steht eine Summe von ungeraden Zahlen. Da diese Summe eine gerade Zahl ergibt, muss die Anzahl p derSummanden gerade sein!2Übung Ermittle die Grade in folgendem Graphen und überprüfe die Aussagen des Satzes 2.1 und der Folgerung.10
b @a @@@ @@ e f cDer folgende Satz wird beim Hauptsatz über Eulersche Grapgen eine entscheidende Rollespielen.Satz 2.2 Es sei G ein Graph, in dem Grad jeder Ecke mindestens zwei beträgt. Dannenthält G einen Zyklus (d.h. einen geschlossenen Weg).Beweis: Sei e1 eine beliebige Ecke. Wegen d(e1 ) 2 gibt es eine angrenzende Kante,deren anderes Ende wir mit e2 bezeichnen.e2 @e1 @ e3@ .Wegen d(e2 ) 2 gibt es eine weitere angrenzende Kante, deren anderes Ende wir mite3 bezeichnen. So machen wir immer weiter, bis wir (zum ersten Mal) einen Knoten entreffen, der schon einmal dran war. Dies muss irgendwann einmal passieren, da wir ja nurendlich viele Knoten haben. en 1 A AA en e3- I@@6@ e2 e1e4 @@@ - ? Dann ist also en ej mit n j, und die gewählten Kanten mit Ecken ej , ej 1 , . . . , en 1 , ejbilden einen Zyklus.211
Bevor wir den Hauptsatz über Eulersche Graphen beweisen, möchte ich kurz auf dasBeweisprinzip der vollständigen Induktion eingehen. Dies wird angewandt, wenneine Aussage A(n) für alle natürlichen Zahlen n 1, 2, 3, . . . bewiesen werden soll. DasVerfahren besteht aus zwei Teilen:1. Schritt (Induktionsanfang): Zeige die Aussage für n 1. Beweise also A(1). Diesist i.a. einfach.2. Schritt (Induktionsschritt): Nehme an, die Aussage A(n) sei für ein (beliebiges)m 1 schon bewiesen (Induktionsvoraussetzung). Beweise unter dieser Annahmedie Aussage A(m 1), also für die nächste natürliche Zahl.Dann gilt die Behauptung für alle natürlichen Zahlen n 1.Beispiel 2.3 Wir zeigen die FormelnXj j 1n(n 1)2für jedes n N ,mit vollständiger Induktion:Induktionsanfang: Sei n 1. Dann steht links 1 und rechts 1·2 1. Also ist die2Behauptung richtig für n 1.Induktionsschluß: Sei die Behauptung richtig für ein m 1. Unter dieser Voraussetzungzeigen wir die Behauptung für m 1: Es istm 1Xj j 1mXj (m 1) j 1 m(m 1) (m 1)2m(m 1) 2(m 1)(m 2)(m 1) .22Dies ist die behauptete Formel für m 1 statt m. Nach dem Induktionsprinzip gilt dieBehauptung jetzt für alle n 1, 2, 3, . . .Beispiel 2.4 (Bernoullische Ungleichung)(1 h)n 1 n h .Für jedes h 1 und alle n N gilt:Beweis durch vollständige Induktion nach n:Für n 1 ist die Behauptung sicher richtig, es gilt sogar Gleichheit.Sei die Behauptung jetzt für ein m 1 richtig. Dann ist unter Ausnutzung der Induktionsvoraussetzung:2(1 h)m 1 (1 h)m (1 h) (1 mh) (1 h) 1 mh h mh {z} 1 (m 1) h . 012
Damit ist die Behauptung auch für m 1 gezeigt. Nach dem Induktionsprinzip gilt dieBehauptung jetzt für alle n 1, 2, 3, . . . (Wo wird die Voraussetzung h 1 benötigt?)2Als drittes Beispiel beweisen wir Satz 2.1 noch einmal mit vollständiger Induktion nachder Anzahl m der Kanten:m 1: Es gibt eine Kante, und dies hat zwei Endpunkte. Daneben kann der Graph nochweitere Ecken enthalten, an denen keine Kanten anstoßen (isolierte Ecken). Da bei denennPder Grad Null ist, werden sie nicht mitgezählt. Wir erhalten alsod(ej ) 2 2m.j 1Sei der Satz jetzt für jeden Graphen mit m Kanten richtig, und sei G jetzt ein Graphmit m 1 Kanten. Wir entfernen jetzt irgendeine Kante von G. Dann erhalten wir einenneuen Graphen G0 mit der selben Eckenmenge und m Kanten. Für diesen gilt die Formelnach Induktionsvoraussetzung, alsonXd0 (ej ) 2m ,j 1wobei d0 (ej ) der Eckengrad von ej in G0 ist. Fügen wir die herausgenommene Kante wiederein, so erhöhen wir für genau zwei Ecken den Grad um 1, daher giltnXd(ej ) 2m 2 2(m 1) ,j 1und die Behauptung ist für G bewiesen.Jetzt können wir zeigen:Satz 2.5 (Hauptsatz über Eulersche Wege)Sei G ein zusammenhängender Graph. G ist genau dann Eulersch, besitzt also einengeschlossenen Eulerschen Weg, wenn der Grad jedes Knotens gerade ist.Beweis: Der Satz beinhaltet zwei Aussagen, die durch genau dann“ beschrieben werden.”Zuerst zeigen wir: Falls es einen geschlossenen Eulerschen Weg gibt, so ist jeder Gradgerade. Danach zeigen wir die Umkehrung, die schwieriger zu beweisen ist: Wenn jederGrad gerade ist, so gibt es einen geschlossenen Eulerschen Weg.Sei also zunächst W (e1 k1 . . . em km en 1 ) ein geschlossener Eulerscher Weg, der bei e1beginnt und endet, also em 1 e1 . Die Ecken {e1 , . . . , em ) müssen nicht alle verschiedensein. Sei e eine beliebige Ecke des Graphen. Da G zusammenhängend ist, so hängt an emindestens eine Kante, und diese kommt unter den {k1 , . . . , km } vor (Eulerscher Weg!).Also kommt auch e unter den {e1 , . . . , em } vor – vielleicht mehrmals, da die {e1 , . . . , em ) janicht alle verschieden sein müssen. Da an jeder Ecke ej zwei verschiedene Kanten anstoßen,so müssen an e eine gerade Zahl von Kanten anstoßen. Damit ist der Grad d(e) geradeund die erste Richtung des Satzes bewiesen.13
Jetzt nehmen wir umgekehrt an, dass der Grad jeder Ecke gerade sei. Sei wieder m dieAnzahl der Kanten im Graphen. Wir beweisen die Aussage durch vollständige Induktionnach m. Die Aussage A(m) lautet folgendermaßen: Jeder zusammenhängende Graph mithöchstens m Kanten und geradem Eckengrad enthält einen geschlossenen Eulerschen Weg.Für m 1 haben wir einen zusammenhängenden Graphen mit höchstens einer Kante, alsoe1ke2genau einer Kante (da der Graph zusammenhängend ist). Er muss so aussehen: ,nur das kann nicht sein, da die Gerade der Ecken jeweils eins sind. Daher müssen wirunseren Induktionsbeweis bei m 2 beginnen.Für m 2 muss unter der Voraussetzung, dass die Eckengrade gerade sind, der Graph soaussehen:k1 e1 e2 k2Ein Eulersche Weg für diesen einfachen Graphen ist (e1 k1 e2 k2 e1 ).Sei m 2 jetzt beliebig, und wir setzen voraus, dass jeder zusammenhängende Graphmit höchstens m Kanten und geradem Eckengrad einen geschlossenen Eulerschen Wegenthält. Sei G jetzt ein Graph mit m 1 Kanten. Da der Grad von jeder Ecke von Gmindestens 2 ist, so enthält er nach Satz 2.2 G einen Zyklus Z. (In der folgende Figur ister rot gezeichnet.) @G: @@@ @ @Z@@@@ @@ Q B QJJB QJJQQ BJJ BB JJJ Wir streichen jetzt die Kanten von Z und erhalten einen neuen Graphen G0 , der nichtmehr zusammenhängend zu sein braucht, die gleiche Eckenmenge wie G besitzt, aberweniger Kanten.14
@G0 :@@ QB QB QQQ B BB In diesem Beispiel zerfällt G0 in 5 Zusammenhangskomponenten. Jeder Eckengrad vonG0 ist wieder gerade, da von jeder Ecke von Z genau zwei Kanten entfernt worden sind.Einige Ecken können aber Grad 0 haben (wie im Beispiel). Insbesondere muss G0 nichtmehr zusammenhängend sein. Nach der Induktionsvoraussetzung gibt es in jeder Zusammenhangskomponente, deren Eckengrade 2 sind, einen geschlossenen Eulerschen Weg.Wir erhalten nun einen geschlossenen Eulerschen Weg von G folgendermaßen: Man beginne mit einem beliebigen Knoten von Z und gehe die Kante von Z entlang bis zu einemKnoten ê, der zu einer Komponente von G0 gehört mit Grad 2 für alle ihre Ecken. @@@ ê@@@ JJJ JJ @@ @@@ BQBBQQQQQQQ BB Q BBB B StartDann schließe man einen Eulerschen Weg dieser Komponente an und kommt wieder zu êzurück. Man verfolge den Zyklus Z weiter bis zur nächsten Zusammenhangskomponenten,etc. Damit ist ein geschlossener Eulersche Weg gefunden!2Man versuche, den folgenden Satz durch Rückführung auf Satz 2.5 zu beweisen!Satz 2.6 Sei G ein zusammenhängender Graph. G besitzt genau dann einen (nicht notwendig geschlossenen) Eulerschen Weg, wenn es höchstens 2 Knoten mit ungeradem Gradund sonst alle mit geradem Grad 2 gibt.3Graphen und MatrizenWie kann man einen Graphen in einem Rechner speichern und verarbeiten? Es gibt unteranderem die folgenden Möglichkeiten:15
(a) Man bildet die Matrix a11 a12 a13 · · · a1n a21 a22 a23 . . . a2n A . , . an1 an2 an3 · · · annwobei aij für i 6 j die Anzahl der Kanten angibt, die die Ecke ei mit der Eckeej verbinden. Ferner vereinbart man aii 0 für alle i. Die Matrix A heißt Adjazenzmatrix des Graphen1 . Sie ist quadratisch (hat also ebenso viele Zeilen wieSpalten) und symmetrisch, d.h. aij aji für alle i, j. Das Element aij steht inZeile i und Spalte j.(b) G habe die Ecken e1 , . . . , en und die Kanten k1 , . . . , km . Man bildet die Inzidenzmatrix B durch b11 b12 · · · b1m b21 b22b2m B . . bn1 bn2bnmwobeibij(0, wenn ei kein Endpunkt von kj ist, 1, wenn ei ein Endpunkt von kj ist.Die Inzidenzmatrix B ist i.a. nicht quadratisch!k2e3 10110102 01 2 0 1100011001010 1A 00 e1k3 e2@k4k1 @@ e4&k50 0B 11% 00 1 1Man beachte, dass uns die Summe der Elemente in der i-ten Zeile von B den Graddes Knoten ei liefert, während die Summe der Elemente in jeder Spalte 2 ist (entsprechend den 2 Enden der Kante).1von adjazere angrenzen, benachbart sein16
Ausflug in die Matrizenrechnung:Eine Matrix ist eine einfach eine rechteckige Anordung von Zahlen. Wir schreiben dafürgroße lateinische Buchstaben A, B, u.s.w. Für die Komponenten der Matrix nehmen wirden entsprechenden kleinen lateinischen Buchstaben und schreiben etwa a11 a12 a13 · · · a1n a21 a22 a23 . . . a2n A . aij i 1,.,m . .j 1,.,n. am1 am2 am3 · · · amnHier beschreibt also m die Anzahl der Zeilen und n die Anzahl der Spalten. Das Elementaij steht in Zeile i und Spalte j. Matrizen gleicher Größe können wir addieren undsubtrahieren. Wir beschränken uns im Folgenden auf quadratische Matrizen (alsom n), denn wir haben ja Adjazenzmatrizen von Graphen im Auge. Für A aij i 1,.,n und B bij i 1,.,n ist A B aij bij i 1,.,n ,j 1,.,nalso z.B.j 1,.,nj 1,.,n 1 2 30 1 21 3 5 0 1 2 3 1 0 3 2 2 .1 0 11 1 12 1 2Quadratische Matrizen können wir auch miteinander multiplizieren: Sei A aij i 1,.,n und B bij i 1,.,n . Dann ist C AB gegeben durchj 1,.,nj 1,.,n C cij i 1,.,n , wobeij 1,.,ncij ai1 b1j ai2 b2j · · · ain bnj nXaik bkj ,i, j 1, . . . , n .k 1Das Element cij , das ja in der i ten Zeile und der j ten Spalte von C AB steht,berechnet sich als Skalarprodukt der Zeile i von A und der Spalte j von B.Beispiel: 1 2 30 1 29 6 5 0 1 2 3 1 0 5 3 2 .1 0 11 1 11 2 3Wir bemerken, dass i.a. AB 6 BA ist, also z.B. 1 00 00 0 ,1 01 10 0aber 0 01 00 0 .1 11 02 017
Außerdem erkennen wir, dass ein Matrizenprodukt Null sein kann, ohne dass einer derFaktoren Null ist. (Die Multiplikation von Matrizen ist also weder kommutativ“ noch”nullteilerfrei“.) Ansonsten haben Addition und Multiplikation von Matrizen viele Eigen”schaften, die wir von der Addition und Multiplikation von Zahlen gewohnt sind. Sie bildeneinen sogenannten Ring“.”Jetzt betrachten wir uns speziell die Adjazenzmatrizen von Graphen. Die Knoten bezeichnen wir mit den Nummern 1, 2, . . . , n anstelle von e1 , e2 , . . . , en .k12' C k2 C k4 C 31 k3CC C k6 C k5 5 0 2 A2 AA 1 00 0 2 A 1 004200101001101100 00 0 2 1 10 000200102001010011100110110001100 00 1 0 0 05 0 0 0 2 0 21 3 00 01 00230030021 10 0 B.1 1Ist B (bij )i,j 1,.,5 , so ist z.B.b14 a11 a14 a12 a24 a13 a34 a14 a44 a15 a54 a12 a24 a13 a34 a15 a54a12a24a12 a24 Anzahl der Kanten von 1 nach 2Anzahl der Kanten von 2 nach 4Anzahl der Wege der Länge 2 von 1 nach 4 über Knoten 2, also:b14 Anzahl der Wege der Länge 2 von 1 nach 4b11 a211 a12 a21 a13 a31 a14 a41 a15 a51 a212 a213 a214 a215a212 Anzahl der Kantenfolgen“ der Länge 2 von 1 nach 1 über 2, nämlich”1 k1 2 k1 11 k1 2 k2 11 k2 2 k1 11 k2 2 k2 118
Analog:a213 Anzahl der Kantenfolgen“ der Länge 2 von 1 nach 1 über 3, nämlich”1 k3 2 k3 1Genauso ist a214 a215 0 und daher b11 5.Beachte: Kantenfolgen sind keine Wege, denn Kanten dürfen doppelt (und mehrfach)auftreten.Fazit: Ist A2 (bij ), so ist bij die Anzahl der Kantenfolgen der Länge 2 von Knoten inach Knoten j.Was A A2 ?(A A2 )ij aij bij Anzahl der Kantenfolgen der Längen 1 oder 2 von i nach j.Analog A3 : Sei B A2 , dann C A3 BA undcij bi1 a1j bi2 a2j . . . bin anjbik akj Anzahl der Kantenfolgen der Länge 3 von i nach j über kWir können leicht durch vollständige Induktion nach p N zeigen:Satz 3.1 Sei A Rn n die Adjazenzmatrix eines Graphen und B Ap für ein p N,B (bij ). Dann ist bij die Anzahl der Kantenfolgen der Länge p von i nach j.Bilden wir C : A A2 . . . Ap (cij ), so ist cij die Anzahl aller Kantenfolgen derLänge höchstens p von i nach j.Beweis: Induktionsanfang p 1: aij ist Anzahl der Kantenfolgen der Länge 1 (dies sindgerade die Kanten selbst) von i nach j. Damit ist die Behauptung richtig für p 1.Induktionsschluss: Sei die Behauptung schon bewiesen für p 1 statt p. Dann beschreibtmit B̃ Ap 1 (b̃ij ) das Element b̃ij die Anzahl der Kantenfolgen der Länge p 1 voni nach j. Es ist B Ap B̃A, also bij b̃i1 a1j b̃i2 a2j . . . b̃in anj , und jeder Termb̃ik akj ist das Produkt der Anzahl der Kantenfolgen der Länge p 1 von i nach k mit derAnzahl der Kanten von k nach j. Also ist b̃ik akj die Anzahl der Kantenfolgen der Längep von i nach j. Damit ist die Behauptung auch für p bewiesen. Der zweite Teil ist klar. 2Satz 3.2 Sei A die Adjazenzmatrix eines Graphen mit n Ecken und2n 1B A A . A n 1XAk (bij )i,j 1,.,n .k 1Dann ist bij 0 genau dann, wenn i und j in derselben Zusammenhangskomponenteliegen. Insbesondere ist der Graph selbst zusammenhängend genau dann, wenn bij 0 füralle i, j 1, . . . , n.19
Beweis: Wenn i und j in derselben Zusammenhangskomponenten liegen, so gibt es einenWeg, der i und j verbindet. Da höchstens n 2 Punkte echt zwischen i und j liegen, sobesitzt der Weg höchstens n 1 Kanten. Daher ist bij mindestens 1. Ist bij 0 so bedeutetdies, dass es wenigstens eine Kantenfolge (der Länge höchstens n 1) gibt, die i und jverbindet. Wir streichen in dieser Kantenfolge alle doppelten Kanten heraus und erhaltenso einen Weg von i nach j. Also liegen i und j in derselben Zusammenhangskomponenten.220
4 werden durch Ecken eines Graphen repr asentiert, die sieben Br ucken b 1;:::;b 7 durch verbindende Kanten: 4. R 4 R 3 R 2 R 1 b 1 b 2 b 7 b 6 b 5 b 3 b 4 % Wir k onnen uns schnell uberlegen, dass so ein Weg nicht m oglich ist: Angenommen, es g abe einen solchen Weg. Betrachten wir dann z.B. das Gebiet R 1. Es ist uber 3 Br ucken
