Seminar Diskrete Optimierung

The Game of Cops and Robbers on Graphs

Viele praktisch relevante Probleme lassen sich als kombinatorische Suchspiele formulieren, die auch abgesehen von ihren möglichen Anwendungen zu mathematisch sehr interessanten Fragen führen. Wir möchten uns in diesem Seminar anhand des neu erschienenen Buches "The Game of Cops and Robbers on Graphs" von Bonato und Nowakowski mit einer ganz grundlegenden Spielvariante befassen, bei der mehrere sogenannte "cops" einen "robber" zu fangen versuchen, indem sich beide Parteien entlang der Kanten eines Graphen bewegen. Der "robber" versucht seinerseits natürlich, der Festnahme zu entgehen. Abhängig von der Struktur des Graphen kann die minimale Anzahl von "cops", die den "cops" eine Gewinnstrategie garantiert, offenbar stark schwanken.

Das Buch legt praktisch alle seine Grundlagen selber und beschränkt sich auf die wesentlichen Aussagen, deren Beweise nicht allzu technisch werden und dabei dennoch die wichtigen Ideen sehr gut darstellen. Es werden u.a.

  • Schranken,
  • algorithmische sowie komplexitätstheoretische Fragen,
  • zufällige Graphen und
  • unendliche Graphen

betrachtet und die Teilnehmer erhalten jeweils auch einen guten Einblick in diese unterschiedlichen Gebiete und ihre Methoden.

Nächste Termine:

  • 10.05: Thema 7
  • 15.05: Thema 8
  • 22.05: Thema 9
  • 24.05: Thema 10
  • 29.05: Thema 12
  • 31.05: Thema 13
  • 05.06: Thema 14
  • 12.06: Thema 15 + Thema 16
  • 14.06: Thema 17
  • 19.06: Thema 18.A
  • 21.06: Thema 18.B

Aktuelles

Die nächste Termine sind da auf der Website.

Die Thema sind sowie aus den Themen.

Die Themen werden in der gleichen Reihenfolge wie auf dieser Liste präsentiert.

Das Seminar findet 2 mal in der Woche (am Dienstag und am Donnerstag von 18-20) statt. Wir fangen ab Donnerstag, den 19.04, an.

Das Seminar findet im Raum He 120 statt.

Sie dürfen maximal 4 Vorträge verpassen. 

Das Buch ist in meinem Semesterapparat!

Ein zweites Buch wird außerhalb des Semesterapparates da sein. Bitte dieses maximal 2 Wochen ausleihen!

Ich erwarte einen 1:30-Stunde Vortrag mit einigen vorbereiteten Spiel-Beispielen.