Kolloquium der Fakultät für Mathematik und Informatik

Termin: 11.09.2012

 

• Begrüßung durch den Dekan der Fakultät Mathematik und Informatik,
  Herrn Prof. Dr. Werner Kirsch
• Prof. Dr. Winfried Hochstättler:
  Vorstellung des Fakultätspreises und des Preisträgers 2012
• Laudatio des Rektors der Fernuniversität,
  Herrn Prof. Dr.-ing. Helmut Hoyer
• Verleihung des Fakultätspreises 2012
  
• Dr. Stephan Dominique Andres:
  „Spielperfekte Graphen“

Abstract:

Graphenfärbungsprobleme treten in vielen Anwendungen auf, wie zum Beispiel bei der Funkfrequenzzuweisung oder Stundenplanproblemen oder, allgemeiner, bei Problemen, bei denen verschiedene Ressourcen miteinander in Konflikt stehen. Meist sind aber keine effizienten Lösungsverfahren bekannt. Eine Klasse von Graphen, bei denen das Färben gutartig ist, sind die sogenannten perfekten Graphen. Diese wurden 2006 von Chudnovsky, Robertson, Seymour und Thomas durch einen Beweis einer jahrzehntelang offenen Vermutung von Berge mittels verbotener induzierter Teilgraphen klassifiziert.

Im Gegensatz zu diesen Problemen, deren Lösung eine zentrale Instanz vornehmen kann, stehen Probleme, in denen anarchistische Elemente, die eigene Interessen verfolgen, die Lösungsfindung stören dürfen. Letztere stellen nichtkooperative Spiele dar. In einem mathematisch sehr vereinfachten Modell färben zwei Spieler abwechselnd bislang ungefärbte Knoten eines gegebenen Graphen mit Farben einer vorgegebenen Farbmenge, so dass benachbarte Knoten verschiedenfarbig gefärbt sind. Wenn das Spiel „aufgeht“, gewinnt der erste Spieler, der Maker, sonst der zweite, der Breaker. In Anwendungen könnte etwa der Maker für eine zentrale Administrationsinstanz stehen und der Breaker für die anarchistischen Elemente. Bei einem solchen Graphenfärbungsspiel lässt sich, analog zur Perfektheit, „Spielperfektheit“ von Graphen definieren.

Der Vortrag gibt einen kurzen Überblick über diese Fragestellungen und geht danach auf unsere Klassifikation spielperfekter Graphen durch verbotene induzierte Teilgraphen ein.

FernUniversität in Hagen, ZMI, 58084 Hagen, E-Mail: viedeostreaming(at)fernuni-hagen.de