06: Haus vom Nikolaus / The House of Saint Nicholas

  • Da hier noch nichts gepostet wurde, werde ich mich mal "erbarmen"! ;)

    Ich habe mich sehr über diese Aufgabe gefreut, da ich meine im vergangenen Semester gesammelten Erkenntnisse im Bereich der Graphentheorie (Stichwort: Eulerweg) anwenden konnte (also folgt nun eine vielleicht etwas informatische Lösung):


    Ein Weg, der sich in einem Zug ablaufen lässt, ohne dass ein Abschnitt doppelt gegangen wird (wie beim originalen zweidimensionalen "Haus vom Nikolaus"), ist ein sogenannter Eulerweg.

    Jedes Wegnetz ist ein Graph, jeder Teilweg eine Kante und jede Stelle, von der mind. eine Kante ausgeht, ein Knoten. Die Anzahl der Kanten, die von einem Knoten ausgehen, nennt sich Knotengrad.


    Die Bedingungen für einen Eulerweg sind nun die, dass im gesamten Graphen entweder ausschließlich gerade Knotengrade vorliegen (in dem Fall wäre es sogar ein Eulerkreis, d.h. Startpunkt = Endpunkt) oder exakt zwei ungerade, wobei einer der beiden Knoten den Start- und der andere den Endpunkt darstellt.


    Auch, wenn es sich hier um dreidimensionale Körper handelt, kann man die Netze der Polyeder dennoch als zweidimensionale Graphen betrachten, indem man jeweils von zwei Kanten, die später aneinandergeklebt würden, nur eine berücksichtigt und die andere streicht.


    Wenn man das Ganze geschickt auspendelt und es schafft, 0 oder 2 Knoten mit ungeradem Grad zu erzeugen, kann man für die Netze A und B einen Eulerweg konstruieren. Da ich meine handschriftlichen Notizen/Kritzeleien vom 06. Dezember leider verlegt habe, habe ich mir jetzt mal nur die Mühe gemacht, Netz A am PC zu rekonstruieren (und habe die jeweiligen Knotengrade dazu geschrieben), da ich denke, das sollte zur Demonstration ausreichen: https://imgur.com/a/BOGvRHp

    (Die eingekreisten Knoten stellen dabei Start- und Endpunkt dar)


    Fährt man hingegen bei Netz C und D exakt auf diese Weise fort, so wird einem schnell auffallen, dass aufgrund ungünstiger Kantenverteilungen in beiden Netzen garantiert mindestens 3 Knoten mit ungeradem Grad existieren müssen.

    Somit scheiden diese beiden Grundrisse für den Nikolaus aus und die korrekte Antwort ist Nr. 2, "Nur bei den Entwürfen A und B kann er das schaffen." :)

  • hm - ich habe die Ecken des 3-Dimensionalen Körpers durchnummeriert (alphabethisch). Dadurch kommt es im 2-D Graphen zu mehreren Knoten, die z.B. "E" heißen, aber im 3-D Körper zur selben Ecke gehören. Die durch das 3-D-kleben aufeinanderfallenden Kanten habe ich das "Gewicht" 1/2 gegeben, während eindeutige Kanten des 2-D Graphen, die nicht mit anderen Kanten zusammenfallen das "Gewicht" 1 bekommen haben.

    Nach dieser Vorbereitung habe ich zu allen, ggf. aufgesplitteten Knoten ("A", "B", ....) des 2-D Graphen den Grad bestimmt, indem ich die Gewichte ihrer Kanten aufaddiert habe.

    Nur für die Netze a und b gab es einen Eulerweg mit exakt 2 Knoten mit ungeradem Grad. Für die Netze c und d gab es mehr als 2 Knoten mit ungeradem Grad und damit keinen Eulerweg.