Graphentheorie (M05) Konsultation am 17.2.2010 ab 14:00 in Rh39/733. Wintersemester 2009/10 (F. Göring) SWS: 4V2Ü Vorlesung:  Di, 13:30-15:00, 2/D201, aber nicht am 26.1.2010 Fr, 9:15-10:45 2/D201 Übung: Di, 7:30-9:00 Rh39/733 Prüfungen:  Mo, 22.2.2010 - Fr, 26.2.2010 (mündlich)

Kurzbeschreibung

Literatur

Wichtige Definitionen und Sätze

Übungen

1. Sei V_i die Menge aller Färbungen f von der Menge aller m-elementigen Teilmengen von M_i:={1,2, ..., m+i-1} mit k Farben derart. G* sei der Graph dessen Knotenmenge die Vereinigung aller V_i (i=0,1,2,...) ist und dessen Kanten nur zwischen Knoten f aus V_i und f' aus V_i+1 verlaufen und zwar genau dann, wenn f eine Einschränkung von f' ist.

a) Man bestimme |V_i| in Abhängigkeit von i.

b) Wieviele Nachbarn hat ein Knoten f aus V_i in V_i+1?

c) Betrachten wir einen unendlichen Weg f₀f₁f₂... in G*, wobei für alle Indizes i der Knoten f_i aus der Partition V_i stammt. Dieser erzeugt eine Färbung aller m-elementigen Teilmengen der natürlichen Zahlen. Welche Farbe erhält eine m-elementige Teilmenge T?

d) Wir betrachten den Untergraphen G von G* induziert durch alle Knoten v von G, welche Färbungen einer Menge X derart sind, dass keine r-elementige Teilmenge von X bezüglich der Färbung v einfarbig ist. Sei f ein Knoten von G aus V_i (i>0). Wieviele Nachbarn (bzgl. G) hat f in V_i-1?

1. Man weise nach, dass t_r-1(n)<=n²(r-2)/(2r-2) gilt.
2. Man bestimme passende Parameter für den Beweis des Satzes von Erdös und Ramsey.
3. Man finde einen dreiecksfreien Graphen mit 5 Knoten, dessen Komplement auch dreiecksfrei ist.
4. Man verbessere die Schranke für n im Beweis des Satzes von Ramsey, ohne die Struktur des Beweises zu ändern.

1. Man zeige, dass ein K_m,n nach Löschung von höchstens (m-s)(n-t)/s Kanten stets noch einen K_s,t als Untergraphen enthält.
2. Man finde zu einem Wald W eine in n lineare obere Schranke für ex(n,W).
3. Gibt es einen Graphen, der kantenmaximal ohne K₃-Minor ist, aber nicht extremal?
4. Zeige: Für k>1 enthält jeder Graph mit n Knoten und wenigstens (k-1)n Kanten jeden Baum mit k Kanten als Untergraphen.

1. Man bestimme ex(n,P₂)! Wie sehen die Extremalgraphen aus?

Zusatz: Man bestimme ex(n, K_1,r)! Wie sehen die Extremalgraphen aus?

2. Man bestimme ex(n,K_r) in Abhängigkeit von n und r. Wie sehen die Extremalgraphen genau aus?
3. Man weise nach, dass der Grenzwert des Verhältnisses der Maximalzahl der Kanten eines Graphen ohne K_r mit n Knoten zur Anzahl der Kanten eines K_n mit wachsendem n gegen (r-2)/(r-1) geht.

1. Zeige die Hadwiger-Vermutung für k=4.
2. Zeige, dass - falls G aus G₁ und G₂ gemäß (iii) der "Definition k-konstruierbar" gewonnen wurde, eine zulässige k-Färbung von G eine zulässige k-Färbung von G₁ oder eine solche von G₂ erzwingt.
3. Sei G ein Graph mit mindestens einer Kante, dessen Kanten bis auf eine beliebigen Kante mit Delta(G)+1 Farben zulässig gefärbt werden können. Die Zahl k sei maximal so gewählt, dass es einen Knoten x, verschiedene Knoten y₁, y₂, ..., y_k in der Nachbarschaft von x, sowie eine Färbung c von G-{x,y₁} in den Farben 1,2,...,Delta(G)+1 derart gibt, dass c(x,y_i)=i-1 für jedes i aus {2,...,k} gilt, um x die Farbe Delta(G)+1 fehlt und für alle i aus {1,2,...,k} um y_i die Farbe i fehlt.  Konstruieren Sie  eine zulässige Kantenfärbung c' für G mit den Farben 1,2,...,Delta(G)+1!
4. Gibt es einen polynomialen Algorithmus, der die Kanten eines Graphen G zulässig mit den Farben {1,2,...,Delta(G)+1} färbt?

1. Zeige, dass jeder dreifach zusammenhängende ebene Graph mit Minimalvalenz 4 ein Land besitzt, dessen Rand höchstens 4 Ecken hat.
2. Wieviele Knoten der Valenz 5 hat ein 3-zshgd. ebener Graph ohne Knoten der Valenz 3 oder 4 mindestens?
3. Beweise den Fünffarbensatz!
4. Ein Färbealgorithmus färbe beginnend mit einem Knoten und auf Nachbarn schon gefärbter Knoten fortsetzend jeden Knoten mit der kleinsten Farbe, die nicht schon einer seiner Nachbarn erhalten hat. Konstruiere einen ebenen Graphen G und eine Reihenfolge seiner Knoten v1,v2, ... , vn derart, dass dieser Algorithmus diese Reihenfolge verwenden kann und mindestens 5 Farben benötigt.
5. Ist jeder Dreiecksfreie, 3 zshgd. ebene Graph 3-färbbar?

1. Sei M eine Menge k-zusammenhängender Graphen, G ein kantenmaximaler  Graph mit mehr als k Knoten ohne topologischen Minor in M und S ein minimaler Trenner in G bestehend aus weniger als Knoten. Für welche k ist der durch S induzierte induzierte Untergraph sicher vollständig?
2. Wieviele Graphen (und welche) liegen im Zyklenraum des K_3,3?
3. Beweisen sie, dass der Zyklenraum des K₅ keine schlichte Basis hat.
4. Finden Sie zwei zueinander isomorphe ebene Graphen deren duale Graphen nicht isomorph zueinander sind!

1. Sei M eine Menge k-zusammenhängender Graphen, G ein nicht k-zusammenhängender Graph mit mehr als k Knoten ohne Minor in M aber mit möglichst vielen Kanten und S ein Trenner in G. Welchen Graphen induziert S in G?
2. Beweisen Sie, dass jeder 3fach zusammenhängende planare Graph so in die Ebene gezeichnet werden kann, dass alle Länder bis auf eines konvex sind!
3. Welche Struktur ist dafür verantwortlich, dass ein Graph G einen andern Graphen H als Minor hat?
4. Fassen Sie den Algorithmus zum Finden einer Einbettung, dessen Grundzüge am vorigen Dienstag angerissen wurde, zusammen!
5. Beweisen Sie: Ein Graph, der einen K_3,3 oder K₅ als Minor hat, hat auch einen K_3,3 oder K₅ als topologischen Minor!

1. Beweisen Sie das Kreuzungslemma!
2. Beweisen Sie das Brückenlemma!
3. Beweisen Sie, dass jede ebene Triangulation (ebener Dreiecksgraph) 2-zusammenhängend ist!
4. Beweisen Sie, dass der Petersen-Graph nicht planar ist!

1. Beweise, das die Länder einer Landkarte sich mit vier Farben färben läßt, wenn der aus den Ländergrenzen bestehende Graph (die Knoten sind Drei- und Mehrländerecke) einen Hamiltonkreis besitzt.
2. Beweise, dass die Toughness eines Graphen stets mindestens genauso groß ist, wie seine topologische Toughness.
3. Beweise, dass der Satz von Ore (auf dem die Idee der hamiltonschen Hülle basiert) scharf ist.
4. Beweise, dass der Satz von Chvatal (für die Existenz eines Hamiltonkreises hinreichende Bedingung an Valenzen) scharf ist.
5. Beweise, dass der Satz von Chvatal und Erdős scharf ist.

1. Man beweise die Defektversion des 1-Faktorsatzes von Tutte aus dem 1-Faktorsatz selbst: Ist für jede Teilmenge S der Knotenmenge eines Graphen G die Anzahl der ungeraden Komponenten von G-S höchstens um d größer als die Anzahl der Knoten in S, so gibt es in G ein Matching, welches alle bis auf d Knoten überdeckt.
2. Der Satz von Mader aus der Vorlesung gilt nur für induzierte Untergraphen U von G. Was muss ergänzt werden, damit er für alle Untergraphen gilt?
3. Man beweise die Zweipunktversion des Satzes von Menger mittels des Satzes von Mader.
4. Man beweise, dass der Petersongraph  zu  jedem kantenlosen Untergraphen U mindestens so viele U-Wege besitzt, wie U Knoten enthält.
5. Ist der Petersongraph hamiltonsch?

1. Man beweise die Kantenversion des Satzes von Menger unter Nutzung des Line-Graphen L(G) vermöge der normalen Version.
2. Man beweise die Defektversion des Heiratssatzes:
   Sei G ein endlicher paarer Graph mit Partitionsklassen A und B. Gibt es in der Nachbarschaft einer beliebigen Teilmenge von A nie mehr als k Elemente weniger als in der Teilmenge selbst, so lässt sich A bis auf k Elemente durch ein Matching in G überdecken.
3. Man bestimme aus dem Beweis des Satzes von Euler in der Vorlesung einen Algorithmus zum Auffinden eines Eulerzyklus, welcher zusätzlich bei nichteulerschen Graphen einen Grund für das Fehlen des Eulerzyklus liefert.
4. Man beweise den Satz von Euler durch Betrachtung eines längsten geschlossenen Eulerzuges.
5. Sei G ein kantenmaximaler Graph ohne 1-Faktor und S eine Menge von Knoten aus G mit |S|<u(G-S).
   Für einen Knoten s aus S bestimme man die Nachbarschaft von s in G.
   Man bestimme die Nachbarschaft eines Knotens v in G, wenn v aus einer Komponente C von G-S stammt.

1. Man beweise die Kantenversion des Satzes von Menger mittels Löschen einer Kante.
2. Man weise nach, dass aus Korollar 1 bzw. Korollar 2 des Satzes von Menger jeweils der Satz von Menger folgt.
3. Welche Zusammenhangszahl hat der K_n?
4. Man beweise den Satz von Whitney unter Nutzung des Satzes von Menger!
5. Man beweise: In G ist der Zusammenhang zwischen a und B mindestens gleich dem Minimum von Mächtigkeit von B und Zusammenhangszahl von G.

1. Ein Graph ist die disjunkte Vereinigung seiner Komponenten.
2. Zwei Knoten a und b eines Graphen G liegen genau dann in einer Komponente von G, wenn sie durch einen a-b-Weg in G verbunden sind.
3. Jeder endliche Baum hat genau einen Knoten mehr als Kanten.

4. ... kantenmaximal kreisfrei ist.
5. ... kreisfrei ist, und höchstens einen Knoten mehr als Kanten hat.

Algorithmen

• Baumsuche (pdf)

alte Skriptschnipsel

Aufgaben WS 2005/2006

Aufgaben WS 2008/2009