Das Integralitäts-Theorem des Min-Cost-Flow-Problems besagt, dass bei gegebenen "Integraldaten" immer eine integrale Lösung für das Problem existiert, die einem minimalen Kostenfluss entspricht. Der Begriff der integralen Daten ist für mich etwas verwirrend, da die meisten Beiträge, Tutorials sagen, dass die Anforderungen, Lieferungen und Kapazitäten integraler Bestandteil sein sollten. Nun wird eine Kapazitätsbeschränkung typischerweise alsFlussintegralitätssatz mit minimalem Kostenaufwand
dargestelltl_i <= c_i <= u_i
wo l_i ist die untere Grenze von der Kapazität der Kante i und u_i ist die obere Grenze. Damit der Integralitätssatz gilt, reicht es, dass l_i and u_i ganze Zahlen sind? Der Zweifel rührt von der Tatsache her, dass dies nicht notwendigerweise bedeutet, dass die Flüsse immer ganze Zahlen sind, wie zum Beispiel für l_i = 0, u_i = 1, kann Rand i einen Fluss von 0,5 haben.
Danke. Heißt es, dass eine Lösung mit allen integralen Strömungen existiert? Oder ist es stärker? Mein Verständnis war, dass ein integraler Fluss existieren würde, der nicht schlechter ist als jeder Teilstrom. Kannst du mich auch auf den Beweis dafür hinweisen? Es ist komisch, dass es in Papieren und Tutorials selbstverständlich ist, a) es zu beweisen oder b) den ursprünglichen Beweis zu zitieren. – statBeginner
Es ist stärker. Der maximale Durchfluss entspricht dem minimalen Schnitt, und es gibt eine Lösung mit einem maximalen Durchfluss und allen integralen Durchflüssen. Siehe http://www.cs.princeton.edu/courses/archive/spr05/cos423/lectures/07maxflow.pdf für einen Nachweis. – btilly