12.4 Leiðir um net

Gerum ráð fyrir að þú viljir leysa völundarhúsið á mynd 12.69. Þú vilt komast frá byrjun að enda.

Þú mátt nálgast verkefnið á hvaða hátt sem er. Eina reglan er að ekki má klifra yfir vegg. Í samhengi netafræði skulum við ímynda okkur hnút við hver gatnamót og hverja beygju. Leggirnir sem tengja hnútana verða að liggja innan veggjanna. Netið í völundarhúsinu liti þá út eins og á mynd 12.70.

Ein leið til að leysa völundarhús er einfaldlega að byrja að ganga. Það er ekki hagkvæmasta leiðin. Þú gætir farið tvisvar um sömu gatnamót eða þurft að snúa við. Það er allt í lagi; við erum aðeins á göngu. Gangan gæti líkst svörtu röð hnútanna og leggjanna á mynd 12.71.

Tilgreina má göngu með því að nefna hnúta hennar í röð, eða leggi hennar í röð ef þeir eru merktir. Tökum netið úr samhengi völundarhússins, gefum hverjum hnút heiti og sýnum stefnu hvers leggs göngunnar eins og á mynd 12.72.

Heiti þessarar göngu frá p til r er p → q → o → n → i → j → c → d → c → j → k → s → r. Þegar farið var um tiltekinn legg í báðar áttir voru örvar í báðar áttir og endurtaka þurfti bókstafi hnúta sem heimsóttir voru oftar en einu sinni í heiti göngunnar.

Auðkenndu leggirnir í neti Y á mynd 12.73 tákna göngu milli f og b. Auðkenndu leggirnir í neti X tákna ekki göngu milli f og b því þar er beygt á stað sem er ekki hnútur. Það samsvarar því að klifra yfir vegg í völundarhúsi. Einnig má segja að b → d → f sé ekki ganga því enginn leggur tengir b og d.

Sjá má tengslin á mynd 12.78.

Æfum okkur að greina göngur, slóðir og vegi með netunum á mynd 12.79.

Sjá má tengslin á mynd 12.84.

Sömu rás má nefna með því að velja hvaða hnút hennar sem er sem upphafspunkt. Rásina d → f → b → c → d má til dæmis einnig nefna á eftirfarandi vegu.

a → b → c → d → a er sama rás og

Æfum okkur að vinna með lokaðar göngur, rásir (lokaðar slóðir) og stefndar rásir (lokaða vegi). Hnútar netsins á mynd 12.85 eru helstu flugvellir í Mið- og Suður-Flórída. Leggirnir tákna beint flug á milli þeirra.

Hingað til höfum við skoðað hvernig fara má um net með því að færast frá einum hnúti til annars í runu án þess að sleppa hnútum. Í sumum hagnýtum verkefnum viljum við hins vegar geta sleppt hnútum. Manstu eftir íþróttakeppninni í sumarbúðunum Camp Woebegone úr Samanburði neta? Þú skipulagðir keppni í fjórum greinum og þátttakendur skráðu sig í greinarnar. Þú teiknaðir net til að sjá betur hvaða greinar ættu þátttakendur sameiginlega. Hnútar nets E á mynd 12.87 tákna greinarnar og aðlægir hnútar sýna að einhverjir þátttakendur keppa í báðum greinum.

Í þessu tilviki viljum við EKKI að greinar sem tveir aðlægir hnútar tákna fari fram á sama tíma því þá gætu þeir þátttakendur sem vilja taka þátt í báðum ekki gert það. Við getum notað netið á mynd 12.87 til að telja hve marga tímaramma þarf til að engir árekstrar verði. Úthlutum hverjum tímaramma sérstökum lit. Greinar klukkan 13 gætu verið rauðar, klukkan 14 fjólubláar, klukkan 15 bláar og klukkan 16 grænar. Síðan gefum við hverju pari aðlægra hnúta ólíka liti svo greinarnar sem þeir tákna lendi ekki á sama tíma. Mynd 12.88 sýnir nokkrar leiðir til að gera þetta án þess að tveir aðlægir hnútar fái sama lit.

