G15

[Millencolin]

ich habe den konten buchstaben gegeben oben links a rechts b, in der mittlere c und unten d

so hier hab ich gewichtete kanten! zuerst ordne ich die kanten nach ihren kantengewichten (7, 10, 11, 12, 14, 18).
jetzt erstelle ich den minimal aufspannenden baum (sprich einen graphen der alle knoten berührt und der kreisfrei ist !!!)

hab ich das getan bekomm ich den graphen (c,a) (c,b) (c,d)

jetzt nur mehr kannten verdoppeln und von a, b und d starten

die "günstigste" tour (d,c) (c,a) (a,b) (b,d) ergibt 47

[michi204]

das mit dem minimal aufspannendem baum ist der kruskal-algorithmus aus algodat, im mutzel/raidl-skriptum von letzem jahr auf seite 123.

ich frage mich nur, wozu man das hier braucht.. weil du es ja nachher auch nicht wirklich weiterverwendest



wozu verdoppelst du eigentlich die kanten?
mir kommt außerdem noch eine zweite gleichwertige tour heraus: |acdba|=47



lg michi

[Millencolin]

gleichwertige tour heraus: |acdba|=47deine is ja die gleiche tour, nur halt in die andere richtung, und start bei knoten "a"

[michi204]

deine is ja die gleiche tour, nur halt in die andere richtung, und start bei knoten "a":D :D peinlich... du hast natürlich recht.

aber warum du kanten verdoppelst verstehe ich noch immer nicht..

lg michi

[Pyro]

also ich komm auch nur auf 47 ......... auch mit der gleichen tour, ..... ich glaub das is auch die einzige! einfach den längsten und den kürzesten weg meiden und fertig ;)


MfG
Pyro

[Millencolin]

ich hab die kanten verdoppelt, damit ich eine tour finde!!
vielleicht hilft die graphik (scann)

die drei sind die einzigen möglichkeiten eine günstige tour zu finden,
bei der günstigsten mit kosten 47 kann ich natürlich
von a, b, c od. d starten (und das ganze in beide richtungen)

acdb
bacd
cdba
dbac

und andere richtung

abdc
bdca
cabd
dcab

// anmerkung: die fett geschriebenen knoten sind start- und endknoten

also 8 verschiedene richtige lösungen -> (hoff ich hab mich da jetzt nicht geirrt)

[michi204]

@millencolin:

ach soo meinst du das.. :D

ich habe das einfach als ungerichtete kanten gelassen, dann kann man ja auch in beide richtungen, oder täusch' ich mich da?

lg michi

[Millencolin]

> michi204
jep !