5.9

[buechsengustel]

poste hier mal meine lösung zur diskussion

ich hab zuerst die gewicht-matrix aufgestellt - die ist natürlich symmetrisch


x a b c d e f g
-----------------------------------
a x 3 10 7 17 9 12

b x 7 4 14 6 9

c x 5 7 9 4

d x 10 4 9

e x 10 7

f x 13

g x


dann bin ich nach kruskal vorgegangen um einen MST zu finden
(a, b), (b, d), (d, f), (c, g), (c, d), (c, e)
kanten verdoppeln, richtung geben --> eulertour
und das fertige ding sieht dann so aus (gesamtgewicht: 46)

[a.menace]

Ich habe auch genau so aber wir können auch (g,e ) statt (c,e) verwenden also das muss nicht eindeutig sein oder...

[abumaster]

nein muss nicht eindeutig sein, du kannst ja auch eine beliebige Eulertour wählen:
ich hab z.b. a-b-d-c-g-e-f-d-a als tour

[Freeek]

nein muss nicht eindeutig sein, du kannst ja auch eine beliebige Eulertour wählen:
ich hab z.b. a-b-d-c-g-e-f-d-a als tour

Hast du dich vielleicht bei deiner Tour verschrieben ? Wenn nicht, wieso kommst du 2 mal bei D vorbei ? Blicke noch nicht ganz da durch ...

Greetz, :confused: Freeek

[tschurlo]

Ich glaub auch, dass abumaster sich einfach vertippt hat.


Nochmal nachgedacht -> vielleicht kann man da was verwechseln:

ad Eulertour: bedeutet, dass man jede KANTE nur genau einmal benutzen darf
Da darf man schon einen Knoten mehrmals besuchen, tun wir ja auch, wenn wir den Kanten eine Orientierung geben, da wir ja einmal zum Knoten hin und dann wieder weg muessen und es ja, da es ja auch sein kann, dass ein Knoten mehr als einen Nachbarn hat.

ad Rundreise: jeden KNOTEN nur einmal besuchen (also in jede Stadt nur einmal)!
[gibts da nicht auch einen Fachbegriff, Hamiltonsche Linie oder so?]


Bin auch eher dem Prinzip gefolgt, mich mal eher nach rechts zu bewegen und habe dieselbe Tour wie abumaster rausbekommen, nur mit dem Unterschied, dass ich das letzte d nicht drinnen habe:
a-b-d-c-g-e-f-a
Mir kommen als Gesamtkosten 42 heraus, wenn ich mich nicht verrechnet habe.

lg

[chri_le_roux]

Hey !!!

Habe das selbe Ergebnis wie tschurlo.
Meine Tour a, b, d, c, g, e, f, a
Gesamtkosten: 42.

Ich glaube das muesste so passen. Odr ???

[the_unclean]

dann bin ich nach kruskal vorgegangen um einen MST zu finden
(a, b), (b, d), (d, f), (c, g), (c, d), (c, e)
kanten verdoppeln, richtung geben --> eulertour
und das fertige ding sieht dann so aus (gesamtgewicht: 46)

wenn du allerdings nur nach kruskal vorgehst, dann entsteht kein mst, weil du bei kante nach punkt c zwischen g, und e entscheiden kannst
und (c,g)=4 billiger ist als (c,e)=7
;)

[tschurlo]

Haeh?? Wieso soll bei Kruskal kein MST entstehen? Das waer fuer mich doch jetzt relativ neu! Du nimmst natuerlich die Kante mit dem geringeren Gewicht auf, aber das steht im Algorithmus explizit so drinnen! Nur darf kein Kreis dabei entstehen, dann muss man sich natuerlich die naechste Kante vornehmen und die, wo ein Kreis entstehen wuerde, verwerfen.
Oder hab ich da jetzt falsch verstanden?

[Christoph]

Auch mögliche Lösung wäre:

