Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Dann für die letzte Veranstaltung.

Heute schauen wir uns noch etwas an und zwar den

Circuit für duale Flussprobleme auf bipartiten Farben.

Das Flussproblem haben wir auch schon gehabt, ich glaube vorgestern.

Wir hatten den bipartiten Grafen von A nach B, also von einer Seite zur anderen.

Das duale ist das Problem, das duale LP.

Wir haben einen Grafen gegeben, Bipartit, nicht zwingend vollständig.

Beim Transportproblem nimmt man typischerweise vollständigen bipartiten Grafen.

Man möchte von links die Menge Fluss 1 und links die Menge Fluss 2 transportieren.

So dass die Produktionskapazitäten weggeschafft werden und hier gerade die Bedarfskapazitäten

decken bzw. genau erfüllen.

Wenn man LP-Dualität macht, kommt man genau auf diese Bedingungen.

Die Zielfunktion steht jetzt auf der rechten Seite.

Die rechte Seite kommt dann irgendwo in die Zielfunktion, die wir hier aber gar nicht

haben, weil wir uns für das Polyeder interessieren.

Für jede Kante, die in diesem bipartiten Grafen auftaucht, haben wir eine Ungleichung.

Zusätzlich, damit das Teil auch noch Ecken hat, machen wir U0 gleich 0.

Wir können das also noch ein bisschen normieren.

Ansonsten könnten wir zu jedem UI einfach einen T dazu addieren und das wird alles weiterhin

erfüllt bleiben.

Deswegen normieren wir das U0 gleich 0 und haben einen Polyeder.

Dieses Polyeder ist bekannt.

Die Hirschranke.

Die der Karte wäre M-1 bei M-1 für vollständige bipartite Grafen.

Gilt und ist scharf.

Kann also nicht verbessert werden.

Der Beweis ist recht konstruktiv.

Er nimmt also zwei Punkte an und konstruiert praktisch für jeden zwei Punkte so einen Weg,

der maximal diese Länge hat.

Er kann aber auch zeigen, dass es zwei Punkte gibt, zwei Ecken, wo diese Konstruktion das

Maximum ausschöpft.

Was man hier ausnutzt, ist, dass man etwas weiß über die Ecken.

Man weiß die Ecken dieses Polyeders.

Die Ungleichungen, die in der Ecke scharf sind, also mit Gleichheit erfüllt sind, die

bilden hier einen aufspannenden Baum.

Damit kann man mit aufspannenden Bäumen eine Kante hinzu, eine Kante weg.

Man kann sehen, wie er von einer Ecke zur anderen kommt.

Also Ecken in diesem Polyeder entsprechend kreisen, wo wir eine Kante hinzunehmen.

Wir nehmen eine Kante zum Baum hinzu, wir haben einen Kreis, nehmen aus diesem Kreis

wieder eine Kante weg und haben wieder einen Baum.

Man kann das also recht schön mit Grafen beschreiben.

Was wir nachweisen konnten, ist das Circuit Durchmesser.

Das ist Englisch.

Man kann also die Ecken gut beschreiben und man kann die Kantenrichtungen gut beschreiben,

und zwar grafisch.

Demzufolge können wir auch gut hier auf diesen Grafen beschreiben, wie wir jetzt durch das

Polyeder da oben durchlaufen können, entlang der Kantenrichtung.

Wir konnten dann zeigen, dass dieser Circuit Durchmesser beschränkt ist durch M plus

N minus zwei.