Christophides Heuristik

  • Ich habe noch ein paar Fragen zur Chridtopides-Heuristik


    Aus den Prüfungsangaben vom 19.01.2001 habe ich folgende Angaben:


    Angabe


    Daraus ist die Christophides Heurisik angewendet werden.
    Ich würde nun hergehen und mit Union Find einen Minimalen Spannbaum aufzeichnen. Der schaut dann so aus


    MST


    Nun ist die Frage, wie genau komme ich auf meine Knotenpaare. Mittels Perfekt Matching muss ich ja den Knoten mit ungeradem Grad einen eindeutige Partner zuordnen oder?
    Kann ich sie da bekiebig verbinden? z.b. ec und ad oder ad und ab, cb?
    Das mach ich ja nur damit ich eine Eulertour finden kann?
    Und vor allem wenn ich das habe wie kommen ich dann auf den Lösungsgrafen. Leider ist das Skriptum da nicht hilfreich. Schon alleine Deshalb weil die Kanten der Graphen nicht gewichtet sind.


    Ich hoffe ihr könnt mir weiterhelfen. Vielen Dank

  • die bilder sind nicht zu sehn. tripod erlaubt wohl "fremden" webseiten nicht auf die bilder zuzugreifen. am besten du ersetzt den IMG-tag mit dem URL-Tag... oder noch besser: uni-account verwenden. :D
    ======================
    Original geschrieben von Calida
    Ich habe noch ein paar Fragen zur Chridtopides-Heuristik


    Aus den Prüfungsangaben vom 19.01.2001 habe ich folgende Angaben:


    http://reinhardtmuehlwerth.tripod.com/forum.bmp



    Daraus ist die Christophides Heurisik angewendet werden.
    Ich würde nun hergehen und mit Union Find einen Minimalen Spannbaum aufzeichnen. Der schaut dann so aus


    http://reinhardtmuehlwerth.tripod.com/Forum_MST.bmp


    Nun ist die Frage, wie genau komme ich auf meine Knotenpaare. Mittels Perfekt Matching muss ich ja den Knoten mit ungeradem Grad einen eindeutige Partner zuordnen oder?
    Kann ich sie da bekiebig verbinden? z.b. ec und ad oder ad und ab, cb?
    Das mach ich ja nur damit ich eine Eulertour finden kann?
    Und vor allem wenn ich das habe wie kommen ich dann auf den Lösungsgrafen. Leider ist das Skriptum da nicht hilfreich. Schon alleine Deshalb weil die Kanten der Graphen nicht gewichtet sind.


    Ich hoffe ihr könnt mir weiterhelfen. Vielen Dank

    Otto: Apes don't read philosophy. - Wanda: Yes they do, Otto, they just don't understand
    Beleidigungen sind Argumente jener, die über keine Argumente verfügen.
    «Signanz braucht keine Worte.» | «Signanz gibts nur im Traum.»


    Das neue MTB-Projekt (PO, Wiki, Mitschriften, Ausarbeitungen, Folien, ...) ist online
    http://mtb-projekt.at

  • @uni-account:


    du bekommst von der Uni 100MB webspace, zugänglich per SSH (=secure shell, so eine art sichereres FTP bzw. Telnet), client für windows gibts u.a. auf gd.tuwien.ac.at zum download (oder im Google nach "PuTTY" suchen.


    username: e1234567
    pass: deinpasswort
    server: stud3 bzw. stud4.tuwien.ac.at

    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  • Perfect Matching bedeutet, dass man jedem Knoten mit ungeradem Grad (deren Anzahl ja immer gerade ist), genau einen anderen Knoten mit ungeradem Grad zuordnet. Dabei muss das Gesamtgewicht, der hinzugefuegten Kanten minimal sein.


    Wenn man die Knoten aus dem Beispiel "Zeilenweise" von links nach rechts numeriert, haben die Knoten 1, 2, 4 und 5 ungeraden Grad. Das heiszt man koennte folgende Paare bilden:


    - (1, 2) und (4, 5): Gesamtgewicht 36 + 54 = 90
    - (1, 4) und (2, 5): Gesamtgewicht 36 + 50 = 86
    - (1, 5) und (2, 4): Gesamtgewicht 71 + 51 =122


    Man sieht also, dass es am billigsten ist, wenn man die Kanten (1, 4) und (2, 5) hinzufuegt.


    Danach hat jeder Knoten einen geraden Grad -> es existiert ein euler'scher Kreis.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!