Netin á mynd 12.88 þar sem hnútar eru litaðir þannig að engir tveir aðlægir hnútar hafa sama lit nefnast hnútalitanir. Athugaðu að net 3 notar fæsta liti og sýnir því hvernig komast má af með fæsta tímaramma. Greinarnar a og d, merktar rauðar, mega fara fram samtímis því hnútarnir eru ekki aðlægir og enginn árekstur verður. Sama gildir um greinarnar b og c, merktar fjólubláar. Græna og bláa tímaramma þyrfti því alls ekki.

Hnútalitun sem $n$notar n liti $\mathit{n}$nefnist n-litun. Minnsti fjöldi lita sem þarf til að lita tiltekið net nefnist litunartala þess.

Hnútalitanir nýtast í mörgum verkefnum, til dæmis við tímasetningar í sumarbúðunum Camp Woebegone. Skoðum þær nánar. Mynd 12.89 sýnir tvær litanir sama nets. Litun A er fjórlitun því hún notar fjóra liti: rauðan (R), grænan (G), bláan (B) og fjólubláan (P). Litun B er þrílitun því hún notar þrjá liti. Litirnir skipta hnútum netsins í hópa. Eina reglan er að aðlægir hnútar hafi ólíka liti og séu því í ólíkum hópum.

Í ljós kemur að þrílitun er besta mögulega litun netsins á mynd 12.89. Sama hve mörg mynstur eru prófuð með aðeins tveimur litum finnst ekkert þar sem aðlægir hnútar hafa alltaf ólíka liti. Litunartala netsins er því þrír. Yfirleitt þarf tölvu til að finna litunartölu stórra neta. Engin formúla gefur litunartölu nets en staðreyndirnar í töflu 12.5 koma að gagni.

Skoðum hvernig þessar staðreyndir hjálpa okkur að lita netið á mynd 12.90.

Við vitum að lita má netið með þremur eða fjórum litum. Yfirleitt er best að byrja á því að lita hnútinn með hæsta stigið eins og sýnt er á mynd 12.91. Hér var rauður (R) notaður en liturinn sjálfur skiptir ekki máli.

Við viljum lita sem flesta hnúta í sama lit. Því skoðum við alla hnúta sem eru ekki aðlægir rauða hnútnum og litum þá rauða, í lækkandi röð eftir stigi. Einu hnútarnir sem eru ekki aðlægir rauða hnútnum eru báðir af stigi 2. Veldu annan þeirra og litaðu hann rauðan eins og sýnt er á mynd 12.92.

Nú er aðeins einn hnútur eftir sem er ekki aðlægur rauðum hnúti; litaðu hann rauðan. Hæsta stig ólituðu hnútanna er fjórir; litaðu því einn hnút af stigi 4 í öðrum lit. Skrefin tvö eru sýnd á mynd 12.93.

Endurtaktu sama ferli. Þrír ólitaðir hnútar eru ekki aðlægir bláum hnúti. Litaðu eins marga þeirra bláa og hægt er og gefðu hnútum af hærra stigi forgang eins og sýnt er á mynd 12.94.

Allir ólituðu hnútarnir eru aðlægir bláum hnúti. Því er kominn tími til að endurtaka ferlið með öðrum lit eins og sýnt er á mynd 12.95.

Allir hnútarnir eru nú litaðir með þrílitun og því vitum við að litunartalan er ekki hærri en þrír. Við vissum einnig að hún væri að minnsta kosti þrír vegna þríhyrnings í netinu. Hún er því nákvæmlega þrír.

Gerum ráð fyrir að hnútar netsins á mynd 12.96 tákni níu greinar í íþróttakeppni Camp Woebegone og að leggir tengi þær greinar sem eiga þátttakendur sameiginlega en óaðlægir hnútar ekki.

Í Grunnatriðum neta sáum við hvernig tákna má kort með netum. Mynd 12.99 úr dæmi 12.4 sýnir kort af miðvesturríkjum Bandaríkjanna.

Mynd 12.100 sýnir hvernig tengja má kortið við net þar sem hver hnútur táknar ríki og hver leggur tvö ríki með sameiginleg landamæri. Mynd 12.101 sýnir endanlega netið.