WS1516.pdf

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

Klausur Lösung WS 15/16

 0
113
5
Download
Wie kommt man da drauf?
also auf den weg
Kann ich hier wirklich den Weg ändern? Denn eigentlich ist ja laut Angabe ein Weg von s-2-C-t vorgegeben. Wenn ich diesen einhalten würde, dann gibt es keinen Weg mehr über D nach t und somit wäre die maximale Flussstärke 3.
View 5 more comments
DU hast übersehen, dass es in der 2ten Iteration immer noch einen Weg im Residualnetzwerk gibt. Der Weg lautet: s-4-C-2-D-t
Lautet dann hier bei e) das Ergebnis auch anders? M=(1,A) (2,C) (2,D) (3,B)???
Da bin ich mir nicht so sicher, wenn die strecke (E,D) nicht existieren sollte, müsste man einen Eulersche Erweiterung einfügen und das geht doch nur bei Strecken die es gibt (man kann ja keine straße dazu erfinden). Demnach müsste die Tour ohne die Strecke (E,D) folgende sein; (A,D,A,E,A), mit Wert 34 bitte Meinungen :)
so hätte ich es auch gemacht
Ist doch falsch oder? Im Skript auf Seite 37 steht: "Finde einen Kantenzug minimaler Länge mit identischem Anfangs- und Endknoten, der jede Kante e 2 E mindestens einmal enthält." Minimal fehlt in der Aufgabe --> Falsch.
köntne man so sehen. Im Zweifel einfach ne Erklärung dazu schreiben, das wird ja bewertet.
A2: b) Hätte man hier nicht, (H,E,D,C,B,A,H) mit der Länge =30 nehmen müssen?
Bei einer Rundreise nach dem Nächster-Nachbar-verfahren nimmt man immer den kürzesten weg von einem Knoten zum nächsten, noch nicht besuchten knoten. da E-C nur die Länge 5 hat, nimmst du das und nicht E-D mit Länge 6. Es geht um den Algorithmus ;) natürlich gibt es kürzere Wege, deswegen optimiert man danach ja mit dem 2-opt
Danke :)