Seminar - Einführung in die Graphen- und Berechenbarkeitstheorie (WS 14/15)

In dieser Veranstaltung beschäftigen wir uns zunächst mit den grundlegenden Begriffen der Graphentheorie und elementaren Beziehnungen zwischen diesen. So werden zum Beispiel der Heiratssatz, die Plättbarkeit von Graphen und Färbbarkeitsprobleme untersucht. Diese Probleme spielen auch in der Praxis eine wichtige Rolle: Beispielsweise ist das Problem, eine Schaltung so auf eine Platine zu drucken, dass sich keine zwei Leiterbahnen überschneiden, ein Plättbarkeitsproblem eines Graphen. Der Fünffarbensatz entscheidet das folgende Färbbarkeitsproblem: Ist es möglich jede vernünftige Landkarte so mit fünf Farben zu färben, dass keine zwei Länder mit derselben Farbe aneinandergrenzen?

Um nicht nur eine theoretische 'ja/nein'-Antwort auf diese Fragen zu bekommen sondern um zu entscheiden, ob eine Lösung der genannten Probleme in hinnehmbarer Zeit praktisch z.B. durch einen Computer zu konstruieren ist, wollen wir uns mit der Theorie der Berechenbarkeit und Komplexität beschäftigen. Es wird auf die grundlegenden Begriffe der Berechenbarkeitstheorie wie den Begriff der formalen Sprache, der Grammatiken, der endlichen Automaten und der Turing Maschinen eingegangen, um die Komplexität eines Problems präzise beschreiben zu können. Dieses führt zu dem vermutlich wichtigsten ungelösten Problem der Informatik: Ist P=NP oder nicht? Diese und weitere spannende Fragen werden wir zu verstehen versuchen.

Bei der genauen Wahl der Themen kann auf besondere Interessen der TeilnehmerInnen eingegangen werden. Es ist möglich, entweder einen Proseminarvortrag (3 Leistungspunkte) über ein elementares Thema oder einen Seminarvortrag (6 Leistungspunkte) über ein fortgeschrittenes Thema zu halten.

Eine Vorbesprechung findet am Mittwoch, den 9.7. um 11:00 Uhr in M201 statt. Hier sollen die ersten Vorträge vergeben werden. Eine Anmeldung ist auch per Email (florian.strunk@mathemath.uni-regensburg.de) möglich.

Organisatorisches:

• Termin: Mittwochs 12:00-14:00 Uhr (c.t.)
• Raum: M103
• Informationen im Vorlesungsverzeichnis.
• Vortragsdauer: Eine Stunde und 15 Minuten plus 15 Minuten Diskussion.

Vorträge:

1. Grundbegriffe der Graphentheorie: Eckengrad, Wege und Kreise, Zusammenhang (8.10. - ) (Proseminarvortrag)
   In diesem Vortrag sollen Graphentheoretische Grundbegriffe und elementare Beziehungen anhand von [1, Kapitel 0.0-0.4] eingeführt werden. Ein Ergebnis ist der Satz von Mader, der besagt, dass aus hohem Durschnittsgrad die Existenz eines Teilgraphen hohen Zusammenhangs folgt. Hoher Zusammenhang setzt hohen Minimalgrad voraus, aber hoher Minimalgrad sichert keinen hohen Zusammenhang.
   
   
2. Bäume, Wälder, bipartite Graphen und Minoren (15.10. - ) (Proseminarvortrag)
   In diesem Vortrag soll [1, Kapitel 0.5-0.7] behandelt werden. Die hier eingeführten Begriffe zu bipartiten Graphen sind Grundlage des Vortrags "Matchings, der Heiratssatz und Anwendungen". Ein Ergebnis dieses Vortrags ist, dass jeder zusammenhängende Graph einen normalen Spannbaum mit beliebig vorgegebener Ecke als Wurzel enthält.
   
   
