WS1314.pdf

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

Lösung Klausur WS 13/14

 0
88
5
Download
No area was marked for this question
Aufgabe 2 d) Matching wieso ist das neue M= (1.6) (3,8) (2,5) somit fehlt doch die Kante (3,6) die auch eine Matchingkante ist?!
das wird einfach ersetzt. Du wählst ja einen Knoten aus der Menge V1, die kleiner ist als V2 (also hier 1,2,3,4) und der nicht Endpunkt einer Matchingkante ist. Daher gibt es 1 und 4 zur Auswahl. Dann wird von diesem Punkt immer zuerst einen Matchingkante erstellt (1,6) und alle anderen Matchingkanten die auf dem weitern Augmenting Path liegen werden "überschrieben", da du jetzt ein größes Matching hast, was ja besser ist. Alle anderen Matchings, die nicht davon betroffen sind bleiben in der Menge M
Danke! Verstanden!
Ist es nicht Knotenzahl? und was genau heißt K n/2, n/2 ?
ja muss knotenzahl heißen. Kn/2,n/2 bedeutet ein bipartiter Graph, der in der Menge V1 die hälfte alle Knoten (n/2) und in der Menge V2 die anderer Hälfte alle knoten (n/2) hat
Müsste zwischen DA und Kö nicht auch noch eine Verbindung sein?
ja ich habs mit einer Verbindung von DA zum Kö gemacht und dann bei b) auch die Verbindung: Bib - Uni - Kö - ZK - H, weil ich ja von der Uni auch schneller am Kö bin als über DA
Knotenanzahl ist gerade....wenn man durch 2 Teilt (mod 2) und rest = 0 dann ist es eine gerade Anzahl
Es muss gelten: n mod 2 = 0 9 mod 2 = 1 9 ist auch einfach keine gerade Zahl ...
Wieso ist das hier nicht 11? Denn man fährt ja um 6 los und kommt um 17 an...oder nimmt man da immer die tatsächliche Uhrzeit?
Man addiert alle Zeiten zusammen. Sonst würde das ganze ja nicht funktionieren. Denn wenn hier 11 stehen würde, würdest du im nächsten Schritt (Iteration 2) nicht prüfen, ob du über DA schneller ans Ziel kommst. Also immer die tatsächliche Uhrzeit oder die Summe aller bisherigen Fahrzeiten/ Laufwege etc. je nach Aufgabe.