d-c-e-f-b-a-g-d

SUM Kantengewichte = 5 + 7 + 10 + 6 + 3 + 12 + 9 = 52


Orientierung stimmt, kein Knoten doppelt
Algo. Güteklasse 2, d.h. kann auch doppeltes Optimum ausgeben

scheint relativ "lange" zu sein ist aber genauso gültig oder ?

[zungerl]

poste hier mal meine lösung zur diskussion

ich hab zuerst die gewicht-matrix aufgestellt - die ist natürlich symmetrisch
x a b c d e f g
-----------------------------------
a x 3 10 7 17 9 12

b x 7 4 14 6 9

c x 5 7 9 4

d x 10 4 9

e x 10 7

f x 13

g x
dann bin ich nach kruskal vorgegangen um einen MST zu finden
(a, b), (b, d), (d, f), (c, g), (c, d), (c, e)
kanten verdoppeln, richtung geben --> eulertour
und das fertige ding sieht dann so aus (gesamtgewicht: 46)
hy,
mich plagt grade die Frage, wie ich auf die einzelnen WErte in der Matrix komme! M(i,j) = |x(i) - x(j)| + |y(i)+y(j)| -- würde für mich bedeuten, da ich ja a(1,8) und b(4,8) gegeben habe --> =|1 - 4| + |8 + 8| = |13| ..hmm, irgendwo happert da meine Denkweise :hewa: , wer sagt mir bitte wo?


(edit und hirnschlag) da hab ich wohl ein - mit einem + verwechselt! Naja, man sollte halt auch abschreiben können :D :ausheck: (/edit hirn weich)
lg, Z

[chri_le_roux]

Hello !!!

du hast einen fehler bei der formel

M(i,j) = |x(i)-y(j)| + |y(i)-y(j)|

dann passts |1-4| + |8-8| = 3 + 0 = 3

mfg

[zungerl]

und wie genau funktioniert jetzt diese Eulertour?

Z

[Flowyes]

the_unclean:
...wenn du allerdings nur nach kruskal vorgehst, dann entsteht kein mst, weil du bei kante nach punkt c zwischen g, und e entscheiden kannst
und (c,g)=4 billiger ist als (c,e)=7

tschurlo:
Haeh?? Wieso soll bei Kruskal kein MST entstehen?...
Kruskal findet natürlich einen MST (sers the_unclean :D ) Dieser ist sogar eindeutig... (Bem: Die Eindeutigkeit muss im Algemeinen nicht sein, wenn nicht alle Kantengewichte verschieden sind)

[Berni]

Hey !!!
Gesamtkosten: 42.


wieder gelöscht, hab mich verzeichnet...

[Mr. Zet]

ganz kurze aber recht "blöde" frage:

hatte UE am montag, und das bsp ned angegeben, weil ich erst am vormittag begonnen hab mit den bsp und nimmer fertig worden bin....

aber: was bedeutet "vollständiger Graph" inder Angabe?

Ich glaube es heißt, dass von jedem knoten zu jedem knoten eine kante existiert
meine kollegen haben aber gemeint das bedeutet es existiert von jedem knoten ein weg zu jedem knoten
(was meiner meinung nach dann aber "nur" ein zusammenhängender graph wäre, und für das bsp keine brauchbare angabe)

wer hat jetzt recht?

würd das bsp nämlich doch noch gern machen.. irgendwann muss es ja sowieso sein ;)

[Flowyes]

DU hast recht ;)
Ein Graph heißt vollständig, wenn je 2 Knoten durch eine Kante verbunden sind:
Also wenn gilt:
Es ex. (u,v) € E für alle u, v € V
---
Weg wäre falsch, weil das wär nur zusammenhängend, wie du sagst.

[Petzi]

ich hab als Eulertour (a,b), (b,d), (d,c), (c,g), (g,e), (e,f), (f,a)

müsste doch auch stimmen oder??