12.5 Euler-rásir

Áður en hægt er að leita bestu dreifingarleiðarinnar þarf að ganga úr skugga um að einhver leið sé til. Gerum til dæmis ráð fyrir að þú eigir að heimsækja alla flugvellina í netinu á mynd 12.105 með flugi. Gætirðu gert það með því að nota aðeins beinu flugleiðirnar sem netið sýnir? Með öðrum orðum, tengjast allir flugvellirnir með vegum eða eru einhverjir þeirra ótengdir hinum?

Á mynd 12.105 má sjá að TPA er aðlægur PBI, FLL, MIA og EYW. Einnig liggur vegur milli TPA og MCO um FLL. Vegur liggur því milli sérhvers hnútapars. Hægt er að ferðast til allra flugvallanna með aðeins beinu flugleiðunum og án þess að heimsækja aðra flugvelli. Netið er með öðrum orðum tengt því vegur tengir hvert hnútapar þess. Athugaðu að ef einn hnútur tengist öllum öðrum hnútum nets þá tengjast allir hnútarnir innbyrðis. Ein leið til að ákvarða hvort net sé tengt er því að velja einn hnút og kanna hvort vegur liggi frá honum til hvers hinna. Ef svo er er netið tengt. Annars er það ótengt, sem merkir að að minnsta kosti eitt hnútapar tengist ekki með vegi. Skoðum net X á mynd 12.106 nánar. Beinum athyglinni að hnúti a. Vegur liggur milli a og b en enginn vegur milli a og c. Net X er því ótengt.

Þegar unnið er með sléttunet má einnig ákvarða hvort net sé tengt með því að leysa það úr flækju. Ef það er teiknað þannig að engir leggir skarist, eins og gert var við net X á mynd 12.106, sést auðveldar að netið er ótengt.

Útgáfur 2 og 3 af neti X á mynd 12.107 hafa sama fjölda hnúta, leggja, sömu stig hnúta og sömu pör aðlægra hnúta og útgáfa 1. Hver útgáfa varðveitir því gerð upphaflega netsins. Þar sem leggir skarast ekki í útgáfum 2 og 3 af neti X er auðveldara að greina hnútapör sem enginn vegur tengir og augljósara að net X er ótengt. Þar eru í raun tvö algjörlega aðskilin, ótengd hlutanet, annað með hnútana {a, b, e} og hitt með hnútana {c, d, f}

Þessi hnútamengi ásamt öllum leggjum þeirra nefnast samhengisþættir nets X. Samhengisþáttur nets er hlutanet þar sem vegur liggur milli sérhvers hnútapars hlutanetsins en enginn leggur liggur frá hnúti þess til hnúts utan hlutanetsins.

Skoðum nú net Y á mynd 12.106. Líkt og í neti X liggur vegur milli hnútanna a og b og einnig milli hnútanna a og e en net Y er ólíkt neti X vegna hnútsins g. Ekki aðeins liggur vegur milli hnútanna a og g heldur brúar hnúturinn g bilið milli a og c með veginum a → b → g → c. Á sama hátt liggur vegur milli hnútanna a og d og milli hnútanna a og f: a → b → g → d, a → b → g → d → f. Þar sem vegur liggur milli hnútsins a og hvers annars hnúts er net Y tengt. Þetta sést enn skýrar þegar net Y er leyst úr flækju eins og á mynd 12.108. Jafnvel þegar Y er teiknað án skörunar leggja er ekki hægt að skipta því í tvo aðskilda, ótengda hluta. Net Y hefur með öðrum orðum aðeins einn samhengisþátt með hnútana {a, b, c, d, e, f}.

Með hugmyndinni um samhengisþætti má skilgreina tengd og ótengd net á annan hátt. Net er tengt ef það hefur aðeins einn samhengisþátt en ótengt ef samhengisþættirnir eru fleiri en einn. Þessar skilgreiningar eru jafngildar fyrri skilgreiningunum. Því má staðfesta hvort net sé tengt eða ótengt annaðhvort með því að kanna hvort vegur liggi milli hvers hnúts og allra hinna eða með því að telja samhengisþættina. Net er tengt ef það hefur aðeins einn samhengisþátt.

Vatnaleiðir skipta borginni Königsberg, nú Kalíníngrad í Rússlandi, í nokkra hluta. Á 18. öld voru sjö brýr yfir vatnaleiðirnar. Kort af brúnum er sýnt á mynd 12.110. Spurningin um hvort finna mætti leið sem færi nákvæmlega einu sinni yfir hverja brú og skilaði manni aftur á upphafsstaðinn nefndist brúarvandamál Königsberg. Árið 1735 leysti einn áhrifamesti stærðfræðingur sögunnar, Leonhard Euler, vandamálið með fræðigrein sem hann skapaði sjálfur: netafræði.

