12.7 Hamilton-rásir

Í umfjöllun um Euler-rásir og Euler-slóðir leituðum við að rásum og vegum sem fóru nákvæmlega einu sinni um hvern legg nets. Í þessum hluta leitum við að rásum sem heimsækja hvern hnút nákvæmlega einu sinni. Eins og mörg hugtök netafræðinnar á hugmyndin um rás sem heimsækir hvern hnút einu sinni rætur í leikjum og þrautum. Allt frá 9. öld veltu indverskir og íslamskir fræðimenn því fyrir sér hvort riddari gæti heimsótt hvern reit á skákborði af tiltekinni stærð. Það jafngildir því að heimsækja hvern hnút nets sem táknar skákborðið.

Árið 1857 fann stærðfræðingurinn William Rowan Hamilton upp þraut þar sem leikmenn áttu að finna leið eftir leggjum tólfflötungs (sjá mynd 12.156) sem heimsótti hvern hornpunkt nákvæmlega einu sinni. Skoðum hvernig netafræði varpar ljósi á þessa leiki og hagnýt verkefni á borð við farandsölumannsvandann.

Áður en við skoðum lausn þrautar Hamiltons skulum við rifja upp orðaforða sem við notuðum á mynd 12.157. Gagnlegt er að muna að stefnd rás er rás sem endurtekur hvorki leggi né hnúta.

Markmið þrautar Hamiltons var að finna leið eftir leggjum tólfflötungsins sem heimsækir hvern hornpunkt nákvæmlega einu sinni. Tólfflötungur er þrívíður rúmfræðilegur hlutur þar sem allir fletirnir eru fimmhyrningar, eins og við sáum á mynd 12.156.

Þar sem auðveldara er að sjá fyrir sér tvær víddir en þrjár fletjum við tólfflötunginn út og skoðum leggi og hnúta hans á sléttum fleti. Net A á mynd 12.158 sýnir tvívítt net leggja og hnúta en net B sýnir leysta útgáfu þess þar sem engir leggir skerast. Net B líkist mjög spilaborðinu sem Hamilton hannaði fyrir þrautina.

Við sjáum að þetta er sléttunet því hægt er að leysa það úr flækju. Til að leysa þraut Hamiltons þurfum við að finna rás sem heimsækir hvern hnút einu sinni. Lausn er sýnd á mynd 12.159.

Rás sem endurtekur enga hnúta, eins og sú á mynd 12.159, nefnist stefnd rás. Því má segja nákvæmast að þraut Hamiltons felist í að finna stefnda rás sem heimsækir hvern hnút nets nákvæmlega einu sinni. Þar sem Hamilton bjó þrautina til og leysti hana voru þessar sérstöku rásir nefndar Hamilton-rásir.

Æfum okkur að nefna og greina Hamilton-rásir og aðgreina þær frá Euler-rásum. Mikilvægt er að muna að Euler-rásir fara um alla leggi án endurtekningar en Hamilton-rásir heimsækja alla hnúta án endurtekningar. Hamilton-rásir eru nefndar eftir hnútum sínum eins og aðrar rásir. Dæmi er sýnt á mynd 12.160.

Rásin a → b → c → d í neti Z á mynd 12.160 er ekki Euler-rás; hún sleppir $\mathit{ac}$, svo skilyrðið er ekki uppfyllt. Sumar Hamilton-rásir eru einnig Euler-rásir en aðrar ekki, og sumar Euler-rásir eru Hamilton-rásir en aðrar ekki.

Athugaðu að netið er rás. Rás er alltaf Euler-net því allir hnútar hennar hafa stig 2. Þar að auki er sérhver rás í netinu bæði Euler-rás og Hamilton-rás. Ekki er alltaf jafnauðvelt að ákvarða hvort net hafi Hamilton-rás og hvort það hafi Euler-rás, en við vitum að stór flokkur neta hefur alltaf Hamilton-rásir: fullkomin net. Þar sem allir hnútar fullkomins nets eru aðlægir getum við alltaf fundið stefnda rás sem heimsækir þá alla. Skoðaðu til dæmis stefndu sex-rásina n → o → p → q → r → s í fullkomna netinu með sex hnúta á mynd 12.162.

