H5.5

[robert.n]

Dieser Satz ist das Problem: "Andere Kanten von der linken in die rechte Komponente gibt es nicht."

Der Rest ist ja in Ordnung.^^

[bruse]

Na wenn ich die beiden beschriebenen Kanten entferne kann man von links nicht mehr nach rechts. Wobei Links im Zweifelsfall alle Knoten sind zu denen man von der Quelle kommt, rechts die, von denen man die Senke erreichen kann. Es gibt wohl noch Kanten andersrum, aber die interessieren ja niemanden...

[linn]

für V'={q,1,2,4,5} und V''={3,S}:

- ist die Kapazität des Kantenschnittes 10, da die Kapazitäten der Kanten die von V' nach V'' führen zusammenaddiert werden. (die Kanten von V'' nach V' werden ignoriert).
- ist der Fluss durch den Kantenschnitt 10. Beim Fluss wird zwar die Differenz beider Richtungen betrachtet, aber anstatt die Kapazitäten der Kanten zu addieren werden die flüsse in den Kanten addiert.

nochmal zur berechnung:
kapazität des schnittes ist die summe der kapazitäten in Richtung Q->S, also 5+5. (die 5en kommen von den Kapazitäten)
Fluss durch den Schnitt ist 5+5-0 ("andere" 5en als oben, nämlich die für die Kantenflüsse)

Für dieses V' und V'' gilt also f=c und der Fluss ist maximal.

[burgi]

ich glaube ich habe das verständnisproblem was kantenschnitte anbelangt erfasst, bel kantenschnitte bringen jeweil eine obergrenze fuer den fluss, d.h. aber nicht dass der jeweilige kantenschnitte die exakte obergrenze ist ! sagen wir bspl also es gibt 3 kantenschnitte einen mit fluss 20 einen mit 11 und einen mit 12, der maximale fluss im graphen ist 11 ! alle drei kantenschnitte bringen einen obere grenze nur dass nur einer der drei eine "scharfe" grenze liefert , seh ich des richtig ?

[robert.n]

Na wenn ich die beiden beschriebenen Kanten entferne kann man von links nicht mehr nach rechts. Wobei Links im Zweifelsfall alle Knoten sind zu denen man von der Quelle kommt, rechts die, von denen man die Senke erreichen kann. Es gibt wohl noch Kanten andersrum, aber die interessieren ja niemanden...

Wieso sollte man die Kanten entfernen?!

Kantenschnitt bedeutet hier doch, dass man die Knotenmenge des Flussgraphen in genau 2 disjunkte Teilmengen S und T zerlegt, sodass die Quelle (s) Element von S und die Senke (t, target) Element von T ist. Der Kantenschnitt geht dann quasi durch die Kanten (u, v) mit u€S und v€T, also diejenigen Kanten, die die eine Hälfte des Flussgraphen mit der anderen verbinden.

Du hast gesagt, dass es zwischen den 2 Komponenten keine anderen Kanten gibt. Das bezieht sich aber auf einen ganz konkreten Kantenschnitt ("von DER linken in DIE rechte Komponente"), daher die Verwirrung. Man kann den Graph ja auch anders aufteilen... deine Aussage klingt aber so, als gäbe es hier einen einzigen eindeutigen Kantenschnitt.
Also ist das ganze einfach nur ein Missverständnis. (Zusatz: welches inzwischen ja geklärt wurde )

[linn]

Hmm, und wir müssen da wirklich zig mal den selben Graphen zeichnen?

[robert.n]

Hmm, und wir müssen da wirklich zig mal den selben Graphen zeichnen?

Mein Tutor hat mir heute nochmal eine Mail geschrieben und da heißt es:

- die einzelnen zunehmenden Wege müssen in den Graphen eingezeichnet werden
- dabei dürft ihr mehrere Wege in einen Graphen einzeichnen, solange sie sich nicht überschneiden und halt immer einen neuen Graphen malen, wenn es zu ner Überschneidung kommen würde.
- und dann am Ende den fertigen Graphen angeben

Ich halte das ja für totalen Overhead, aber wen interessiert das...

(Ich habe es bis jetzt so gemacht, dass ich den Flussgraphen (=>Ergebnis) mit jeweils c(u,v) und f(u,v) sowie den Restgraphen (=>um zu zeigen, dass es keinen zunehmenden Weg mehr gibt) gezeichnet habe (also 2 Graphen). Dazu noch eine Liste der zunehmenden Wege (S -> A -> ... -> P/T: X) die der Algorithmus in den jeweiligen Schritten um den Wert X erhöht hat (=>für den Ablauf des Algorithmus bzw. wie man zum Ergebnis gekommen ist).)

[bruse]

Das dürfte dann zu Punktabzügen führen.

Wenn man es geschickt anfängt muss man den Graphen vielleicht zwei, drei mal zeichnen, wenn man die kompakte Notation verwendet und seine zunehmenden Wege schlau wählt. Bei sich überschneidenden zunehmenden Wegen muss zwingend neu gezeichnet werden. Der Grund ist, dass sonst nicht mehr einfach nachvollziehbar ist, wo welcher zunehmende Pfad verläuft. Bevor hier die Debatte losbricht: Es geht ja nicht nur darum, dass der Tutor nachvollzieht, das jemand den Algorithmus verstanden hat, sondern auch darum, eine klare Darstellungsart für den Algorithmus zu lernen. Natürlich könnte man (darf aber in GDI2 nicht!) z.B. mehrere Farben verwenden. Dann kommen aber die Experten die gepunktet und gestrichelt verwenden, weil sie nur eine Farbe haben usw. (Ihr glaubt gar nicht was manche für Schmierereien abgeben...). Also: Neu zeichnen!

[Michael_R]

Natürlich könnte man (darf aber in GDI2 nicht!) z.B. mehrere Farben verwenden.

Puh, damit hast Du mich vor Punktabzug bewahrt

Also die Tage nochmal hinsetzen und neu machen

Danke