Springe zum Hauptinhalt
Professur Algorithmische und Diskrete Mathematik
Algorithmische und Diskrete Mathematik

Graphentheorie (M05)


Wintersemester 2017/18 (F. Göring)
SWS: 4V2Ü
Vorlesung: 

Do, 13:45-15:15, 2/B201
Fr, 11:30-13:00, 2/W044

Übung:

Mi, 7:30-9:00, 2/B202

Prüfungen individuell nach Absprache, mündlich im Februar 2018
LOGO

Kurzbeschreibung

Inhalt:  Einführungsvorlesung zur Graphentheorie. Es wird ein Überblick über die moderne Graphentheorie gegeben. Insbesondere werden die Themenkreise Zusammenhang, Plättbarkeit, Färbungen und Minoren behandelt.
Zielgruppe:  wo : D_InEM7, D_TM__7, D_WM__7, M_MaFM1, M_MaIn1, M_MaMa1, M_MaWM1, D_Ma__7
fak : D_TM__5, D_TM__9, D_WM__5, D_WM__9, M_MaTM1, D_Ma__9, D_Ma__5
Vorwissen:  Grundlagen der Mathematik

Opal-Kurs

Bitte schreiben Sie sich in den vermöge der Überschrift verlinkten Opal-Kurs ein, um an dieser Lehrveranstaltung teilzunehmen.

Literatur

R.Diestel:  Graphentheorie
D. B. West:  Introduction to Graph Theory
W.K.Shih, W.L.Hsu: A simple test for planar graphs
R. Thomas: Planarity in linear time
M. Voigt: List Colorings of planar graphs
C. Thomassen: Every Planar Graph Is 5-Choosable

Inhalt

Grundbegriffe
Zusammenhang
Eulerzyklen und Hamiltonkreise
Matchings
Planarität
Färbungen
Ramsey-Theorie
Extremalgraphen
Zufallsgraphen
Wohlquaisordnung

Übungsaufgaben in Vorlesung.

Alte Übungen

Übungen 2011/12 ( pdf ps )

Di 2.2.2010 (letzte Übung)

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

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

c) Betrachten wir einen unendlichen Weg f0f1f2... in G*, wobei für alle Indizes i der Knoten fi aus der Partition Vi 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 Vi (i>0). Wieviele Nachbarn (bzgl. G) hat f in Vi-1?

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

Di 26.1.2010

  1. Man weise nach, dass tr-1(n)<=n2(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.

 

Di 19.1.2010

 

  1. Man zeige, dass ein Km,n nach Löschung von höchstens (m-s)(n-t)/s Kanten stets noch einen Ks,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 K3-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.

 

Di 12.1.2010

 

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

  1. Man bestimme ex(n,P2)! Wie sehen die Extremalgraphen aus?
  2. Man bestimme ex(n,Kr) 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 Kr mit n Knoten zur Anzahl der Kanten eines Kn mit wachsendem n gegen (r-2)/(r-1) geht.

 

Di 5.1.2010

 

  1. Zeige die Hadwiger-Vermutung für k=4.
  2. Zeige, dass - falls G aus G1 und G2 gemäß (iii) der "Definition k-konstruierbar" gewonnen wurde, eine zulässige k-Färbung von G eine zulässige k-Färbung von G1 oder eine solche von G2 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 y1, y2, ..., yk in der Nachbarschaft von x, sowie eine Färbung c von G-{x,y1} in den Farben 1,2,...,Delta(G)+1 derart gibt, dass c(x,yi)=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 yi 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?

 

Di 15.12.2009

 

  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?

Di, 8.12.2009

  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 K3,3?
  3. Beweisen sie, dass der Zyklenraum des K5 keine schlichte Basis hat.
  4. Finden Sie zwei zueinander isomorphe ebene Graphen deren duale Graphen nicht isomorph zueinander sind!

 

Di, 1.12.2009

 

  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 K3,3 oder K5 als Minor hat, hat auch einen K3,3 oder K5 als topologischen Minor!

Di, 24.11.2009

  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!

Di, 17.11.2009

  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.

Di, 10.11.2009

  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?

Di,  3.11.2009

  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.

Di, 27.10.2009

  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 Kn?
  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.

Di, 20.10.2009

Man beweise:

  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.

Ein endlicher Graph ist genau dann ein Baum, wenn  er ...

  1. ... kantenmaximal kreisfrei ist.
  2. ... kreisfrei ist, und höchstens einen Knoten mehr als Kanten hat.

Algorithmen

  • Baumsuche (pdf)

alte Skriptschnipsel

Wichtige Definitionen und Sätze 2011 ( pdf ps )
Beweis des Satzes von Vizing (ps, pdf)
Vorlesungen vom 5.Januar 2006 (ps, pdf)
Vorlesung vom 12.Januar 2006 (ps, pdf)
Vorlesungen vom 19.Januar 2006 (ps, pdf)

Aufgaben WS 2005/2006

Serie zum 20.Oktober 2005 (ps, pdf)
Serie zum 3.November 2005 (ps, pdf)
Serie zum 17.November 2005 (ps, pdf)
Serie zum 1.Dezember 2005 (ps, pdf)
Serie zum 15.Dezember 2005 (ps, pdf)
Serie zum 12.Januar 2006 (ps, pdf)
Letzte Serie von 2006 (ps, pdf)

Aufgaben WS 2008/2009

Übung 1 (17.10.2008) (ps.gz, pdf)
Übung 2 (24.10.2008) (ps.gz, pdf)
Übung 3 (7.11.2008) (ps.gz, pdf)
Übung 4 (21.11.2008) (ps.gz, pdf)
Übung 5 (28.11.2008) (ps.gz, pdf)
Übung 6 (5.12.2008) (ps.gz, pdf)
Übung 7 (12.12.2008) (ps.gz, pdf)
Übung 8 (19.12.2008) (ps.gz, pdf)
Übung 9 (9.1.2009) (ps.gz, pdf)
Übung 10 (16.1.2009) (ps.gz, pdf)
Übung 11 (23.1.2009) (ps.gz, pdf)
Übung 12 (30.1.2009) (ps.gz, pdf)
Übung 13 (6.1.2009) (ps.gz, pdf)