Albert-Ludwigs-Universität Freiburg
	Institut für mathematische Logik und Grundlagen der Mathematik

Vorlesung: Das Graphen-Isomorphieproblem, SS 1997

M. Grohe

Zeit: Do 14-16 Uhr
Ort: SR 318, Eckerstr 1

Wie kann man feststellen, ob zwei endliche Graphen isomorph sind? Seit den sechziger Jahren versucht man, effiziente Algorithmen zu finden, die dies tun. Das Interesse an diesem Problem beruht zum einen auf seiner mathematischen Komplexität, zum anderen aber auch auf einer gewissen praktischen Bedeutung, denn bekanntlich lassen sich viele Anwendungen als Graphenprobleme auffassen.

Schon früh fand man gewisse Klassen von Graphen, für die sich das Isomorphieproblem effizient lösen lässt. Ein nichttriviales Beispiel sind die planaren Graphen. Die dabei verwendeten Verfahren nutzen gewisse kombinatorische Eigenschaften der betrachteten Graphen aus. Wir werden sehen, dass nicht nur spezielle Graphen wie die planaren, sondern "fast alle", in einem präzisen Sinne, solche kombinatorischen Eigenschaften besitzen. Nur müssen wir leider einsehen, dass es auch Ausnahmen gibt.

In den achtziger Jahren versuchte man zunehmend, Eigenschaften der Automorphismengruppen von Graphen auszunutzen, um zu besseren Ergebnissen zu gelangen. Am Ende der Vorlesung soll ein von Babai und Luks 1983 entwickelter gruppentheoretischer Algorithmus stehen, der bis heute das beste Verfahren darstellt, Isomorphie von beliebigen Graphen zu entscheiden.

Vorlesungsskript

Kapitel 1 (Version vom 26. Mai 1997)

Kapitel 2 (Version vom 3. Juni 1997)

Kapitel 3 (Version vom 18. Juni 1997)

Kapitel 4 (Version vom 10. Juli 1997)