[DSAL] Niveaunetzw., Überlagerung von plan. Graphen,

[YtKM]

Niveaunetzwerk
Ich habe das Niveaunetzwerk noch nicht ganz verstanden. Laut Foloe 1659 ist der Status eines Knotens durch den Abstand zu Quelle definiert. Soweit ich es richtig verstanden haben, ist dies einfach die Länge des Kürzesten Pfades von der Quelle zu dem entsprechenden Knoten ohne jegliche Gewichtung.

Das Niveaunetzwerk ist dann eindeutig definiert durch das Restnetzwerk und eben die Kanten bei denen Status_Destination-Status_Origin=1 gilt.

Im nachfolgenden Beispiel wurden dann laut Google-Group einige Fehler gemacht, wobei mir bis jetzt nicht klar ist, wie es richtig funktioniert.
Wie bilde ich mit Hilfe der Definition ein korrektes Niveaunetzwerk und was genau ist der Sinn des Netzwerkes?



Überlagerung von plan. Graphen
Auf Folie 2033 wird entschieden welche Zyklen die gleichen Facetten begrenzen. Mir ist allerdings dieses Vorgehen nicht ganz klar.

Wieso machen wir dies? Vorher wurden die Knoten und Kanten schon eindeutig bestimmt. D.h. die Facetten sind schon klar definiert, oder?

Ist dieser Vorgang nur noch nötig um den Facetten den richtigen Namen zu geben und den Facetten jeweils die richtigen Outer und Innercomponents zu zuweisen?

Ich wäre erfreut, wenn man mir hierzu nochmal Auskunft geben könnte.

Vielen Dank

ytkm

[Commo]

In der Vorlesung Effiziente Algorithmen werden die Flussalgorithmen gut erklärt.. Wenn du noch die Zeit findest, kannst du ja in das Skript reinschauen: http://www-i1.informatik.rwth-aachen.de/Lehre/SS08/VEA.php. Sehr zu empfehlen dort auch die Beispiele: http://www-i1.informatik.rwth-aachen.de/Lehre/SS08/VEA/Skripte/dinic.pdf

Das Beispiel aus der Vorlesung kannst du eigentlich bedenkenlos nehmen, das einzige was falsch ist, sind die Kanten von 1-1 und 2-2. Wenn du die einfach mal wegstreichst, kannste dir das Beispiel trotzdem antun, weil die benutzen diese Kanten ja auch nicht.

Vielleicht helfen dir die Beispiele ja schon.. Ansonsten nochmal klipp und klar: Ein Knoten liegt auf Niveau i, wenn der kleinste Abstand (Anzahl der Kanten) von Quelle bis zum Knoten genau i beträgt. Im Niveaugraphen übernimmst du das Restnetzwerk mit der Einschränkung, dass du nur Kanten einfügst, die von einem Knoten mit Niveau i zu einem Knoten mit Niveau i+1 führen.

Der Sperrfluss, den du mit Dinitz berechnest, verstopft dann auf jedem Weg im Niveaugraphen mindestens einen Knoten (Flaschenhals). Dadurch verlängert sich die Länge der flussvergrößernden Wege im Restgraphen um mindestens 1. Zum Vergleich: Bei Ford-Fulkerson mit Breitensuche stellst du sicher, dass die Länge eines solchen fv-Weges nicht kleiner wird. Weil du aber nicht alle kürztesten fv-Wege pro Iteration vestopfst, sondern nur einen, kann es auch sein, dass es danach noch fv-Wege gibt, die so lang sind, wie der, den du zuvor berechnet hast. Bei Dinitz sind die mind. 1 größer und hast dadurch eine bessere Laufzeitschranke.

[YtKM]

Danke für die sehr gute Erklärung. Vor allem die Hintergründe sind mir damit nochmal klar geworden.

[O.D.]

Wie bilde ich mit Hilfe der Definition ein korrektes Niveaunetzwerk und was genau ist der Sinn des Netzwerkes?

Ein Niveaunetzwerk ist nur ein in der Quelle gewurzelter Breitensuchbaum. Insbesondere ist es wirklich ein echter Baum (also ein DAG).

[Commo]

Insbesondere ist es wirklich ein echter Baum (also ein DAG).

Wenn man die Senke entfernt *klugscheiß*

[O.D.]

Insbesondere ist es wirklich ein echter Baum (also ein DAG).

Wenn man die Senke entfernt *klugscheiß*

Wieso das?

[HE]

Das ist sowieso kein echter Baum, jedenfalls nicht im konventionellen Sinne. Gegeben seien 4 Knoten q,u,v,s, so dass q mit u, q mit v und u,v jeweils mit s verbunden sind. Dann ist das gleichzeitig auch das Niveaunetzwerk, aber s hat keinen eindeutigen Vater-Knoten.

[O.D.]

Stimmt, Du hast recht. Aber es ist ein DAG.