Große Kreise

Das Rundreiseproblem, bei dem eine kürzeste Rundreise durch eine Anzahl vorgegebener Städte gesucht ist, ist eine der populärsten Aufgabenstellungen in der kombinatorischen Optimierung. Verwandt damit ist das Problem eines hamiltonschen Kreises, das ist ein wiederholungsfreier Kreis, der alle Knoten besucht, in Graphen. Auch dieses Problem ist kombinatorisch schwer und man nimmt an, daß es keine sinnvolle Charakterisierung der Existenz eines solchen Hamiltonkreises gibt. Statt dessen muß man sich mit notwendigen oder hinreichenden Bedingungen begnügen. Die wohl bekannteste solche hinreichende Bedingung ist die folgende von Dirac:

Sei G=(V,E) ein Graph ohne Schleifen und Parallelen und sei an jedem Knoten $v\in V$ die Anzahl der ausgehenden Kanten $d(v)\ge \frac{\vert V\vert}{2}$. Dann hat G einen Hamiltonschen Kreis.

Wir untersuchten nun, inwiefern diese Aussage sich allein mit Mitteln der Linearen Algebra formulieren und beweisen läßt. Dazu stellt man zunächst fest, daß die Punkte einen |V|-1 dimensionalen Vektorraum aufspannen, man spricht vom Rang r(M) des Matroides M auf der Kantenmenge E. Also können wir |V| durch r(M)+1 ersetzen. Um d(v) ersetzen zu können, beobachten wir zunächst, daß jeder Kreis einen Knoten gerade oft trifft. Die Bedingung $d(v)\ge \frac{\vert V\vert}{2}$impliziert darüberhinaus, daß jede nichtleere Kantenmenge, die von jedem Kreis gerade oft getroffen wird, wir sprechen vom orthogonalen Komplement des Kreisraums oder den Kokreisen, mindestens $\frac{\vert V\vert}{2}$ Kanten enthält. Damit können wir obigen Satz umformulieren.

Sei M ein einfaches binäres Matroid auf der Menge E und habe jeder Kokreis mindestens $\frac{r(M)+1}{2}$ Elemente. Dann hat M einen Kreis der Größe r(M)+1.

Leider ist dieser Satz so falsch. Betrachten wir dazu das Fanodual, das aus folgenden Vektoren besteht.

$$F_7^\ast=\bordermatrix{&e_1&e_2&e_3&e_4&f_1&f_2&f_3\cr & 1 &... ... 0 & 0 & 1 & 0 & 1 & 1 & 0\cr & 0 & 0 & 0 & 1 & 1 & 1 & 1\cr}$$

Die Matrix hat vollen Rang 4 und alle Kreise haben 4 Elemente, hingegen habe alle Cokreise 3 oder 4, in jedem Fall jedoch mehr als $\frac{4+1}{2}$ Elemente. Allerdings ist das Fanodual als Übeltäter, wenn es um Verallgemeinerungen von graphentheoretischen Sätzen geht, bekannt. Die Matroide, die diesen Übeltäter nicht enthalten sind eine etwas größere Klasse, als die Matroide, die durch total unimodulare Matrizen definiert sind, welche wiederum alle Graphen umfassen. Es gelang uns nun zu zeigen, daß obiger Satz - und ein paar ähnliche Sätze - in regulären Matroiden gelten. Genauer konnten wir die Gültigkeit in einer etwas größeren Klasse zeigen, wobei der Übeltäter diesmal nicht das Fanodual, sondern die Fanoebene selbst ist.

Sei $M\ne F_7^\ast$ ein ein einfaches binäres Matroid auf der Menge E ohne F₇-Minor und habe jeder Kokreis mindestens $\frac{r(M)+1}{2}$ Elemente. Dann hat M einen Kreis der Größe r(M)+1.