Þetta er þó ekki eina stefnda sex-rásin í netinu. Við gætum fundið aðra með því að snúa stefnunni við og enn fleiri með því að nota aðra leggi. Hve margar Hamilton-rásir eru þá í $n$fullkomnu neti með n hnúta? Áður en við leysum það verkefni skulum við skoða styttan rithátt sem nýtist okkur.

Á mörgum sviðum stærðfræðinnar þarf að reikna margfeldi á borð við 7 · 6 $7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$· $11\cdot 10\cdot 9\cdot 8\cdot 7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$5 · 4 · 3 · 2 · 1 eða 11 · 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1, þar sem allar teljanlegar tölur frá tiltekinni tölu niður í 1 eru margfaldaðar saman. Ef margfeldið næði frá 100 niður í 1 yrði það mjög langt! Því var tekinn upp styttur ritháttur. Í stað 7 · 6 · 5 · $7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1$4 · $7!$3 · 2 · 1 skrifum við til dæmis 7!, lesið „sjö hrópmerkt“. Margfeldi allra teljanlegra talna frá n niður í $n$1 nefnist með öðrum orðum $n$hrópmerkt n og er ritað n!. $n!$

Snúum aftur að spurningunni um fjölda Hamilton-rása í fullkomnu neti. Í töflu 12.8 höfum við teiknað allar fjórar rásirnar í fullkomnu neti með fjóra hnúta. Munaðu að nefna má rás frá hvaða hnúti hennar sem er, en hér hefjum við heitin á hnúti a.$a$

Tafla 12.8 sýnir að þrjár ólíkar fjögurra rásir eru í fullkomnu neti með fjóra hnúta. Hverja rás má nefna á tvo vegu, með því að lesa hnútana réttsælis eða rangsælis. Þetta skiptir máli því Hamilton-rásir eru stefndar rásir. Þótt rásirnar (a, b, c, d) og (a, d, c, b) séu sama rásin teljast stefndu rásirnar a → b → c → d → a og a → d → c → b → a, sem fara sömu leið í gagnstæðar áttir, ólíkar stefndar rásir eins og sýnt er í töflu 12.9.

Stefndu fjögurra rásirnar sex í töflu 12.9 eru einu ólíku Hamilton-rásirnar í fullkomnu neti með fjóra hnúta. Sex er einnig fjöldi leiða til að raða bókstöfunum þremur b, c og d. (Sérðu hvers vegna?) Fjöldi leiða til að raða þremur bókstöfum er 3! = 3 · 2 · 1 = 6. Á sama $3!=3\cdot 2\cdot 1=6$hátt er fjöldi Hamilton-rása í neti með fimm hnúta jafn fjölda leiða til að raða fjórum bókstöfum, 4! = 4 · 3 · 2 · 1 $4!=4\cdot 3\cdot 2\cdot 1=24$= 24. Almennt finnum við fjölda Hamilton-rása í fullkomnu neti með því að taka tölu sem er einum lægri en fjöldi hnúta og reikna hrópmerkt gildi hennar.

Gerum ráð fyrir að liðsforingi í bandaríska flughernum, staðsettur í Vandenberg-flugherstöðinni, þurfi að aka til þriggja annarra flugherstöðva í Kaliforníu áður en hann snýr aftur til Vandenberg. Hann þarf að heimsækja hverja stöð einu sinni. Hnútarnir í netinu á mynd 12.164 tákna flugherstöðvarnar fjórar: Vandenberg, Edwards, Los Angeles og Beale. Leggirnir eru merktir akstursfjarlægðinni milli sérhvers pars.

Netið á mynd 12.164 nefnist vegið net því hverjum legg hefur verið gefið gildi eða vægi. Vægi geta táknað tíma, fjarlægð, peninga eða aðra stærð sem tengist aðlægu hnútunum sem leggirnir tengja. Heildarvægi göngu, slóðar eða vegar er summa vægis þeirra leggja sem farið er um.