Prof. Dr. G. Reinelt, Dr. M. Oswald, D. O. Theis

Seminar "Polyedrische Kombinatorik"



Zeit: nach Vereinbarung
Vorbesprechung: Di, 21.10., 16:00 Uhr Raum 220 INF 368 oder: bis 27.10. in Raum 106/104 INF 368 vorbeikommen oder: eMail.
Beginn: 27.10. (dritte Semesterwoche)
Großgebiet: Diskrete Geometrie, Kombinatorische Optimierung
Zuordnung: Angewandte Mathematik
Voraussetzungen: Vordiplomsstoff



Ein konvexes Polyeder ist der Schnitt endlich vieler Halbräume
       { x \in Rm |  aT x \le \alpha }
im Rm. Da wir uns ausschließlich für konvexe Polyeder interessieren, lassen wir das Wort "konvex" weg.

Loading icosaeder geometry.

Ein fundamentaler Satz der Polyedertheorie besagt, dass die obige Definition eines Polyeders äquivalent ist zu der folgenden: eine Menge P \subset Rm ist ein Polyeder, wenn eine endliche Menge von Punkten X und eine endliche Menge von Vektoren Y im R^n existieren, so dass P = conv X + cone Y, wobei conv die konvexe Hülle der Punkte meint und cone den von den Vektoren erzeugten konvexen Kegel. Die Menge X wäre für das Polyeder in dem animierten Bild oben z.B. die Menge der roten Punkte, Y ist dort leer.

In der Polyedrischen Kombinatorik beschäftigt man sich mit Polyedern, bei denen diese Mengen X und Y durch eine kombinatorische Fragestellung definiert sind.

Ein wichtiges Beispiel ist etwa die konvexe Hülle der charakteristischen Vektoren aller Hamiltonschen Kreise in einem ungerichteten (meist vollständigen) Graphen. Ein Graph G=(V,E) ist ein Paar bestehend aus einer Menge von Knoten V und einer Menge von Kanten E, die man sich als Verbindungen von zwei Knoten denkt (formal ist eine Kante eine zweielementige Teilmenge der Knotenmenge, wenn man zwischen je zwei Knoten nur eine Kante erlaubt; erlaubt man mehrere, dann ist die Definition nicht mehr so schön aber nicht weniger intuitiv). Ein Hamiltonscher Kreis ist eine Menge von genau |V| Kanten mit der Eigenschaft, daß an jedem Knoten genau zwei Kanten aus der Menge anliegen. Nehmen wir als Beispiel den vollständigen Graphen mit vier Knoten, K4:

Er hat drei Hamiltonsche Kreise. Das Polyeder ist ein Dreieck im R6 (also ziemlich trivial).

Diese Polyeder sind in der Kombinatorischen Optimierung sehr wichtig, da sie Nachweise der Optimalität von Lösungen für das sog. Traveling Salesman Problem (TSP) erlauben. Deswegen wird das Polyeder, das duch die konvexe Hülle aller Hamiltonscher Kreise auf dem vollständigen Graphen mit n Knoten definiert wird, mit STSP(n) bezeichnet (S für symmetrisch -- der Graph ist ungerichtet). STSP(3) ist also ein Dreieck im R6, STSP(4) und STSP(5) sind auch noch relativ einfach, bei STSP(6) wird es schon spannend. Für STSP(9) braucht man über 42 Millionen Halbräume.

Eine Klasse von Polyedern, die mit den STSP-Polyedern stark verwandt sind, wird definiert durch die Menge aller aufspannenden geschlossenen Pfade in einem ungerichteten Graphen. Erklärung durch Beispiel -- im Folgenden sieht man aufspannende geschlossene Pfade im vollständigen Graphen mit vier Knoten (die dicken Kanten bedeuten, daß die Kante zwei mal im Pfad vorkommt):

Die konvexe Hülle aller aufspannender geschlossener Pfade in einem Graphen G ist ein Polyeder das mit GTSP(G) bezeichnet wird, da es mit dem sog. Graphical Traveling Salesman Problem verwandt ist. Im Fall von vollständige Graphen schreibt man auch GTSP(n).
Die oben graphisch dargestellten Punkte sind gerade die Ecken (Extrempunkte) von GTSP(4); nimmt sie als Menge X und die sechs Einheitsvektoren als Menge Y, so bekommt man GTSP(4) = conv X + cone Y.
Die Hamiltonschen Kreise sind spezielle aufspannende geschlossene Pfade, d.h. STSP(n) \subset GTSP(n). Im Beispiel des vollständigen Graphen mit vier Knoten ist GTSP(4) sechs-dimensional, und eine "Seitenfläche" dieses Polyeders ist das STSP(4).
Das animierte Bild zeigt GTSP(3). STSP(3) besteht nur aus einem Punkt, nämlich der "Bleistiftspitze" im Bild. GTSP(3) ist ein unbeschränktes Polyeder (der "Bleistift" ist unendlich lang) -- im Bild ist es oben abgeschnitten.

Loading geometry.

In diesem Seminar werden zunächst vorlesungsartig die Voraussetzungen aus der Polyedertheorie und Graphentheorie vermittelt. Dazu gehören natürlich alle oben schon benutzten Begriffe und einige weitere Definitionen und Sätze. Zu Themen aus der allgemeinen Polyedertheorie können auch Vorträge vergeben werden.

Anschließend werden wir uns schwerpunkmäßig konkret mit den beiden oben angerissenen Klassen von Polyedern beschäftigen: STSP(n) und GTSP(G). Trotz ihrer großen Bedeutung in der kombinatorischen Optimierung gibt es zu diesen Polyedern noch eine Reihe von wichtigen offenen Fragen.
Zu diesen gehört insbesondere die Graphical-Relaxation-Vermutung, die das Verhältnis der beiden Klassen von Polyedern präzisiert und mit der wir uns am Schluss beschäftigen werden.



Literatur: