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