Streufahrzeug [gelöst]

Neue Frage »

KnightMove Auf diesen Beitrag antworten »
Streufahrzeug [gelöst]
Ein Streufahrzeug soll die Straßen einer Wohnanlage abfahren. Da das an- und abschalten des Streuers mühsam ist, will der Fahrer in einem Zug durchfahren - und dazu so wenige strecken wie möglich doppelt befahren. Wie geht er am besten vor?
GMjun Auf diesen Beitrag antworten »

d2/d3/a3/a1/d1/d2/c2/c1/b1/b3/c3/c2/a2

Dabei muß er die Strecke 2x doppelt befahren
 
 
AD Auf diesen Beitrag antworten »

a2-a3-d3-d1-a1-a2-c2-c3-b3-b1-c1-c2-d2 (nicht alle Punkte aufgelistet - jeweils gerade "durchziehen")

dabei werden zwei Strecken doppelt abgefahren: b1-c1 und b3-c3

Kürzer geht es nicht, da 6 Knoten eine ungerade Kantenzahl haben - zwei davon kann man als Start- und Endpunkt nehmen, die anderen vier müssen aber durch Zusatzstrecken verbunden werden, und das sind nun mal mindestens zwei.
kurellajunior Auf diesen Beitrag antworten »

Kurze aber exakte Begründung. (Und schnell wie immersmile ) Magst Du nicht noch ein bisschen die Graphentheorie ausweiten, Arthur... Augenzwinkern

Es gibt also noch eine Menge anderer Lösungen. Interessant wäre vielleicht noch wieviele? Aber das eigentliche Rätsel is gelöst...

Jan
AD Auf diesen Beitrag antworten »

Ich seh gerade erst, dass das ja unter Rätsel eingeordnet wurde - muss ich da jetzt die Lösung herausnehmen, damit andere noch probieren können (bin aus den Regeln noch nicht so recht schlau geworden)? verwirrt
kurellajunior Auf diesen Beitrag antworten »

Stehen doch bereits zwei allerdings spiegelverkehrte Lösungen da, was solls. Augenzwinkern
AD Auf diesen Beitrag antworten »

Ja stimmt, durch nachträgliches Editieren hat ja GMjun seine nichtoptimale Lösung (3x) zu einer optimalen (2x) korrigiert. Big Laugh
KnightMove Auf diesen Beitrag antworten »

Jo - gelöst.
Sciencefreak Auf diesen Beitrag antworten »

Wenn man sich etwas mit Graphentheorie beschäftigt hat ist es wirklich ganz leicht. Man muss einfach nur die Knoten mit ungerade Grad herausfinden und sich überlegen, wie man diese am besten verbindet, dabei muss man eine Verbindung nicht machen, da es nicht gefordert ist wieder am Ausgangspunkt anzukommen. Nun hat man 6 Knoten mit ungerade Grad (a2,d2,b1,c1,b3,c3) und man muss nun 2Paare verbinden, wobei sich ja b1-c1 und b3-c3 geradezu anbieten.
GMjun Auf diesen Beitrag antworten »

Nur soviel dazu, meine erste Lösung war mit drei doppelt befahrenen Strecken, diese habe ich gepostet, zwischenzeitlich suchte und fand ich eine noch kürzere Lösung und dazu benutzt man für gewöhnlich, was aber anscheinend verboten ist, die Editfunktion.
AD Auf diesen Beitrag antworten »

War auch nicht bös gemeint - ich wollte (für spätere Betrachter) nur rechtfertigen, warum ich noch eine Lösung reinstelle, wenn doch schon eine optimale vorliegt, wär ja in diesem Fall irgendwie sinnlos.

P.S.: Nachträgliche gravierende Änderungen kann man ja auch durch "EDIT"-Anmerkungen deutlich kennzeichnen.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »