Stellen Sie fest, ob ein Fluss Knotenanforderungen in einem angerichteten azyklischen Diagramm erfüllen kann

Question

Ich habe das folgende Problem, das ich nicht erfolgreich versuche zu lösen:

Ich habe ein gerichtetes Diagramm mit Node-Anforderungen. Im Gegensatz zu Kreislauf mit Anforderungen erhebt sich diese Knotennachlässe nicht von dem Fluss - die Knoten verlangen lediglich, dass ein Strömungsfluss k durch sie fließt. Die Grafik ist azyklisch, es ist jedoch kein Baum - mehrere Routen existieren von den höheren bis unteren Knoten.

Die Frage ist, ob ein Kraftfluss r alle Anforderungen der Knoten erfüllen kann. Natürlich kann ein Fluss mit Festigkeit mehr als k durch einen Knoten mit Bedarf k fließen. Es gibt auch keine Kapazitätsgrenzen in der Eingabediagramm.

Ich muss dieses Problem auf das Problem des MAX-Flow-Problems reduzieren. Ich habe versucht, ihn mit niedrigeren Grenzen und Zirkulation mit Anforderungen zu reduzieren, aber nicht erfolgreich, da ich keinen guten Weg finden kann, wie man irgendwie den Fluss in den Knoten einschränken kann, um die Anforderungen zu erfüllen und es zu messen zur gleichen Zeit.

Answer 1

Fügen Sie eine neue Quelle hinzu $ S $ und die Kante $ (S ', S) $ mit maximaler und minimaler Kapazität $ R $ .

Für jeden Scheitelpunkt $ V $ mit Bedarf $ D $ Führen Sie Folgendes an:

.
• ersetzen $ V $ mit zwei Scheitelpunkten $ v_1 $ und $ v_2 $ .
• Ersetzen Sie alle ehemaligen Kanten $ (u, v) $ mit $ (u, v_1) $
• Alle ersetzten Kanten ersetzen $ (v, u) $ mit $ (v_2, u) $ .
• Fügen Sie den Edge $ (v_1, v_2) $ mit minimaler Kapazität $ D $ .

Das Problem ist nun gleichwertig zu überprüfen, ob in einem Netzwerk in einem Netzwerk mit minimalen und maximalen Kantenkapazitäten vorhanden ist.

Dieses Problem ist allgemein bekannt und kann auf den Max-Flow reduziert werden (siehe z. B. "Salden und Pseudoflows" im Buch Algorithmen von Jeff Erickson).

im Wesentlichen, wenn $ D $ die Summe aller minimalen Kapazitäten der Kanten ist:

.
• Fügen Sie einen neuen Quellvertex hinzu $ s ^ * $ und ein neuer Ziel-Scheitelpunkt $ t ^ * $ .
• Fügen Sie den Edge $ (s ^ *, s ') $ mit maximaler Kapazität $ + \ Infty $ .

• für jede Kante $ (u, v) $ mit minimalkapazität $ c \ neq 0 $ < / span> und maximale Kapazität $ C $ , fügen Sie die Kante $ (u, t ^ *) $ hinzu> Mit Kapazität $ C $ , die Kante $ (s ^ *, v) $ mit Kapazität $ C $ , entfernen Sie die Mindestkapazität von $ (u, v) $ und ändern Sie die maximale Kapazität von $ (u, v) $ bis $ CC $ (falls $ C $ war $ + \ inmTy $ , dann ist die neue Kapazität auch $ + \ Infty $ ).

• Prüfen Sie, ob der maximale Fluss von $ s ^ * $ bis $ t ^ * $ ist gleich $ D $ .