12.8 Hamilton-vegir

Í Bandaríkjunum flytja skólabílar 25 milljónir barna milli skóla og heimilis á hverjum degi. Heildarakstursvegalengdin er um 6 milljarðar kílómetra á ári. Árið 2016 voru 120 milljónir Bandaríkjadala áætlaðar í rekstur skólabíla í Boston í Massachusetts. Árið 2017 efndi borgin til samkeppni um leiðir til að lækka kostnað. Quantum-teymið við MIT Operations Research Center kom til hjálpar og notaði tölvureiknirit til að finna hagkvæmustu leiðirnar. Það sparaði Boston fimm milljónir dala á ári og minnkaði jafnvel daglega losun CO₂ um 9.000 kílógrömm. (Sean Fleming, „Bandarísk borg fól reikniriti að stjórna skólabílaleiðum og sparaði fimm milljónir dala“, World Economic Forum)

Rétt eins og rásir sem heimsækja hvern hnút nets nákvæmlega einu sinni nefnast Hamilton-rásir, nefnast vegir sem heimsækja hvern hnút nets nákvæmlega einu sinni Hamilton-vegir. Við skoðun þeirra getur verið gagnlegt að rifja upp tengsl gangna, slóða og vega á mynd 12.166. Við vitum að vegur er ganga sem endurtekur hvorki hnúta né leggi. Hamilton-vegur heimsækir því alla hnúta án þess að endurtaka hnúta eða leggi. Mynd 12.167 sýnir annars vegar veg frá hnúti A til hnúts E og hins vegar Hamilton-veg milli sömu hnúta.

Gerum ráð fyrir að þú heimsækir fiskasafn með vinum. Kort af safninu er á mynd 12.169. Bókstafirnir tákna sýningarsvæðin.

Mynd 12.170 sýnir net fiskasafnsins þar sem hver hnútur táknar sýningarsvæði og hver leggur leið milli tveggja sýningarsvæða sem fer ekki fram hjá öðru svæði.

Skoðum hvort hægt sé að skipuleggja ferð sem heimsækir hvert sýningarsvæði nákvæmlega einu sinni, hefst við O og endar við C. Gerum ráð fyrir að eftir O ætlum við að heimsækja Q og síðan M. Eigum við næst að fara til N, L eða R? Skoðaðu mynd 12.171. Ef R verður ekki fyrir valinu næst skapast vandamál síðar. Sérðu hvert það er?

Ef L eða N verður fyrir valinu er síðar aðeins hægt að komast til R frá S. Þá getum við ekki haldið áfram án þess að endurtaka hnút. Við veljum því R næst og þá er S eini kosturinn. Eftir S þurfum við að velja aftur. Eins og mynd 12.172 sýnir stendur valið milli B og E. Hvort er betra ef markmiðið er að enda við C?

Ef þú valdir B svaraðirðu rétt. Annars gætum við ekki heimsótt B síðar. Eftir B er E eini kosturinn. Þá má velja D eða G og hvort tveggja gengur. Veljum G eins og á mynd 12.173. Eftir G verður að heimsækja H, en eigum við síðan að velja K eða L?

Ef þú valdir L svaraðirðu rétt. Annars yrði ómögulegt að heimsækja N án þess að endurtaka hnút. Næst koma því L, N og K. Við J þarf að velja aftur eins og mynd 12.174 sýnir. Eigum við að velja F, I eða P næst?

Ef þú valdir P svaraðirðu rétt. Ef annar hvor hinna hnútanna yrði valinn væri síðar ekki hægt að heimsækja P án þess að fara tvisvar um annan hnút. Eftir P verður I að koma næst og síðan F. Þá þarf að velja milli A og D eins og sýnt er á mynd 12.175.

Í þessu tilviki verðum við að fara til D og síðan A til að geta heimsótt C án bakslags. Heildar-Hamilton-vegurinn er sýndur á mynd 12.176.

Einn Hamilton-vegur sem hefst við O og endar við C er $\mathrm{O}\to \mathrm{Q}$ → $\mathrm{M}\to \mathrm{R}$ → S → B → $\mathrm{E}\to \mathrm{G}$ → H → L → N → K → J → P → I → F → D → A → C.

Enginn Hamilton-vegur er milli hnútanna A og E í neti G á mynd 12.177. Til að skilja hvers vegna skulum við ímynda okkur rautt eplatré öðrum megin við brú og grænt eplatré hinum megin. Gerum síðan ráð fyrir að þú eigir að taka upp öll fallin epli undir báðum trjám án þess að fara oftar en einu sinni yfir brúna og að fyrsta og síðasta eplið séu bæði rauð. Það er ómögulegt. Til þess þyrfti annaðhvort að skilja grænu eplin eftir eða fara tvisvar yfir brúna.

Skoðum hvernig þetta tengist því að finna Hamilton-veg milli A og E í neti G. Leggurinn AC er brú því ef hann væri fjarlægður yrði netið ótengt með samhengisþættina {C} og {A, B, D, E, F}. Við getum hugsað okkur hnútana A, B, D, E og F sem rauðu eplin, hnútinn C sem græna eplið og legginn AC sem brúna milli þeirra, eins og á mynd 12.178.

Til að mynda Hamilton-veg þarf að heimsækja hvern hnút, rétt eins og heimsækja þarf hvert epli til að taka þau öll upp. A og E eru bæði rauð epli og vegur frá A til E myndi því bæði hefjast og enda við rautt epli. Ekki mætti fara tvisvar yfir brúna því þá væri A heimsótt tvisvar, sem er óheimilt á Hamilton-vegi. Því er jafn ómögulegt að finna Hamilton-veg frá A til E og að taka upp öll eplin án þess að fara oftar en einu sinni yfir brúna. Af sömu ástæðu getur Hamilton-vegur í neti með brú aldrei hafist og endað sömu megin við brúna, það er í hnútum sem væru í sama samhengisþætti ef brúin væri fjarlægð.

Engin stutt aðferð virkar í öllum tilvikum til að ákvarða hvort Hamilton-vegur sé milli tveggja hnúta nets. Nokkrar algengar aðstæður geta þó fljótt sýnt að enginn Hamilton-vegur er til. Sumar þeirra eru í töflu 12.10.

Við lærðum að Euler-slóð fer nákvæmlega einu sinni um hvern legg en Hamilton-vegur heimsækir hvern hnút nákvæmlega einu sinni. Æfum okkur að greina þar á milli.