24: Nachtwache / Nightwatch

  • Du hast vermutlich vergessen, dass wenn man in A startet, man über die zwei geradzahlig oft begangenen Wege nach T gehen kann und schließlich in dieser Variante in C endet.


    Somit sind von A aus die Endpunkte C oder T (je nachdem, ob man die beiden geradzahligen Weg zwischen A und C bzw. A und T legt), von B bzw. D aus die Endpunkte J, S oder U (einen geradzahligen Weg von B bzw. D nach C und einen geradzahligen Weg von T nach J, S oder U) und von C aus die Endpunkte A, E, F, O, J, S erreichbar (von T aus zwei geradzahlige Wege nach A, E, F, O, J oder S).


    Damit ergeben sich insgesamt 9 mögliche Endpunkte: A, C, E, F, J, O, S, T und U.

  • Die kritischen Knoten sind C und T, da sie eine ungerade Anzahl an Kanten haben und somit entweder einen der doppelt oder vierfach durchlaufenen Wege "verbrauchen", oder Start- / Endpunkt sein müssen.


    Da alle Wege mindestens einmal durchlaufen werden müssen, sind die ungeradzahlig vielfach durchlaufenen Wege (3mal oder 5mal) irrelevant. Sie führen zu dem Knoten zurück, an dem Winfried nach dem einmaligen durchlaufen gestanden hat. Die ungeradzahlig durchlaufenen Wege (>1) können deshalb für die Lösungsfindung komplett ignoriert werden.


    Für Startpunkte A und B wird ein geradzahlig durchlaufener Weg bei C "verbraucht". Winfried endet dann in T mit noch einem übrigen geradzahligen Weg "im Köcher". mit diesem kommt er zu J, S und U.

    Geht andersherum (also erst nach T und dann nach C), so scheitert er bei Start in B, da er T nicht so verlassen kann, dass er in C enden könnte. Bei Start in A kann er T über J und das "verbrauchen" eines geradzahlig durchlaufenen Weges verlassen. Dadurch bekommt J aber eine Kante mehr und wird jetzt selber ungeradzahlig. Um J dann zu verlassen, (J->A) benötigt er deshalb einen weiteren geradzahlig durchlaufenen Weg, so dass er nur genau in C enden kann.


    Für Startpunkt in C kann er ohne einen einzigen Weg mehrfach zu durchlaufen nach T gelangen, hat in T also noch zwei geradzahlig zu durchlaufende Wege "im Köcher". Mit diesen kommt er max. zwei Knoten weit also nach S, J, E, A, F, T und O.


    Für Start in D verbraucht er einen geradzahlig durchlaufenen Weg bei C und kommt somit nicht mehr von T weg bzw. endet auf den bereits bekannten Knoten.


    Endknoten sind somit S, J, E, A, F, T, O, U und C insgesamt 9 Stück.

  • Ja genau, habe das direkt auf dem Aufgabenzettel farbig gelöst: Man stelle sich einen neuen Graphen mit den Zusatzwegen vor.

    Dort wo der 2fach bzw 4fach Weg angebaut wird "switchen" jeweils die angrenzenden Ecken (Punkte) von ungerade nach gerade.


    Insgesamt darf es für einen Eulerweg maximal 2 ungerade Ecken geben. Die gibt es schon (C und T). Daraus folgt, dass der 2fach/ 4fach Weg nur an T und C (bei C: wegen Start im Norden bleiben!) angebaut werden darf: Verschieben der ungeraden Ecke um eins, bzw. per Verlängerung (direkt hintereinander von T oder C ausgehend): Verschieben der ungeraden Ecke um zwei:


    https://www.dropbox.com/s/hejt…Nachtwache_Euler.JPG?dl=0

  • Du hast vermutlich vergessen, dass wenn man in A startet, man über die zwei geradzahlig oft begangenen Wege nach T gehen kann und schließlich in dieser Variante in C endet.


    Somit sind von A aus die Endpunkte C oder T (je nachdem, ob man die beiden geradzahligen Weg zwischen A und C bzw. A und T legt), von B bzw. D aus die Endpunkte J, S oder U (einen geradzahligen Weg von B bzw. D nach C und einen geradzahligen Weg von T nach J, S oder U) und von C aus die Endpunkte A, E, F, O, J, S erreichbar (von T aus zwei geradzahlige Wege nach A, E, F, O, J oder S).


    Damit ergeben sich insgesamt 9 mögliche Endpunkte: A, C, E, F, J, O, S, T und U.

    Man kann den Endpunkt T auch vom Start in D aus erreichen: D nach I und zurück (2er Weg "verbraten"), dann nach C von C nach I (4er- Weg "verbraten") und dann den Eulerweg von C nach T.

  • Man kann den Endpunkt T auch vom Start in D aus erreichen: D nach I und zurück (2er Weg "verbraten"), dann nach C von C nach I (4er- Weg "verbraten") und dann den Eulerweg von C nach T.

    Stimmt! Geht dann logischerweise auch von B aus (2er nach G), dann regulär nach C und von dort 4er nach G - anschließend normaler Eulerweg von C nach T.