Kriterium für vollständige Unimodularität

In der Kombinatorischen Optimierung, einem der Teilgebiete der Kombinatorik, findet man einige Kriterien für die vollständige Unimodularität ganzzahliger Matrizen. Ein besonders nützliches dieser Kriterien geht auf eine Arbeit des französischen Mathematikers Alain Ghouila-Houri aus dem Jahre 1962 zurück.

Kriterium

Das Kriterium lässt sich angeben wie folgt:

Eine Matrix $A=(a_{ij})\in \mathbb {Z} ^{m\times n}\;(m,n\in \mathbb {N} )$ ist genau dann vollständig unimodular, wenn es für jede Teilmenge $R\subseteq \{1,...,m\}$ eine Zerlegung

$R_{1}\;{\dot {\cup }}\;R_{2}=R$

gibt derart, dass für jeden Index $j=1,...,n$ die Beziehung

$\sum _{i\in R_{1}}{a_{ij}}-\sum _{i\in R_{2}}{a_{ij}}\in \{-1,0,1\}$

erfüllt ist.

Korollar

Das Kriterium von Ghouila-Houri lässt sich umsetzen in ein Kriterium für bipartite Graphen:

Die Inzidenzmatrix $I_{G}$ eines endlichen ungerichteten Graphen $G$ ist vollständig unimodular genau dann, wenn $G$ bipartit ist.

Weiteres Kriterium

Ein anderes wichtiges Kriterium für die vollständige Unimodularität ganzzahliger Matrizen – welches auch zum Beweis des Kriteriums von Ghouila-Houri herangezogen werden kann – hatten schon A.J. Hoffman und J.B. Kruskal im Jahre 1956 geliefert. Darin wird die vollständige Unimodularität ganzzahliger Matrizen in Verbindung gebracht mit Ganzzahligkeitseigenschaften der zugehörigen Polyeder. Im Einzelnen gilt nämlich der folgende Satz:

Eine Matrix $A\in \mathbb {Z} ^{m\times n}\;(m,n\in \mathbb {N} )$ ist genau dann vollständig unimodular, wenn für jeden Vektor $b\in \mathbb {Z} ^{m}$ sämtliche Eckpunkte des zu $b$ gehörigen Polytops $\{x\in \mathbb {R} ^{n}\mid x\geq 0\;,{A\cdot x}\leq b\}$ ganzzahlige Koordinaten haben.

Anmerkungen

• Eine Matrix $A\in \mathbb {Z} ^{m\times n}\;(m,n\in \mathbb {N} )$ heißt vollständig unimodular oder auch total unimodular, englisch totally unimodular, falls jede Unterdeterminante (und damit auch jedes Element) von $A$ gleich 0 oder gleich 1 oder gleich −1 ist.

Literatur

• Martin Aigner: Diskrete Mathematik (= Vieweg Studium: Aufbaukurs Mathematik). 6., korrigierte Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8. 
• Alain Ghouila-Houri: Caractérisation des graphes non orientés dont on peut orienter les arětes de manière à obtenir le graphe d'une relation d'ordre. In: Comptes Rendus Hebdomadaires des Séances de l'Académie des Sciences. Band 254, 1962, S. 1370–1371 (MR0172275). 
• A. J. Hoffman, J. B. Kruskal: Integral boundary points of convex polyhedra In: Linear Inequalities and Related Systems. In: Annals of Mathematics Studies. Band 38, 1956, S. 223–246 (MR0085148). 
• Bernhard Korte, Jens Vygen: Kombinatorische Optimierung: Theorie und Algorithmen. 3. Auflage. Springer Spektrum, Berlin 2018, ISBN 978-3-662-57690-8, S. 122 ff.