Reduzieren der minimalen Scheitelpunktabdeckung in einem zweigeteilten Diagramm auf maximalen Fluss

7

Kann gezeigt werden, dass die minimale Scheitelpunktabdeckung in einem zweigeteilten Diagramm auf ein maximales Flussproblem reduziert werden kann? Oder zum Minimum-Cut-Problem (dann folgen Sie dem Max-Flow-Min-Cut-Theorem, der Anspruch gilt).

Intuitiv: Wählen Sie für jeden Fluss einen Endpunkt aus, dann ist dies eine minimale Scheitelpunktabdeckung im zweigeteilten Diagramm. Aber kann es konsequent gezeigt werden?

Summer_More_More_Tea
quelle
"Intuitiv: Wählen Sie für jeden Fluss einen Endpunkt aus, dann ist es eine minimale Scheitelpunktabdeckung in einem zweigeteilten Diagramm." Das ist nicht wahr. Betrachten Sie den Fall von 3 Eckpunkten und 2 Kanten.
Xuhdev

Antworten:

3

Nach dem Satz von König entspricht die Größe der minimalen Scheitelpunktabdeckung im zweigliedrigen Graphen der Größe der maximalen Übereinstimmung in , und es gibt eine offensichtliche Verringerung von der maximalen Übereinstimmung im zweigliedrigen Graphen zum Maxflow-Problem.GG

Wu Yin
quelle
1
Wenn Sie diese Antwort verbessern möchten, sollten Sie die Idee der Reduzierung skizzieren.
Raphael
2

Rufen Sie die beiden Partitionen der Knoten und . Fügen Sie zwei neue Knoten hinzu, eine Quelle und eine Senke . Verbinden Sie den Startknoten mit allen Knoten in mit einer Kante mit einer maximalen Kapazität von eins. Verbinden Sie alle Knoten in mit Kanten mit einer maximalen Kapazität von eins mit der Spüle. Und geben Sie zum Schluss allen Originalkanten im Diagramm eine maximale Kapazität von eins. Wenn Sie nun den maximalen Durchfluss von nach wird die minimale Scheitelpunktabdeckung ermittelt.ABstABst

Für jede Kante die im Max-Flow enthalten ist, ist entweder der Knoten oder Teil der minimalen Scheitelpunktabdeckung.(u,v)uv

Zeichnen Sie dies und Sie werden verstehen.

Die Unfun Cat
quelle
Wie werden Sie die Sätze A und B auswählen?
Abhishek Bhatia
@AbhishekBhatia Sie werden durch den zweiteiligen Graphen definiert.
Karlos