51本色

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 " 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