Warum genau werden die Punkte A und B benötigt, um das Haus des Nikolaus zu vervollständigen?
Guten Tag,
ich stehe vor dem Problem, warum genau die untere Abbildung bei den Punkten A oder B anfangen muss, um in einem Zug ohne Kantenwiederholungen vollständig gezeichnet zu werden.
Mir ist klar, dass ich folgende Kantenfolge haben muss: ACBDCFDAB
oder eben das gleiche auf B angepasst
Erkenntnisse sind, dass sowohl A als auch B ungerade sind und sowohl C als auch D und F gerade sind.
Außerdem überlege ich, ob es mit dem noch angefügtem Satz zu beweisen gilt, oder ob es eine logische Erklärung dafür gibt, welche einfacher wäre und evtl. sogar möglich ist.
Vielen Dank :)
1 Antwort
Die Kantenfolge ist nicht eindeutig, auch nicht wenn man deine Folge auf B anwendet.
Ich zeichne es zum Beispiel so: ACFDBCDAB
Wie du richtig erkannt hast, der der Grad der Knoten A und B 3. Es ist plausibel, dass wenn du einen geraden Grad hast, Ein- und Auskehr sich "aufheben". Ein Knoten mit 5000 Kanten würde 2500 mal angesteuert und wieder verlassen werden.
Bei einem ungeraden Knoten muss deshalb der Graph (/Weg) entweder beginnen oder enden.
Das lässt sich mit der Graphentheorie auch beweisen, allerdings ist es schon zu lange her und die Speicherkapazität brauchte ich irgendwann für andere Dinge.