Max-Flow Min-Cut Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 16:57 Do 26.01.2017 | | Autor: | sagat |
| Aufgabe | Gegeben sei ein Flussnetzwerk Quelle s und Senke t mit einer positiven Kapazitatsfunktion c
auf der Menge der Kanten und zusatzlich einer positiven Kapazitatsfunktion d auf der Menge
der Knoten. Gesucht ist der maximale Fluss, sowie der minimale Schnitt fur dieses Flussproblem und den
gegebenen Graphen. Uberlegen Sie sich dazu, wie Sie dieses Problem so umformulieren, dass
daraus ein Standard Flussproblem wird.
In der Delivery.java-Datei finden Sie zwei Variablen, die fur die Abgabe relevant sind. Den
maximalen Fluss geben Sie mittels der Variable
public int[][] maxFlow
und den minimalen Schnitt mittels der Variable
public String[] minCut an.
Bitte bedenken Sie, dass der minimale Schnitt in diesem Fall nicht nur Kanten sondern auch
Knoten enthalten kann.
Hinweise bezuglich des Formats, sowie eine Matrix mit Kantenkapazitaten, finden Sie in der
Delivery.java. |
Hallo,
das ist meine erste Frage hier im Forum. Ich freue mich hier zu sein und hoffe auf meine Errettung :)
Wie bereits oben angegeben, geht es in der Aufgabe um den Max Flow und den Min Cut zu meinem Graphen.
[Dateianhang nicht öffentlich]
Ich habe bereits einen Max Flow angegeben:
//----- Maximaler Fluss -----
//Spalten- und Zeilenindizies: S A B C D E F G H T.
//D. h. dass z. B. die Zeile & Spalte 0 für den Knoten S steht, 1 für A usw.
//Demnach represäntiert z. B. die Zelle (1,2) die Kantenkapazität vom Knoten A zum Knoten B.
//Die diagonale, also alle Zellen (i,i) geben die Knotenkapazitäten an. Zelle (3,3) gibt also an, welche Kapazität der Knoten C hat.
//Die Hilfsmatrix "capacities" gibt die maximalen Kapazitäten Ihres Graphens an.
//Geben Sie Ihre Lösung im gleichen Format in der Variable "maxFlow" an.
//Als Werte in der Matrix, geben Sie den Durchfluss über die einzelnen Kanten/Knoten.
public int[][] maxFlow =
{
{0,3,4,0,3,0,0,0,0,0},
{0,3,0,3,0,0,0,0,0,0},
{0,0,4,0,0,3,0,0,0,0},
{0,0,0,4,0,0,4,0,0,0},
{0,0,0,0,3,3,0,0,0,0},
{0,0,0,0,0,6,0,3,3,0},
{0,0,0,0,0,0,4,0,0,4},
{0,0,0,0,0,0,0,3,0,3},
{0,0,0,0,0,0,0,0,3,3},
{0,0,0,0,0,0,0,0,0,0}
};
Jetzt suche ich den Min Cut und habe absolut keine echte Vorstellung, wie ich den finde.
Soweit ich verstanden habe, geht es darum, den Graphen Vertikal zu teilen und dann Kanten zu finden,
ganz nach dem Motto Max Flow = Min Cut.
Wäre super wenn mir jemand helfen könnte.
Grüße
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:39 Fr 03.02.2017 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
