12.4 Leiðir um net
12.4 Leiðir um net
Námsmarkmið
Eftir að hafa lokið þessum hluta átt þú að geta:
Nú þekkjum við grunnhluta neta og getum greint eitt net frá öðru. Þá er kominn tími til að nýta netin. Mörg hagnýt verkefni í netafræði snúast um að rata um net líkt og um völundarhús. Ímyndaðu þér að þú sért við inngang völundarhúss og viljir komast frá einum stað til annars á sem hagkvæmastan hátt. Kannski eru fjársjóðir á leiðinni sem gera það þess virði að víkja af stystu leiðinni eða kannski þarftu einfaldlega að komast hratt til enda. Hvort sem er viltu forðast rangar beygjur sem valda óþarfa bakslagi. Sem betur fer getur netafræðin hjálpað.
Göngur
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.
Slík röð aðlægra hnúta og leggja nefnist einnig ganga (eða stefnd ganga) í netafræði.
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.
Dæmi 12.19
Ganga um hús nefnd
Mynd 12.74 sýnir grunnmynd húss. Notaðu hana til að svara hverri spurningu.
- Teiknaðu net sem táknar grunnmyndina þannig að hver hnútur tákni herbergi eða gang og leggir tákni dyr milli rýma.
- Tilgreindu göngu um húsið sem hefst í stofunni, endar í bílskúrnum og fer að minnsta kosti einu sinni um hvert herbergi og ganginn.
Lausn
Skref 1: Við þurfum hnút fyrir hvert herbergi og hentugt er að merkja þá eftir heitum herbergjanna. Sjáðu aðstæðurnar fyrir þér eins og á mynd 12.75. Ekki þarf að skrifa þetta skref á blaðið.
Mynd 12.75 Hnútum úthlutað til herbergja. Skref 2: Teiknaðu net sem táknar aðstæðurnar. Byrjaðu á hnútunum og tengdu síðan hnúta rýma sem dyr liggja á milli, eins og á mynd
12.76. Mynd 12.76 Net grunnmyndarinnar Skref 1: Teiknaðu göngu sem hefst í hnúti L, sem táknar stofuna, og endar í hnúti G, sem táknar bílskúrinn, þannig að farið sé að minnsta kosti einu sinni um hvert rými. Margar leiðir eru færar. Gott getur verið að númera leggina til að halda utan um röð þeirra. Eitt dæmi er sýnt á mynd 12.77. Mynd 12.77 Gangan frá L til G teiknuð. Skref
2: Nefndu gönguna með því að telja hnútana upp í heimsóknarröð: → → → →
M → H → G
Vegir og slóðir
Ganga er einfaldasta leiðin um net því eina skilyrðið er að halda sig á netinu. Þegar takmarkanir gilda um hvaða hnúta eða leggi má heimsækja fær gangan annað heiti. Ganga þar sem sami leggur er aldrei farinn tvisvar nefnist slóð (eða stefnd slóð). Ganga þar sem sami hnútur er aldrei heimsóttur tvisvar nefnist vegur (eða stefndur vegur).
Göngur, slóðir og vegir tengjast innbyrðis.
Sjá má tengslin á mynd 12.78.
Æfum okkur að greina göngur, slóðir og vegi með netunum á mynd 12.79.
Dæmi 12.20
Lausn
- Athugaðu fyrst hvort hnútarrunan sé ganga með því að ganga úr skugga um að hnútarnir séu samliggjandi í rununni. Eins og sjá má á mynd 12.80 er enginn leggur milli hnúts c
og hnúts d. Mynd 12.80. Runan er því ekki ganga. Ef hún er ekki ganga getur hún hvorki verið vegur né slóð og er því ekkert af þessu.
- Athugaðu fyrst hvort runan sé ganga. Eins og sjá má á mynd 12.81 eru hnútarnir samliggjandi í
rununni. Mynd 12.81. Runan er því ganga. Þar sem hnúturinn b er heimsóttur tvisvar er gangan ekki vegur. Þar sem leggurinn bd er farinn tvisvar er gangan ekki slóð. Runan er því aðeins ganga.
- Athugaðu fyrst hvort runan sé ganga. Á mynd 12.82 má sjá að hnútarnir eru samliggjandi í rununni og hún er því
ganga. Mynd 12.82. Athugaðu næst hvort einhver hnútur sé heimsóttur tvisvar. Athugaðu að upphaf og endir í sama hnúti telst hér ekki sem tvöföld heimsókn. Enginn hnútur var því heimsóttur tvisvar og gangan er einnig vegur. Að lokum athugum við hvort einhver leggur hafi verið farinn tvisvar; svo er ekki. Runan er því ganga, vegur og slóð.
- Athugaðu fyrst hvort runan sé ganga. Á mynd 12.83 má sjá að hnútarnir eru samliggjandi í rununni og hún er því ganga.
Mynd 12.83. Athugaðu næst hvort einhver hnútur sé heimsóttur tvisvar. Þar sem hnúturinn b er heimsóttur tvisvar er runan ekki vegur. Að lokum athugum við hvort einhver leggur sé farinn tvisvar. Enginn leggur er farinn tvisvar og runan er því slóð. Hún er bæði ganga og slóð.
Rásir
Í mörgum hagnýtum verkefnum netafræði, svo sem við gerð hagkvæmra dreifingarleiða, er skilyrði að byrja og enda á sama stað. Ganga, vegur eða slóð sem endar á sama stað eða í sama hnúti og hún hófst nefnist lokuð. Annars nefnist hún opin, það er hún byrjar og endar ekki á sama stað eða í sama hnúti. Taflan hér á eftir sýnir dæmi um lokaðar göngur, lokaðar slóðir og lokaða vegi.
| LÝSING | DÆMI | EIGINLEIKAR |
|---|---|---|
| Lokuð ganga er ganga sem hefst og endar í sama hnúti. | Víxlruna hnúta og leggja. Hefst og endar í sama hnúti. | |
| Lokuð slóð er slóð sem hefst og endar í sama hnúti. Hún er yfirleitt nefnd rás. | Engir leggir endurteknir. Hefst og endar í sama hnúti. | |
| Lokaður vegur er vegur sem hefst og endar í sama hnúti. Hann er einnig nefndur stefnd rás því farið er um rásarhlutanet. | Engir leggir eða hnútar endurteknir. Hefst og endar í sama hnúti. |
Þar sem göngur, slóðir og vegir tengjast innbyrðis gera lokaðar göngur, rásir og stefndar rásir það einnig.
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.
Dæmi 12.21
Lokuð ganga, rás eða stefnd rás greind
Gerum ráð fyrir að þú þurfir að fljúga frá Miami (MIA) til Orlando (MCO) og megir aðeins nota flugleiðirnar í netinu. Á leiðinni til Orlando kaupir þú miða með millilendingu í Key West (EYW), eins og sýnt er á mynd 12.86, en átt eftir að ákveða heimleiðina. Ákvarðaðu hvort ferðin fram og til baka sé lokuð ganga, rás og/eða stefnd rás miðað við heimleiðina sem lýst er í hverjum lið.
- Þú snerir aftur til Miami (MIA) með því að fara sömu leið til baka.
- Beina flugið til baka fór frá Orlando (MCO) en var beint til Fort Lauderdale (FLL). Þaðan flaugstu til Tampa (TPA) og síðan aftur til Miami (MIA).
Lausn
Hnútalitanir
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 notar n liti 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.
| Staðreynd | Dæmi |
|---|---|
| Mundu að sléttunet eru leyst úr flækju, það er hægt er að teikna þau á flatan flöt án þess að tveir leggir skerist. Ef net er sléttunet má lita það með fjórum eða færri litum. | |
| Hver hnútur fullkomins nets er aðlægur öllum öðrum hnútum og því þarf hver þeirra sérstakan lit. Litunartala fullkomins nets er jöfn fjölda hnútanna. | |
| Ef net hefur klíku, það er fullkomið hlutanet, þarf hver hnútur klíkunnar sérstakan lit og hnútar utan hennar kunna að krefjast fleiri lita. Litunartala nets er að minnsta kosti fjöldi hnúta í stærstu klíku þess. |
Litanir notaðar til að leysa verkefni
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.
Hnútar í sama lit eru ekki aðlægir og því eru engir árekstrar milli þeirra. Þar sem netið er þrílitun mætti tímasetja allar níu greinarnar í aðeins þrjá tímaramma.
Dæmi 12.22
Skilningur á litunartölum
Í dæmi 12.17 ræddum við framhaldsskóla sem heldur lokapróf í ensku 3 (E3), ensku 4 (E4), framhaldsstærðfræði (M), stærðfræðigreiningu (C), mannkynssögu (W), sögu Bandaríkjanna (U), líffræði (B) og eðlisfræði (P). Gefinn var listi yfir námskeið án sameiginlegra nemenda. Með þeim upplýsingum fundum við netið á mynd 12.63 þar sem leggir tengja próf með sameiginlega nemendur. Notaðu netið úr dæmi 12.17 til að svara hverri spurningu.
- Netið hefur klíku af stærð 4 sem hnútarnir P, E3, C og U mynda. Hvað segir það um litunartöluna?
- Netið er ekki sléttunet, það er ekki hægt að leysa það úr flækju. Hvað segir það um litunartöluna?
- Búðu til litun með því að lita fyrst hnútinn með hæsta stigið, lita síðan eins marga aðra hnúta og hægt er í hverjum lit í lækkandi röð eftir stigi og endurtaka ferlið fyrir ólituðu hnútana.
- Veistu hver minnsti mögulegi fjöldi tímaramma er? Ef svo er, hver er hann og hvernig veistu það? Ef ekki, hvaða gildi koma til greina?
Lausn
- Við þyrftum fjóra ólíka liti fyrir klíkuna með fjórum hnútum og því er litunartalan að minnsta kosti fjórir.
- Litunartalan gæti verið hærri en fjórir.
- Ferlið er sýnt í töflu 12.6.
Þetta er upphaflega netið. Hnútur B hefur hæsta stigið. Litaðu hnút B. Hnútur E3 er eini ólitaði hnúturinn sem er EKKI aðlægur B. Litaðu E3 í sama lit. Hnútarnir P, U, W og C eru ólituðu hnútarnir með hæsta stigið. Veldu einn þeirra til að lita. Litaðu P í nýjum lit. Hnútarnir E4 og M eru EKKI aðlægir P og M hefur hærra stig. Litaðu M í sama lit. E4 er eini ólitaði hnúturinn sem er EKKI aðlægur P eða M. Litaðu E4 í sama lit. Hnútarnir U, W og C eru ólituðu hnútarnir með hæsta stigið. Veldu einn þeirra til að lita. Litaðu U í nýjum lit. W er eini ólitaði hnúturinn sem er EKKI aðlægur U. Litaðu W í sama lit. C er eini ólitaði hnúturinn. Litaðu C í nýjum lit. Lituninni er lokið og fjórir litir voru notaðir. Tafla 12.6 Netið litað.Síðasta netið í töflu 12.6 sýnir endanlegu litunina.
- Já. Minnsti fjöldi tímaramma er litunartalan. Við vissum að litunartalan væri að minnsta kosti fjórir vegna klíkunnar með fjórum hnútum. Nú höfum við fundið fjórlitun netsins og því er litunartalan ekki hærri en fjórir. Hún hlýtur því að vera fjórir.
Fjórlitavandinn
Hugmyndin um að lita net til að leysa verkefni varð til út frá einu frægasta vandamáli stærðfræðinnar, fjórlitavandanum. Spurt var hvort fjórir litir nægðu alltaf til að lita kort, sama hve flókið það væri, þannig að engin tvö svæði með sameiginleg landamæri hefðu sama lit. Lengi grunaði alla að svo væri því engum tókst að búa til kort sem þyrfti fleiri en fjóra liti, en enginn gat sannað það almennt. Loks voru net notuð til að leysa vandann.
Í 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ð.
Athugaðu að netið sem táknar sameiginleg landamæri miðvesturríkjanna er sléttunet, það er hægt er að teikna það á flatan flöt án þess að leggir skerist. Eins og við höfum séð er litunartala sérhvers sléttunets fjórir eða lægri. Þessi vel þekkta staðreynd nefnist fjórlitasetningin eða fjórlitakortasetningin.
Dæmi 12.23
Lausn
Skrefin við að lita netið eru sýnd í töflu 12.7.
| Skref 1: Net þar sem stig hnútanna eru merkt. Hnútur IA hefur hæsta stigið. | Skref 2: Litaðu hnút IA í hvaða lit sem er. Hnútarnir ND, KS, MI, OH og IN eru EKKI aðlægir IA. MI og IN hafa hæsta stigið, 3. | Skref 3: Litaðu annaðhvort MI eða IN í sama lit og IA. Hnútarnir ND og KS eru einu ólituðu hnútarnir sem eru ekki aðlægir rauðum hnúti. Báðir hafa stigið 2. |
| Skref 4: Þar sem KS og ND eru ekki aðlægir má spara skref og lita báða rauða. Hæsta stig ólituðu hnútanna er fjórir. | Skref 5: Veldu einn hnút af stigi 4, SD, og litaðu hann í nýjum lit, bláum. Hnútarnir WI, IL, MO, IN og OH eru EKKI aðlægir bláum hnúti. WI, IL og MO hafa hæsta stigið. | Skref 6: Veldu WI, IL eða MO til að lita. Við litum WI bláan. MO, IN og OH eru EKKI aðlægir bláum hnúti. MO hefur hæsta stig þeirra. |
| Skref 7: Litaðu MO bláan. Allir ólituðu hnútarnir eru aðlægir bláum hnúti. Veldu nýjan lit. Fjórir hnútar eru eftir: MN, NE, IL og OH. MN, NE og IL hafa hæsta stigið. | Skref 8: Þar sem MN, IL og NE eru ekki aðlægir má spara skref og lita þá alla í nýja litnum, fjólubláum. OH er eini ólitaði hnúturinn. | Skref 9: Þar sem OH er ekki aðlægur fjólubláum hnúti skaltu lita hann fjólubláan. Þetta er endanlega netið. Við notuðum þrjá liti. |
Endanlega netið í töflu 12.7 sýnir hvernig lita á kortið. Á mynd 12.102 hefur kortið verið litað í samræmi við liti netsins.
Við notuðum þrjá liti til að lita netið. Það styður fjórlitasetninguna því netið er sléttunet og litunartala þess er lægri en fjórir.
Athugaðu skilning þinn
Í eftirfarandi verkefnum skaltu ákvarða hvort hver fullyrðing sé alltaf sönn eða stundum sönn.
Verkefni úr hluta 12.4
Í eftirfarandi verkefnum skaltu greina hverja hnútarrunu á myndinni sem göngu, slóð og/eða veg. Veldu allt sem á við.
Notaðu netin sem sýnd eru í eftirfarandi verkefnum. Tilgreindu netið eða netin með tiltekna eiginleika.
Í eftirfarandi verkefnum skaltu ljúka hnútarrununni úr netinu þannig að tiltekin gerð lokaðrar göngu fáist.
Notaðu netin sem sýnd eru í eftirfarandi verkefnum.
Kort af ríkjum Imaginaria er gefið. Notaðu myndina til að leysa eftirfarandi verkefni.
