Programmieraufgabe: Kanten-Kapazität und minimaler Schnitt

Moderator: Effiziente Graphenalgorithmen

Joni
Neuling
Neuling
Beiträge: 1
Registriert: 18. Sep 2016 18:01

Programmieraufgabe: Kanten-Kapazität und minimaler Schnitt

Beitrag von Joni » 8. Jan 2019 23:47

Ich bin bei der Implementierung des Zufallsgenerators für Instanzen des Max-Flow Problems über eine scheinbare einfache Anforderung gestolpert:
Start- und Zielknoten sowie die Kapazitäten der einzelnen Kanten sind so festzulegen, dass keine zum Start- bzw. zum Zielknoten inzidente Kante zu einem minimalen Schnitt gehört.
1. Da wir den minimalen Schnitt nicht finden können, ohne einen der Fluss-Algorithmen zu verwenden, vermute ich, dass wir uns eine Art Heuristik ausdenken sollen wie wir Start- und Zielknoten wählen und die Gewichte setzen?

2. Zur Formulierung "inzident" (ich gehe mal davon aus, dass die Rückkanten im Residualgraphen mit 0 initialisiert werden können, somit können wir diese für die Suche des min-cuts vernachlässigen): Für die Berechnung des Gewichtes eines Schnittes sind nur die gerichteten Kanten heranzuziehen, deren Startpunkt in S und deren Endpunkt in T liegen. Somit kann der Startknoten selbst ja gar nicht Teil eines minimalen Schnittes sein - alle Kanten, die zu ihm inzident (also "einfallend") sind, haben ihnen Endpunkt nicht in T sondern in S!

3. Gibt es einen Hinweis, wie man das Geforderte zuverlässig implementieren könnte? Alle Ideen die ich bis jetzt hatte, vereinfachen das Max-Fluss Problem entweder zusehr oder (nicht-exklusives oder) sind Heuristiken, die im allgemeinen Fall fehlschlagen könnten.

Zurück zu „Effiziente Graphenalgorithmen“