3. Eulersche Graphen, Lineare Algebra in der Graphentheorie und Anwendungen (22.10. - ) (Seminarvortrag)
   In diesem Vortrag sollen zunächst eulersche Graphen anhand von [1, Kapitel 0.8] besprochen werden. Ein Graph ist eulersch, wenn er einen geschlossenen Kantenzug enthält, der jede Kante des Graphen genau einmal enthält. Ein Ergebnis ist hier, dass ein Graph eulersch ist genau dann, wenn jede seiner Ecken geraden Grad hat. Einem Graphen (oder allgemeiner einem gerichteten und gewichteten Graphen) kann man eine Adjazenzmatrix (siehe [1, Kapitel 0.9]) zuordnen. Nun kann man diese Matrix mit linearer Algebra untersuchen und von den dabei erhaltenen Ergebnissen auf Eigenschaften des Graphen schließen. Auf diese Weise lässt sich auch die ungefähre Funktion der Suchmaschine Google verstehen.
   
   
4. Matchings, der Heiratssatz und Anwendungen (19.10. - ) (Proseminarvortrag)
   In diesem Vortrag soll zunächst auf das Material aus [1, Kapitel 1.1] eingegangen werden. Ein Ergebnis ist hier der sogenannte Heiratssatz, der besagt, dass ein bipartiter Graph (mit linker und rechter Eckenpartition) genau dann ein Matching besitzt, wenn jede Teilmenge der linken Partition mindestens so viele Nachbarn besitzt, wie sie selbst Elemente hat. Dieser Satz lässt viele Interpretationen als Situationen im Alltag zu, von denen einige beschrieben werden sollen.
   
   
5. n-Zusammenhang und der Satz von Menger (5.11. - ) (Proseminarvortrag)
   In diesem Vortrag soll [1, Kapitel 2.1-2.3] behandelt werden. Ein Ergebnis ist der Satz von Menger, der besagt, dass für zwei Mengen von Ecken A und B in einem Graphen die kleinste Mächtigkeit einer A von B trennenden Eckenmenge gleich der größten Mächtigkeit einer Menge disjunkter A-B-Wege ist.
   
   
6. Graphen in der Ebene: Plättbarkeit und der Satz von Kuratowski (12.11. - ) (Seminarvortrag)
   Grundlage dieses Vortrags ist [1, Kapitel 3.1-3.5]. Es werden zunächst einige topologische Aussagen wie die Eulersche Polyederformel bewiesen. Ein Korollar hiervon ist, dass ein ebener Graph mit n Ecken, wobei n mindestens Drei ist, höchstens 3n-6 Kanten haben kann. Ein weiteres Ergebnis ist der Satz von Kuratowski, der besagt, dass ein Graph genau dann plättbar ist, wenn er weder einen K5 noch einen K(3,3) als Minor enthält.
   
   
7. Grundlagen der Färbbarkeitstheorie (19.11. - ) (Proseminarvortrag)
   Diesem Vortrag liegt [1, Kapitel 4.1-4.2 ohne den Satz 4.2.4. von Brooks] zu Grunde. Zunächst sollen die grundlegenden Begriffe der Färbbarkeitstheorie eingeführt und der Greedy-Algorithmus erklärt werden. Wesentliches Ergebnis dieses Vortrags ist der Fünffarbensatz, der besagt, dass jeder ebene Graph 5-färbbar ist. Die Aussage des stärkeren Vierfarbensatzes soll formuliert und eine Interpretation als eine Aussage über die Einfärbung von Landkarten gegeben werden.
   
   
8. Eckenfärbungen und Kantenfärbungen (19.11. - ) (Seminarvortrag)
   Dieser Vortrag ist eine Weiterführung des letzten Vortrags "Grundlagen der Färbbarkeitstheorie" nach [1, Kapitel 4.1-4.3, 4.5]. Die Existenz des Greedy-Algorithmus stellt sicher, dass die chromatische Zahl nach oben durch den Maximalgrad plus Eins beschränkt und Graphen mit hoher chromatischer Zahl haben daher einen hohen Maximalgrad. Der Satz von Brooks besagt, dass die chromatische Zahl zusammenhängender Graphen, die weder vollständig noch einen Kreis ungerader Länge sind sogar nach oben durch den Maximalgrad beschränkt sind. Neben Eckenfärbunden sollen auch Kantenfärbungen besprochen werden. Der Satz von Vizing besagt, dass die Kantenchromatische Zahl eines Graphen entweder dessen Maximalgrad oder dessen Maximalgrad plus Eins ist. Schlussendlich sollen einige Aussagen aus Kapitel [1, Kapitel 4.5] über perfekte Graphen skizziert werden.
   
   
