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.Bernhard Korte, Jens Vygen: Kombinatorische Optimierung. 2018, S. 122 ff.
Kriterium Das Kriterium lässt sich angeben wie folgt:Korte/Vygen, op. cit., S. 124 Eine Matrix ist genau dann vollständig unimodular, wenn es für jede Teilmenge eine Zerlegung
gibt derart, dass für jeden Index die Beziehung
erfüllt ist.
Korollar Das Kriterium von Ghouila-Houri lässt sich umsetzen in ein Kriterium für bipartite Graphen:Korte/Vygen, op. cit., S. 125
Die Inzidenzmatrix eines endlichen ungerichteten Graphen ist vollständig unimodular genau dann, wenn 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:Martin Aigner: Diskrete Mathematik. 2006, S. 319Korte/Vygen, op. cit., S. 122
Eine Matrix ist genau dann vollständig unimodular, wenn für jeden Vektor sämtliche Eckpunkte des zu gehörigen Polytops ganzzahlige Koordinaten haben.
Anmerkungen Eine Matrix heißt vollständig unimodular oder auch total unimodular, , falls jede Unterdeterminante (und damit auch jedes Element) von gleich 0 oder gleich 1 oder gleich −1 ist.
Literatur
Einzelnachweise
Kategorie:Kombinatorik Kriterium für Vollständige Unimodularität