12.8 Hamilton-vegir – Stærðfræði í daglegu lífi (IS) | Námsgögn
1212 Netafræði
12.8 Hamilton-vegir
12.8 Hamilton-vegir
Mynd 12.165. Skólabíll sækir börn eftir skipulagðri leið. (mynd: „Kids at School Bus Stop“ eftir Ty Hatch/Flickr, CC BY 2.0)
Námsmarkmið
Eftir að hafa lokið þessum hluta átt þú að geta:
Lýst og greint Hamilton-vegi.
Metið Hamilton-vegi í hagnýtum verkefnum.
Greint á milli Hamilton-vega og Euler-slóða.
Í 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 CO2 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)
Verkefnið sem Quantum-teymið leysti snýst um netafræði. Hugsum okkur net þar sem hnútarnir eru bílamiðstöðin, skólinn og biðstöðvar á tiltekinni leið. Bílinn þarf að hefja aksturinn í miðstöðinni, heimsækja hverja biðstöð nákvæmlega einu sinni og enda við skólann. Leiðin er sérstakur vegur sem heimsækir hvern hnút nákvæmlega einu sinni. Geturðu giskað á hvað slíkir vegir nefnast?
Hamilton-vegir
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.
Mynd 12.166. Göngur, slóðir og vegir
Mynd 12.167. Vegur eða Hamilton-vegur?
Dæmi 12.38
Hamilton-vegir greindir
Hver eftirfarandi hnútarruna er Hamilton-vegur í neti Q á mynd 12.168?
Mynd 12.168. Net Q
a → d → b → c → e → g → f
c → b → e → h → g → f → d → a
h → e → g → d → b → e → g → f → d → a → b → c
Lausn
Runa 1 er vegur því hún er ganga sem endurtekur hvorki hnúta né leggi, en ekki Hamilton-vegur því hún sleppir hnúti h. Runa 2 er vegur sem heimsækir hvern hnút nákvæmlega einu sinni og er því Hamilton-vegur. Runa 3 er ganga en ekki vegur því hún heimsækir hnútana g, e og b oftar en einu sinni; hún getur því ekki verið Hamilton-vegur. Aðeins runa 2 er Hamilton-vegur.
Hamilton-vegir fundnir
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.169. Kort af sýningarsvæðum fiskasafns
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.
Mynd 12.170. Net fiskasafnsins
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?
Mynd 12.171. Valið milli hnúta L, N og R
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?
Mynd 12.172. Valið milli hnúta B og E
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?
Mynd 12.173. Valið milli hnúta L og K
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?
Mynd 12.174. Valið milli hnúta F, I og P
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.
Mynd 12.175. Valið milli hnúta A og D
Í þ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.
Mynd 12.176. Heildar-Hamilton-vegur frá O til C
Einn Hamilton-vegur sem hefst við O og endar við C er → → S → B → → H → L → N → K → J → P → I → F → D → A → C.
Engin föst skrefaröð finnur Hamilton-veg í öllum tilvikum þar sem slíkur vegur er til. Gagnlegt er þó að hafa endahnútinn í huga og forðast val sem gera ómögulegt að komast síðar að tilteknum hnúti án endurtekningar. Æfum okkur að finna Hamilton-vegi.
Dæmi 12.39
Hamilton-vegur fundinn
Notaðu mynd 12.177 til að finna Hamilton-veg milli hnútanna C og D.
Mynd 12.177. Net G
Lausn
Ef við byrjum í C verður A að koma næst. Þá þarf að velja milli B og F. Ef F verður fyrir valinu þarf að fara til baka til að ná B og því verður að velja B. Eftir B verður að velja F. Eftir F veljum við E því við viljum enda í D. Hamilton-vegur milli C og D er því → B → F → E → D.
Tilvist Hamilton-vegar
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.
Mynd 12.178. Brú milli rauðra og grænna epla
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ð.
Dæmi 12.40
Hamilton-vegur fundinn ef hann er til
Finndu Hamilton-veg frá hnúti s til hnúts v í hverju neti á mynd 12.179 eða segðu til ef enginn er til.
Mynd 12.179. Net A, B, C og D
Lausn
Net A: Leggurinn uw er brú sem tengir samhengisþáttinn {s, t, u, v} við þáttinn {w, x, y, z}. Enginn Hamilton-vegur er frá hnúti s til hnúts v því þeir væru í sama samhengisþætti ef brúin uw væri fjarlægð.
Net B: Engar brýr eru í neti B. Eina aðferðin sem við höfum til að ákvarða hvort Hamilton-vegur sé frá s til v er að prófa alla möguleika. Frá s má heimsækja y eða t. Prófum y fyrst og snúum síðan aftur til að sjá hvað gerist ef t er valið. Eftir y verður að heimsækja z og síðan u, en þá þarf að velja r, t eða v næst eins og sýnt er á mynd 12.180.
Mynd 12.180. Valið milli hnúta r, t og v
Hnútur v kemur ekki til greina því við viljum enda í v. Hnútur t kemur ekki heldur til greina því þá þyrftum við að heimsækja s í annað sinn. Við verðum því að fara næst til r. Eftir r verða x, w og v að koma í þessari röð, en þá höfum við sleppt t eins og mynd 12.181 sýnir.
Mynd 12.181. Hnúti t sleppt
Snúum aftur til upphafsins og veljum t í stað y. Eftir t verðum við að fara til u og þá þarf að velja milli r, v og z eins og sýnt er á mynd 12.182.
Mynd 12.182. Valið milli hnúta v, r og z
Hnútur v kemur ekki til greina því við viljum enda í v. Hnútur z kemur ekki heldur til greina því þá þyrftum við að fara til y og síðan heimsækja s í annað sinn. Við verðum því að fara næst til r. Eftir r verða x, w og v að koma í þessari röð og þar verðum við að stöðva þótt hnútunum y og z hafi verið sleppt, eins og mynd 12.183 sýnir.
Mynd 12.183. Hnútunum y og z sleppt
Við höfum því prófað allar mögulegar leiðir og enginn Hamilton-vegur er milli s og v í neti B.
Net C: Í neti C er Hamilton-vegurinn s → t → u → x → w → v.
Net D: Í neti D er brúin tx. Ef hún væri fjarlægð mynduðust samhengisþættirnir {r, s, t, u, q} og {v, w, x, y, z}. Þar sem s og v væru í ólíkum þáttum gæti Hamilton-vegur verið milli þeirra. Til að komast að því þarf að prófa alla möguleika. Ef byrjað er í s má fara til r og síðan t eða beint til t. Hvort tveggja skapar vandamál eins og sést á mynd 12.184.
Mynd 12.184. Hnútar heimsóttir tvisvar eða sleppt
Ef við heimsækjum alla hnúta samhengisþáttarins {r, s, t, u, q} verðum við að heimsækja t í annað sinn til að fara yfir brúna. Ef t er aðeins heimsóttur einu sinni þarf að sleppa einhverjum hnútum. Því er enginn Hamilton-vegur milli s og v.
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.
Aðstæður
Mynd
Aðstæður 1: Ef leggurinn ab er brú er enginn Hamilton-vegur milli tveggja hnúta sem liggja sömu megin við ab. Þetta sáum við í neti A í dæmi 12.40.
No Hamilton path between any two vertices in the component { a , c , d , f }. No Hamilton path between any two vertices in { b , e , h , g , i }.
Aðstæður 2: Ef leggurinn ab er brú með að minnsta kosti þrjá samhengisþætti hvorum megin getur enginn Hamilton-vegur hafist eða endað í a eða b. Þetta sáum við í neti D í dæmi 12.40.
Enginn Hamilton-vegur hefst eða endar í a eða b.
Aðstæður 3: Ef net er myndað úr tveimur rásum sem tengjast aðeins í einum hnúti p og v er hnútur sem er EKKI aðlægur p, getur enginn Hamilton-vegur hafist eða endað í p eða v. Þetta sáum við í neti B í dæmi 12.40.
Enginn Hamilton-vegur getur hafist eða endað í hnútunum r, v eða u því þeir eru ekki aðlægir p.
Hamilton-vegur eða Euler-slóð?
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.
Dæmi 12.41
Hamilton-vegur og Euler-slóð aðgreind
Notaðu mynd 12.185 til að ákvarða hvort gefna hnútarrunan sé Hamilton-vegur, Euler-slóð, hvort tveggja eða hvorugt.
Mynd 12.185. Net A, F og K
Net A, e → b → a → e → d → c → b
Net F, f → g → j → h → i
Net K, k → l → m → n → o
Lausn
Þar sem runan fer einu sinni um hvern legg en heimsækir suma hnúta oftar en einu sinni er hún aðeins Euler-slóð.
Þar sem runan heimsækir hvern hnút nákvæmlega einu sinni en sleppir nokkrum leggjum er hún aðeins Hamilton-vegur.
Þar sem runan fer nákvæmlega einu sinni um hvern legg og heimsækir hvern hnút nákvæmlega einu sinni er hún bæði Euler-slóð og Hamilton-vegur.
Athugaðu skilning þinn
Fylltu í eyðurnar með
sami og
eða
frábrugðinn
svo fullyrðingarnar verði sannar.
Ólíkt Hamilton-rás er upphafshnútur Hamilton-vegar _________ endahnúturinn.
Ef hnútarruna táknar Hamilton-veg á fjöldi skráðra hnúta að vera _______ fjölda hnúta í öllu netinu.
Aðferðin til að ákvarða hvort net hafi Hamilton-veg er _________ aðferðinni til að ákvarða hvort net hafi Euler-slóð.
Ef net með brú hefur Hamilton-veg á upphafshnúturinn að vera þeim megin við brúna sem er ________ hliðinni þar sem endahnúturinn er.
Vegur milli tveggja hnúta nets sem heimsækir hvern hnút þess nákvæmlega einu sinni nefnist Euler-vegur.
Satt
Ósatt
Sérhvert net sem hefur nákvæmlega tvo hnúta af oddatölustigi hefur Hamilton-veg.
Satt
Ósatt
Ef net er myndað úr tveimur rásum sem tengjast aðeins í einum hnúti p getur enginn Hamilton-vegur hafist eða endað í hnúti sem er aðlægur p.
Satt
Ósatt
Ef leggurinn ab er brú með að minnsta kosti þrjá samhengisþætti hvorum megin er enginn Hamilton-vegur milli hnútsins a og nokkurs hnúts hinum megin við ab.
Satt
Ósatt
Verkefni úr hluta 12.8
Notaðu myndina til að ákvarða hvort hnútarrunan í gefnu neti sé Hamilton-vegur, Euler-slóð, hvort tveggja eða hvorugt.
1.
Net G: f → b → g → e → d → c
2.
Net G: g → b → f → c → d → e
3.
Net G: f → b → g → d → f → c → d → e → g
4.
Net W: v → w → r → s → t → o → q
5.
Net W: s → r → w → v → q → o → t
6.
Net N: h → i → k → n → j → h
7.
Net N: n → i → h → j → m
8.
Net N: m → j → h → i → k → n → i → j → k
Notaðu myndina til að útskýra hvers vegna gefin hnútarruna táknar ekki Hamilton-veg.
9.
Net A: t → s → v → u → x → w → y → z
10.
Net B: w → x → r → u → z → y → s → t → u → v
11.
Net C: s → u → w → v → t
12.
Net D: r → t → q → u → t → x → v → w → x → z → y
Notaðu myndina til að finna veg sem samsvarar lýsingunni eða tilgreindu þær aðstæður á myndinni sem gera hann ómögulegan.
13.
Hamilton-vegur í neti H sem hefst í hnúti c og endar í hnúti e.
14.
Hamilton-vegur í neti Q sem hefst í hnúti n og endar í hnúti h.
15.
Hamilton-vegur í neti H sem hefst í hnúti c og endar í hnúti g.
16.
Hamilton-vegur í neti Q sem hefst í hnúti m og endar í hnúti j.
17.
Hamilton-vegur í neti H sem hefst í hnúti g.
18.
Hamilton-vegur í neti Q sem hefst í hnúti i.
19.
Vegur milli n og j í neti Q sem er EKKI Hamilton-vegur; útskýrðu hvers vegna hann er ekki Hamilton-vegur.
20.
Vegur milli a og c í neti H sem er EKKI Hamilton-vegur; útskýrðu hvers vegna hann er ekki Hamilton-vegur.
21.
Í skák getur riddari færst í hvaða stefnu sem er en þarf að fara tvo reiti, beygja og fara síðan einn reit í viðbót. Myndin sýnir átta mögulegar færslur riddara frá tilteknum reit. Riddaraferð er runa færslna riddara á skákborði af hvaða stærð sem er þar sem riddarinn heimsækir hvern reit nákvæmlega einu sinni. Ef ferðin skilar riddaranum aftur á upphafsreitinn nefnist hún lokuð riddaraferð, annars opin riddaraferð. Ákvarðaðu hvort riddaraferðin á myndinni sé Hamilton-vegur, Euler-slóð eða hvort tveggja í neti allra mögulegra riddarafærslna á átta sinnum átta reita skákborði, þar sem hnútarnir eru reitirnir og leggir sýna mögulega beina færslu milli reita. Rökstyddu svarið.
Rifjaðu upp kanókeppnina á Ólánsbúðunum úr hlutanum um Euler-rásir. Eftirlitsstöð er við hverja af ellefu ám eins og myndin sýnir og keppendur þurfa að heimsækja þær allar.
22.
Teiknaðu net þar sem hnútarnir tákna eftirlitsstöðvar og leggur merkir að hægt sé að fara milli tveggja þeirra án þess að fara fram hjá annarri eftirlitsstöð.
23.
Finndu Hamilton-veg sem hefst í hnúti A og endar í hnúti E.
24.
Hvað táknar þessi Hamilton-vegur í samhengi keppninnar?
Myndin sýnir kort af sýningarsvæðum dýragarðs
A
til
P
Notaðu það til að svara spurningunum.
25.
Teiknaðu net sem táknar leiðirnar um dýragarðinn, þar sem leggirnir tákna göngustíga og hnútarnir sýningarsvæði. Tveir hnútar tengjast ef hægt er að ganga milli svæðanna sem þeir tákna án þess að fara fram hjá öðru sýningarsvæði.
26.
Notaðu netið til að finna leið sem hefst við sýningarsvæði M, endar við sýningarsvæði J og heimsækir hvert svæði nákvæmlega einu sinni.