Euler teiknaði fjölnet þar sem hver hnútur táknaði landsvæði og hver leggur brú sem tengdi þau, eins og sýnt er á mynd 12.111. Mundu úr Leiðum um net að rás er slóð og endurtekur því engan legg, og að hún er lokuð og hefst því og endar í sama hnúti. Euler benti á að brúarvandamál Königsberg jafngilti eftirfarandi netafræðispurningu: Er hægt að finna rás sem fer um hvern legg? Rásir, eða lokaðar slóðir, sem fara nákvæmlega einu sinni um hvern legg nets hafa síðan verið nefndar Euler-rásir til heiðurs Leonhard Euler.

Euler sannaði að til að Euler-rás sé til þurfi stig allra hnúta nets að vera slétt. Hann sannaði einnig að sérhvert tengt net með þann eiginleika hafi Euler-rás. Að segja að tengt net sé Euler-net jafngildir því að segja að allir hnútar þess hafi slétt stig. Þetta nefnist setningin um Euler-rásir.

Til að skilja hvers vegna setningin um Euler-rásir er sönn skaltu íhuga hnút af stigi 3 í einhverju neti, eins og sýnt er á mynd 12.112.

Ímyndaðu þér fyrst að hnúturinn af stigi 3 á mynd 12.112 sé ekki upphafshnúturinn. Fara þarf um hvern legg einhvern tíma. Þegar farið er um fyrsta legginn er stefnan að hnútnum og um annan legginn frá honum. Síðar þarf að fara um þriðja legginn inn að hnútnum. Þá kemur upp vandamál því eina leiðin aftur að upphafshnútnum er að fara öðru sinni um einn legganna þriggja. Hnúturinn getur því ekki verið hluti Euler-rásar.

Ímyndaðu þér næst að hnúturinn af stigi 3 á mynd 12.112 sé upphafshnúturinn. Fyrst er farið um legg frá hnútnum. Síðar er farið um annan legg inn að hnútnum og þann þriðja aftur frá honum. Upphafshnútur rásar þarf einnig að vera endahnúturinn en eina leiðin til baka er nú að fara öðru sinni um einn legganna. Hnúturinn getur því heldur ekki verið hluti Euler-rásar.

Af sömu ástæðu og hnútur af stigi 3 getur aldrei verið hluti Euler-rásar getur enginn hnútur af oddatölustigi verið það. Við getum notað þessa staðreynd og netið á mynd 12.113 til að leysa brúarvandamál Königsberg. Þar sem stig hnútanna eru ekki slétt er netið ekki Euler-net og hefur enga Euler-rás. Því er ómögulegt að ferðast um Königsberg, fara nákvæmlega einu sinni yfir hverja brú og snúa aftur á upphafsstaðinn.

Í sumarbúðunum Camp Woebegone ferðast þátttakendur eftir vatnaleiðum í kanóum. Halda á kanókeppni sem hluta af íþróttakeppni búðanna. Eftirlitsstöð hefur verið komið fyrir á hverjum ellefu lækjum svæðisins. Hvert lið þarf að fara um hvern læk, fara um eftirlitsstöðvarnar í hvaða röð sem er og snúa aftur að rásmarkinu eins og sýnt er á mynd 12.114.

Þar sem liðin vilja fara eins hratt og hægt er leita þau stystu leiðar um brautina sem heimsækir hverja eftirlitsstöð og snýr aftur að rásmarkinu. Ef hægt er vilja þau einnig forðast að fara sömu leið til baka. Sýnum brautina sem fjölnet þar sem hnútarnir tákna beygjur og leggirnir eftirlitsstöðvar, eins og á mynd 12.115.

Liðin vilja finna lokaða göngu sem endurtekur sem fæsta leggi en fer samt um þá alla. Ef enginn leggur er endurtekinn hafa þau fundið lokaða slóð, það er rás. Rásin þarf að ná yfir alla leggi og væri því Euler-rás. Verkefnið að finna stystu rás sem fer um hvern legg tengds nets nefnist oft kínverska póstburðarmannsvandamálið. Heitið var myndað til heiðurs kínverska stærðfræðingnum Kwan Mei-Ko, sem rannsakaði vandamálið fyrst árið 1960.

Ef net hefur Euler-rás er hún alltaf besta lausnin á kínverska póstburðarmannsvandamálinu. Ákvarðum hvort fjölnet brautarinnar hafi Euler-rás með því að skoða stig hnútanna á mynd 12.116. Þar sem stig allra hnútanna eru slétt og netið er tengt er það Euler-net. Lið getur því lokið kanóbrautinni, farið nákvæmlega einu sinni um hverja eftirlitsstöð og snúið aftur að rásmarkinu.

Finnum Euler-rás á korti kanókeppninnar í Camp Woebegone. Á mynd 12.119 hafa leggir fjölnetsins verið merktir svo hægt sé að nefna rásirnar. Í fjölneti þarf að nefna rásir með bæði leggjum og hnútum því fleiri en einn leggur getur tengt aðlæga hnúta.

Við byrjum í hnúti 1 því hann táknar rásmarkið í þessu verkefni. Almennt má byrja í hvaða hnúti sem er. Finndu einhverja rás sem hefst og endar í hnúti 1. Mundu að rás er slóð og fer því ekki oftar en einu sinni um neinn legg. Mynd 12.120 sýnir eina mögulega fyrstu rás: 1 → A → 2 → B → 3 → C → 4 → G → 5 → J → 1.

Úr leggjunum sem eftir eru má mynda tvær rásir í viðbót sem hvor hefst í hnúti fyrstu rásarinnar. Frá hnúti 3 má nota 3 → H → 5 → I → 1 → K → 3 og frá hnúti 2 má nota 2 → D → 6 → E → 7 → F → 2, eins og sýnt er á mynd 12.121.

Að lokum má nefna rásina með hnútunum 1 → 2 → 6 → 7 → 2 → 3 → 5 → 1 → 3 → 4 → 5 → 1 eða leggjunum $\mathrm{A}\to \mathrm{D}$ → $\mathrm{E}\to \mathrm{F}$ → $\mathrm{B}\to \mathrm{H}$ → I → K → C → G → J.

Skref við að finna Euler-rás í Euler-neti

Skref 1 – Finndu rás sem hefst og endar í einhverjum hnúti netsins. Ef rásin fer um alla leggi netsins er hún Euler-rás. Annars skaltu halda áfram í skref 2.

Skref 2 – Byrjaðu í hnúti rásar sem þegar hefur fundist og finndu rás sem inniheldur aðeins leggi sem ekki hefur áður verið farið um. Ef ein rásanna sem fundist hafa fer um hvern legg skaltu halda áfram í skref 3. Annars skaltu endurtaka skref 2.

Skref 3 – Nú hafa fundist rásir sem ná yfir alla leggi netsins. Sameinaðu þær í Euler-rás með því að setja hverja rás inn í aðra rás sem hefur sameiginlegan hnút, þar til ein löng rás fæst.

Kínverska póstburðarmannsvandamálið á ekki aðeins við um Euler-net. Mundu eftir póstburðarmanninum sem þurfti að bera póst í hverja húsalengd við hverja götu hverfis. Við notuðum kortið á mynd 12.126 til að búa til netið á mynd 12.127.

Þar sem net hverfisins hefur hnúta af oddatölustigi er engin Euler-rás til. Engin leið fer því um hverja húsalengd við hverja götu án þess að endurtaka einhverja þeirra. Hvað á póstburðarmaðurinn þá að gera? Hann þarf að endurtaka sem fæstar húsalengdir. Aðferðin sem við notum til að finna lokaða göngu sem endurtekur sem fæsta leggi nefnist Euler-væðing. Þá eru afrit leggja sett í netið til að gera stig hnútanna slétt svo netið fái Euler-rás.

Á mynd 12.128 eru átta hnútar af oddatölustigi í neti hverfisins afmarkaðir með grænu. Við höfum bætt við afritum leggja milli hnútapara. Við það verða stig hnútanna slétt og fjölnetið sem fæst hefur Euler-rás. Með öðrum orðum höfum við Euler-vætt netið.

Afrit leggjanna í Euler-vædda netinu samsvara húsalengdum sem póstburðarmaðurinn þarf að fara tvisvar um. Með því að halda þeim í lágmarki tryggjum við stystu mögulegu leið. Erfitt getur verið að finna minnsta fjölda afrita sem þarf til að Euler-væða net, en hann getur aldrei verið minni en helmingur fjölda hnúta af oddatölustigi. Í netinu á mynd 12.128 hefur tekist að laga hnútana átta af oddatölustigi með aðeins fjórum afritum leggja. Þar sem fjórir eru helmingur af átta er ekki hægt að gera betur.