WS1617.pdf

Exams
Uploaded by Anonymous User at 2018-01-28
Description:

Klausur Lösung WS 16/17

 +1
182
10
Download
No area was marked for this question
Aufgabe 1: Der Fluss ist komplett falsch - Maximaler Fluss ist 10.
No area was marked for this question
Bei Aufgabe 4d, die müsste doch falsch sein da ein perfektes maximales Matching nichts mit dem Gewicht zu tun hat, und wenn müsste man beim Matching minimieren und bei der cliquenpartitionierung maximieren, oder?
-> Skript Seite 60, Bemerkung 7.1./Punkt 4 Antwort ist also: richtig
Wenn da steht es ist ein maximales Matching gesucht maximiert man natürlich. Wohingegen man bei einem minimalen Matching minimiert.
No area was marked for this question
Zu Aufgabe 2d) Müsste in der 3. Iteration als Vorgänger nicht die "3" stehen?
meiner Meinung nach ja, denn ich komme nun ja von der 3 schneller an die 5.
Ja
Ist die Richtung der Kante irrelevant? also kann man obwohl der Pfeil von 3 zu 2 geht trz. die Leitung nutzen um Fluss von 2 nach 3 zu schicken?
View 3 more comments
In Residualnetzwerk 3 passt noch alles. In 2 Fließt hinein: 4 Einheiten aus s und 1 Einheit aus 3. Aus 2 heraus fließt: 4 Einheiten in 5 und 1 Einheit in 6. Also was die Knoten s,3,2 angeht ist die Flusserhaltungsbedingung erfüllt. Und natürlich hast du Recht, dass unten im Endergebniss (Fluss4) Die Flusserhaltungsbedingung nicht efüllt wird. In 2 fließen nämlich 7 Einheiten hinein und nur 5 wieder hinaus.
@ Anonymer Währungswechsel. Du kannst die Kante nicht nutzen, um den einen Fluss von 2 zu 3 zu schicken. Du kannst aber einen Fluss, den deu vorher von 3 zu 2 geschickt hast wieder "zurückholen", dass der Fluss von 3 zu 2 0 ist und die eine einheit zu 5 schicken. Was hier im Endergebnis steht (2 Einheiten von 3 zu 2) ist aber falsch, denn 3 bekommt ja nur eine Einheit aus s zur verfügung.
Könnte man die eine Einheit auch anstatt von 5 zu t, von 5 zur 7 fließen lassen und dann von der 7 5/5 zu t, oder wäre die a dann nicht mehr richtig gelöst?
View 2 more comments
Ich hätte den Fluss zwischen s und 4 von 4 auf 3 geändert...
Glaube hier ist es egal wie man es macht. Die Frage ist nur, ob das "unmittelbar" heißen soll, dass möglichst wenig geändert werden muss.
No area was marked for this question
Aufgabe 2 c) wie kommt genau auf die Werte?
Am besten die Angabe richtig lesen, da wird es erklärt "Kürzester Weg ausgehend von 1" müsste normal mit Dijkstra bzw. Tripel-Algorithmus berechnet werden, kann man hier aber einfach ablesen.
muss es hier nicht 10 mit Vorgänger 3 heißen?
ja, müsste Vorgänger 3 sein
Wieso beginnt die neue Rundreise immer mit A,B?? Man ersetzt doch die Kante (A,F) und (D,E) durch die Kanten (A,D) und (F,E)...wieso fängt die Rundreise dann nicht mit A,D,...an??
ganz einfach: weil in der Teilaufgabe a, steht "Ausgehend vom Standort A" Also das einfachste vorgehen ist, die Richtung genau so aufzuschreiben, wie die Kante, die gegeben ist, also: r=(A,F,E,D,C,B,A) dann ersetzt zu (A,F) und (E,D) (achtung: reihenfolge beachten! es muss genauso dortstehen, wie die Rundreise in r durchlaufen wird) durch (A,E) und (F,D) zur veranschaulichung: r = (A,F, E,D, C,B,A) r*=(A,E, F,D, C,B,A)
Die Lösung in der Klausur ist doch aber dann auch richtig? Weil wir sollen ja eigentlich die Rundreise optimieren die wir in a) bestimmt haben. Diese wäre ja r=(A,B,C,D,E,F,A).
sollten D und E hier nicht in der vertauschten Reihenfolge sein?
No area was marked for this question
Zu 1 b : wie kann es sein dass in knoten 3 eine Einheit hineinfließt jedoch 3 wieder hinausfließen?
View 1 more comment
Ich meine nicht im residualnetzwerk sondern beim fluss 4
Im Residualnetzwerk 3 ist zu erkennen dass der Fluss von 3 nach 2 umgekehrt wird (quasi ein Rückfluss). Also wird der Fluss von 3 nach 2 in Fluss 4 um 1 reduziert, also auf 0/2. Somit ist das Problem gelöst.