9. Hamiltonkreise (3.12. - ) (Seminarvortrag)
   Analog zu der Definition eines eulerschen Graphen nennt man einen Graphen hamiltonsch, wenn er einen geschlossenen Kantenzug enthält, der jede Ecke des Graphen genau einmal enthält. Es wurde ein einfaches Kriterium vorgestellt, das entscheidet, ob ein Graph eulersch ist. Allerdings ist es wesentlich schwieriger zu entscheiden, ob ein Graph hamiltonsch ist. Es soll das Material aus [1, Kapitel 8 ohne Beweis von 8.3.1] vorgestellt werden. Ein Ergebnis ist der Satz von Dirac, dass ein Graph mit mehr als drei Ecken und dem Minimalgrad mindestens der halben Eckenanzahl hamiltonsch ist.
   
   
10. Zufallsgraphen und Existenzaussagen (10.12. - ) (Seminarvortrag)
    Grundlage dieses Vortrags ist [1, Kapitel 9.1-9.2]. Wesentliches Ergebnis ist der Satz von Erdős, der besagt, dass es zu einer festen Zahl k einen Graphen mit chromatischer Zahl mindestens k und Taillenweite mindestens k gibt. Dieser Satz über die Existenz eines bestimmten Graphen wird erstaunlicherweise durch Wahrscheinlichkeitstheoretische Methoden bewiesen.
    
    
11. Formale Sprachen und Grammatiken, Chomsky-Hierarchie (17.12. - ) (Proseminarvortrag)
    Dieser Vortrag baut nicht auf dem vorher Besprochenen auf. Es soll zunächst erklärt werden, was eine formale Sprache und die von einer Grammatik erzeugte formale Sprache ist. Die regulären Sprachen (Typ 3), kontext-freien Sprachen (Typ 2), ε-kontext sensitiven Sprachen (Typ 1) und rekursiv aufzählbaren Sprachen (Typ 0) sollen definiert werden. Anschliessend soll das Existenzlemma der Chomsky-Normalform bewiesen werden.
    
    
12. Turingmaschinen, rekursive Mengen und Funktionen (7.01. - ) (Proseminarvortrag)
    In diesem Vortrag soll zunächst eine Definition einer Turingmaschine, eine Definition einer rekursiv aufzählbaren Menge und einer rekursiv aufzählbaren Funktion gegeben und einige grundlegende Beobachtungen dazu gemacht werden. Grundlage sind Teile von [2]. Es soll erklärt werden, wieso die Turingmaschinensprachen genau die rekursiv aufzählbaren Sprachen (Typ 0) sind. Anschließend soll kurz skizziert werden, wieso verschiedene andere mögliche Definitionen einer Turingmaschine (z.B. mehrbändige Turingmaschinen) die gleichen Sprachen erzeugen und die Church-Turing-These soll erwähnt werden. Eine Turingmaschine heisst Algorithmus, wenn sie für jede Eingabe nach endlich vielen Bewegungen hält. Die von diesen Turingmaschinen definierten Sprachen heißen rekursive Sprachen und man könnte ihnen den Typ 0.5 zuordnen, d.h. sie enthalten die ε-kontext sensitiven Sprachen, sind aber nicht alle rekursiv aufzählbaren Sprachen (letzteres wird im Vortrag "Das Halteproblem" diskutiert). Es kann auf spezielle Turingmaschinen, die (deterministischen) endlichen Automaten ((D)EA) eingegangen und erklärt werden, wieso deren Sprachen genau die regulären Sprachen (Typ 3) sind.
    
    
