Zur Haupt­na­vi­ga­ti­on sprin­gen [Alt]+[0] Zum Sei­ten­in­halt sprin­gen [Alt]+[1]

Ha­mil­ton­krei­se – Übun­gen – Lö­sung

  1.  

    Abbildung 1 Lösung zur Übung Hamilton-Kreise

  2. Eu­ro­pa per Bahn

    Abbildung 2 Lösung zur Übung Hamilton-Kreise

    Ja, der Ha­mil­ton-Kreis zeigt zwei mög­li­che Rou­ten. Wenn man wei­te­re su­chen möch­te, kann man mit dem ge­fun­de­nen Ha­mil­ton­kreis, auch einen iso­mor­phen, kreis­för­mi­gen Gra­phen zeich­nen (siehe oben).

  3. Re­gel­mä­ßi­ge Fünf­ecke

    Abbildung 3 Lösung zur Übung Hamilton-Kreise

    Oben sind die vier mög­li­chen geo­me­tri­schen For­men zu sehen. Bei der ers­ten und drit­ten Figur könn­te man in jedem der fünf Kno­ten star­ten und würde die glei­che ro­ta­ti­ons­sym­me­tri­sche Figur er­hal­ten. Bei der zwei­ten und vier­ten Figur ver­hält es sich an­ders. Hier er­hält man je­weils fünf ver­schie­de­ne Ha­mil­ton­krei­se, wenn man an un­ter­schied­li­chen Kno­ten be­ginnt. Ins­ge­samt gibt es also 1+5+1+5=12 Ha­mil­ton­krei­se in einem voll­stän­di­gen Gra­phen mit fünf Kno­ten.

  4. LKW-Tour

    a) Der Rou­ten­vor­schlag des Fah­rers wäre 333 km lang, es gibt eine kür­ze­re Route.

    Abbildung 4 Lösung zur Übung Hamilton-Kreise

    b) Der be­wer­te­te Graph ist ein voll­stän­di­ger Graph mit 4 Kno­ten und 6 Kan­ten. Er be­sitzt die 3 ab­ge­bil­de­ten Ha­mil­ton­krei­se, deren ent­spre­chen­de Rou­ten über­prüft wer­den müs­sen:

    ABCDA (bzw. ADCBA): 333 km

    ABDCA (bzw. ACDBA): 442 km

    ADBCA (bzw. ACBDA): 329 km

    Der Fah­rer soll­te die Städ­te also in der Rei­hen­fol­ge D,B,C an­fah­ren.

    Hin­weis: Die An­zahl der Ha­mil­ton­krei­se in voll­stän­di­gen Gra­phen mit n=3,4,5… Kno­ten wird schnell grö­ßer. Bei 5 Kno­ten sind es 12 (vgl. Auf­ga­be 3), bei 6 Kno­ten be­reits 60 …, ohne ge­eig­ne­te Al­go­rith­men käme man nicht weit!

  5. Ha­mil­tons Spiel­brett

    Abbildung 5 Lösung zur Übung Hamilton-Kreise

    Es gibt viele Mög­lich­kei­ten, hier sind drei ab­ge­bil­det. Ha­mil­ton nann­te sein Spiel üb­ri­gens „Tra­vel­ler's Do­de­ca­he­dron or A Voya­ge Round The World“. Es ging darum, eine vom Mit­spie­ler be­gon­ne­ne Route durch 20 Me­tro­po­len der Welt zu einem Ha­mil­ton-Kreis zu er­gän­zen.

    6.  

     

    Ha­mil­ton­krei­se – Übun­gen – Lö­sung: Her­un­ter­la­den [odt][353 KB]

    Ha­mil­ton­krei­se – Übun­gen – Lö­sung: Her­un­ter­la­den [pdf][272 KB]

     

    Wei­ter zu Gra­phen als Ta­bel­len