Illustration

Dr. Stephan Dominique Andres: „Spielperfekte Graphen“

Kolloquium der Fakultät für Mathematik und Informatik

Termin: 11.09.2012

Loading the player ...

 

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.


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