13. Das Halteproblem (14.01. - ) (Seminarvortrag)
    In diesem Vortrag soll gezeigt werden, wieso es eine rekursiv aufzählbare Sprache gibt, die nicht rekursiv ist. Der Satz von Rice [2] besagt sogar, dass jede nicht-triviale Eigenschaft rekursiv abzählbarer Sprachen nicht entscheidbar ist, wie z.B. Leere, Endlichkeit, Rekursivität und Regularität. Dieser Vortrag ist stark mit dem vorherigen verknüpft und die beiden Vortragenden sollten sich stark abstimmen. So können zum Beispiel Themen aus "Turingmaschinen, rekursive Mengen und Funktionen" besprochen werden, wenn der vorherige Vortrag zeitlich nicht gut zu bewältigen war. Insbesondere sollen noch nichtdeterministische Turingmaschinen (d.h. grob gesprochen Turingmaschinen, die anstatt einer Übergangsfunktion mit einer Übergangsrelation funktionieren) eingeführt und skizziert werden, wieso sie die gleichen Sprachen erkennen.
    
    
14. Die Komplexitätsklassen P und NP (21.01. - ) (Seminarvortrag)
    Grundlage dieses Vortrags ist wieder das Buch [2]. Im Gegensatz zu den vorherigen beiden Vorträgen "Turingmaschinen, rekursive Mengen und Funktionen" und "Das Halteproblem" beschäftigt sich dieser Vortrag nicht mit der Effektivität, d.h. der Frage ob eine bestimmte Menge rekursiv ist, sondern mit der Effizienz, d.h. der Frage wie schnell ein Halten zu erwarten ist. Tatsächlich beschäftigen wir uns nur mit der zeitlichen Komplexität und ignorieren, wieviel Speicherplatz benutzt werden muss. Probleme, die sich auf einer deterministischen Turingmaschine in polynomieller Zeit lösen lassen formen die Klasse P. Probleme, die sich auf einer nichtdeterministischen Turingmaschine in polynomieller Zeit lösen lassen formen die Klasse NP. Sicherlich ist P in NP enthalten, aber die Umkehrung ist nicht bekannt und das berühmte P-NP-Problem. Die Klasse der NP-vollständigen Probleme besteht genau aus den Problemen aus NP, die die Eigenschaft haben, dass sich jedes Problem aus NP in polynomieller Zeit (mit einer deterministischen Turingmaschine) auf dieses zurückführen lässt. Hier ist ein Zitat von Wikipedia: Die Tatsache, dass so viele wichtige, aber deterministisch bisher nicht effizient lösbare Probleme in dieser Klasse [NP] liegen, hat die Hoffnung genährt, durch eine Untersuchung des nichtdeterministischen Turingmaschinentyps Hinweise auf eine effizientere Lösung dieser Probleme zu erhalten. Ließe sich etwa ein allgemeines Verfahren finden, mit dem eine nichtdeterministische Turingmaschine durch eine deterministische in Polynomialzeit simuliert werden kann, so wäre für alle genannten Probleme [in NP] gezeigt, dass sie in P liegen und damit effizient lösbar sind. Die Klassen P und NP wären dann identisch. Dies ist aber bis heute nicht gelungen. Die Fragestellung ist auch als P-NP-Problem bekannt.
    
    
15. 3FARB ist NP-vollständig (28.01. - Vortragende_r) (Seminarvortrag)
    In diesem Vortrag soll gezeigt werden, dass das Problem zu entscheiden, ob ein gegebener Graph 3-färbbar ist (d.h. eine chromatische Zahl kleiner oder gleich Drei hat), ein NP-vollständiges Problem ist. Mit dieser Frage werden die beiden Teile des Seminars zusammengeführt. Der Satz von Cook-Levin, der besagt, dass das Problem SAT, d.h. das Problem zu entscheiden, ob ein boolscher Ausdruck erfüllt werden kann, ein NP-vollständiges Problem ist, soll zitiert werden. Es soll gezeigt werden, dass SAT durch einen Algorithmus in polynomieller Zeit auf das Problem CLIQUE, also das Problem zu entscheiden, ob ein gegebener Graph (als Eingabe zusammen mit einer natürlichen Zahl k) eine k-Clique enthält, reduzierbar ist. Damit ist CLIQUE NP-vollständig. Schlussendlich kann man durch einen Algorithmus das Problem CLIQUE in polynomieller Zeit auf das Problem 3FARB reduzieren, womit gezeigt ist, dass 3FARB NP-vollständig ist. Hierzu kann man einen schönen graphischen Beweis angeben.
    
    

Literatur: