12.6 Euler-slóðir

Rétt eins og Euler ákvarðaði að aðeins net með hnúta af sléttu stigi hefðu Euler-rásir áttaði hann sig á að einu hnútarnir af oddatölustigi í neti með Euler-slóð væru upphafs- og endahnútarnir. Net H á mynd 12.132 hefur til dæmis nákvæmlega tvo hnúta af oddatölustigi, g og e. Athugaðu að Euler-slóðin í 3. lið dæmis 12.29 hófst í g og endaði í e.

Þetta samræmist því sem við lærðum um hnúta af oddatölustigi við athugun Euler-rása. Við sáum að slíkur hnútur gæti ekki verið í Euler-rás, eins og mynd 12.133 sýnir. Ef hann væri upphafshnútur myndum við einhvern tíma fara frá honum án þess að geta snúið aftur án endurtekningar leggs. Ef hann væri ekki upphafshnútur myndum við einhvern tíma koma aftur að honum án þess að geta farið frá honum án endurtekningar leggs. Upphafs- og endahnútur Euler-slóðar eru ekki sami hnúturinn. Frá upphafshnútnum viljum við fara án þess að snúa aftur og að endahnútnum viljum við koma án þess að fara aftur frá honum. Þessir tveir hnútar verða að hafa oddatölustig en hinir mega það ekki.

Notum setninguna um Euler-slóðir til að leysa þraut sem þú getur komið vinum þínum á óvart með. Hún nefnist fimm herbergja þrautin. Gerum ráð fyrir að þú sért í húsi með fimm herbergjum og svæði utan hússins. Dyr eru á öllum sameiginlegum veggjum tveggja herbergja og milli hvers herbergis og útisvæðisins eins og sýnt er á mynd 12.134. Gætirðu fundið leið um húsið sem fer nákvæmlega einu sinni um hverjar dyr?

Táknum þrautina með neti þar sem hnútarnir eru herbergin eða útisvæðið og leggur táknar dyr milli tveggja rýma, eins og sýnt er á mynd 12.135.

Þar sem fleiri en tveir hnútar hafa oddatölustig, eins og sýnt er á mynd 12.136, hefur net fimm herbergja þrautarinnar enga Euler-slóð. Nú geturðu komið vinum þínum á óvart.

Nú vitum við hvaða net hafa Euler-slóðir og getum skoðað aðferð til að finna þær. Aðferðin byggist á því að greina brýr í neti. Brú er leggur sem fjölgar samhengisþáttum nets þegar hann er fjarlægður. Brýr nefnast einnig skurðleggir. Mynd 12.137 sýnir nokkur dæmi. Athugaðu að leggur sem er ekki hluti rásar er alltaf brú en leggur í rás er aldrei brú.

Leggirnir bf, cg og dg eru brýr

Netið á mynd 12.137 er tengt og hefur því nákvæmlega einn samhengisþátt. Í hvert sinn sem ein brú er fjarlægð fjölgar samhengisþáttunum um einn, eins og sýnt er á mynd 12.138. Ef allar þrjár eru fjarlægðar hefur netið sem fæst fjóra samhengisþætti.

Í félagsfræði eru brýr mikilvægur þáttur í greiningu félagsneta. Félagsfræðingar rannsaka tvenns konar brýr: staðbundnar brýr og venjulegar brýr. Venjuleg brú er skilgreind eins í félagsfræði og netafræði en er sjaldgæf í stórum félagsnetum því ólíklegt er að hópur einstaklinga hafi aðeins ein tengsl við allt hitt netið. Staðbundnar brýr eru hins vegar algengari. Staðbundin brú er vinátta tveggja einstaklinga sem eiga enga aðra vini sameiginlega. Ef sambandið rofnar er enginn einn einstaklingur sem getur miðlað upplýsingum milli þeirra. Í netafræði er staðbundin brú leggur milli tveggja hnúta sem, þegar hann er fjarlægður, lengir stysta veg milli hnútanna í meira en tvo leggi. Á mynd 12.139 hefur staðbundna brúin milli b og e verið fjarlægð. Stysti vegurinn milli b og e verður þá b → i → j → k → e, sem er fjórir leggir. Ef leggurinn ab væri hins vegar fjarlægður væru enn til tveggja leggja vegir milli a og b, til dæmis a → i → b.

Mikilvægi staðbundinnar brúar í félagsfræði felst í því að hún er stysta samskiptaleið tveggja hópa. Ef brúin er fjarlægð verður erfiðara að miðla upplýsingum milli hópanna. Segjum að hnútur b sé Brielle og hnútur e Ella. Þá eru minni líkur á að Brielle frétti til dæmis af atvinnutækifærum sem Ella veit um. Það hefur líklega áhrif bæði á Brielle og vini hennar.

Skref 1: Byrjaðu í öðrum hnútnum af oddatölustigi.

Skref 2: Fjarlægðu legg frá hnútnum til einhvers aðlægs hnúts sem er EKKI brú, nema enginn annar kostur sé í boði, og skráðu legginn sem var fjarlægður. Endurtaktu skrefið þar til allir leggir hafa verið fjarlægðir.

Skref 3: Skrifaðu Euler-slóðina með hnútunum og leggjunum í þeirri röð sem fundin var. Ef leggirnir ab, bc, cd, de og ef voru til dæmis fjarlægðir í þessari röð er Euler-slóðin a → b → c → d → e → f.

Mynd 12.142 sýnir skref reiknirits Fleurys við að finna Euler-slóð í neti.

Euler-slóðin sem fannst á mynd 12.142 er t → v → w → u → t → w → y → x → v.

Skref 1: Byrjaðu í hvaða hnúti sem er.

Skref 2: Fjarlægðu legg frá hnútnum til einhvers aðlægs hnúts sem er EKKI brú, nema enginn annar kostur sé í boði, og skráðu legginn sem var fjarlægður. Endurtaktu skrefið þar til allir leggir hafa verið fjarlægðir.

Skref 3: Skrifaðu Euler-rásina með hnútunum og leggjunum í þeirri röð sem fundin var. Ef leggirnir ab, bc, cd, de og ea voru til dæmis fjarlægðir í þessari röð er Euler-rásin a → b → c → d → e → a.