12.3 Samanburður neta

Mynd 12.38 sýnir net A og F sem eru eins að öðru leyti en merkingum. Net eru sjónræn framsetning tengsla. Ef tvö net sýna sama tengslamynstur, eins og A og F, teljast þau einsmóta.

Ef annað skilyrðið fyrir einsmótun gildir gerir hitt það einnig. Til að ákveða hvort tvö net séu einsmóta þarf því að staðfesta annað þeirra. Á mynd 12.39 má til dæmis beygja og spegla net T þannig að það líti út eins og Z. Netin uppfylla því fyrsta skilyrðið og eru einsmóta.

Hnútarnir sem voru aðlægir í fyrra netinu eru enn aðlægir eftir umbreytinguna, eins og mynd 12.40 sýnir. Hnútur 3 er til dæmis enn aðlægur hnút 4; þeir eru enn grannhnútar sem einn leggur tengir.

Erfitt getur verið að staðfesta einsmótun, einkum fyrir stór net. Því er skynsamlegt að leita fyrst að augljósum mun svo tíma sé ekki varið í að sannreyna einsmótun sem ekki er til staðar. Ef tvö net eru ólík á einhvern þann hátt sem tafla 12.3 sýnir geta þau ekki verið einsmóta.

Einsmóta net geta litið mjög ólíkt út þótt grunngerð þeirra sé sú sama. Teygja og snúa má leggjunum og snúa eða spegla netinu. Á mynd 12.41 tákna allar teikningarnar til dæmis sama tengslamynstur.

Hvernig vitum við að netin á mynd 12.41 eru einsmóta? Fyrst leitum við að augljósum mun. Hvert þeirra hefur fjóra hnúta og fimm leggi. Næst skoðum við stig hnútanna sem eru merkt á mynd 12.42.

Á mynd 12.42 hefur hvert net tvo hnúta af stigi 2 og tvo af stigi 3. Þar er því enginn munur. Skoðum næst rásarhlutanetin sem eru auðkennd á mynd 12.43.

Á mynd 12.43 hefur hvert net tvo þríhyrninga og einn ferhyrning. Enginn munur er þar heldur. Líklegt virðist að netin séu einsmóta, en skoða þarf þau nánar til að vera viss.

Til að staðfesta einsmótun þarf að sannreyna annað tveggja skilgreiningarskilyrða. Fyrir lítil net má oft sjá fyrir sér hvernig teygja og snúa megi öðru í hitt. Ímyndaðu þér að leggirnir séu teygjanlegir. Ef þetta er hægt án þess að rjúfa eða bæta við tengslum eru netin í raun sama netið. Mynd 12.44 sýnir _hvernig A4 er _umbreytt í A3, _síðan A2 og _loks A1.

Sjónræn greining sýnir að fyrsta skilyrðið gildir fyrir A1, A2, A3 _og A4 og _þau eru því _einsmóta. Í A4 _skarast tveir leggir, en með umbreytingunni í A3 er netið „flækt í sundur“. Net sem _má teikna án skörunar leggja nefnast sléttunet. Fullkomið _net með fimm hnúta er dæmi um net sem er ekki sléttunet; ekki er hægt að leysa það úr flækju. Við samanburð neta er samt gagnlegt að leysa þau eins mikið úr flækju og hægt er svo líkindi og munur sjáist betur.

Mörg vinsæl borðspil líta ólíkt út en eru í raun sama spilið. Gott dæmi eru fjölmargar útgáfur Monopoly®, sem var skráð hjá einkaleyfastofu Bandaríkjanna árið 1935. Reglunum hefur verið breytt lítillega en mjög svipað spilaborð er enn notað. Margar útgáfur hafa fengið þemu úr sjónvarpsþáttum eða íþróttum en halda sömu grunngerð. Net sem tákna ólíkar útgáfur væru því einsmóta. Greinum nokkur spilaborð með netafræði til að sjá hvort þau hafi sömu gerð þrátt fyrir ólíkt útlit.

Þegar tvö net eru einsmóta hafa þau sömu gerð og samsvörun er milli hnútanna. Skrá má samsvarandi hnútapör þannig að hvert aðlægt par í öðru netinu samsvari aðlægu pari í hinu. Slík samsvörun nefnist netaeinsmótun. Skoðum einsmóta netin á mynd 12.38. Á mynd 12.51 mætti skipta merkingum F út fyrir merkingar A og fá eins net eins og á mynd 12.52.

Einsmótun milli A og F má því gefa með samsvarandi hnútapörum: b–g, c–h, d–i og e–j. Hnútur b er aðlægur c og g er aðlægur h, eins og verður að vera þar sem b samsvarar g og c samsvarar h. Hið sama gildir um önnur aðlæg pör.

Einsmótun tveggja neta þarf ekki að vera ótvíræð; fleiri en ein einsmótun getur verið til. Önnur einsmótun milli A og F fæst með því að snúa F réttsælis og bera saman við A. Þá fæst samsvörunin b–j, d–h, c–i og e–g eins og á mynd 12.53.

Gerum ráð fyrir að þú sért leiðbeinandi í sumarbúðunum Camp Woebegone og haldir þar íþróttakeppni með fjórum greinum. Þátttakendur hafa skráð sig í greinarnar. Þú teiknar netið á mynd 12.58 til að sjá betur hvaða greinar eiga þátttakendur sameiginlega.

Net E á mynd 12.58 sýnir að sumir sömu þátttakendur keppa í greinum a og b, b og d, c og d og a og c. Hvernig heldurðu að netið sem táknar greinar án sameiginlegra þátttakenda líti út? Það hefði sömu hnúta en hvert par sem er aðlægt í neti E væri ekki aðlægt í nýja netinu og öfugt. Slíkt net nefnist nykurnet og er sýnt á mynd 12.59. Tvö net eru nykurnet hvort annars ef þau hafa sama hnútamengi en hnútar sem eru aðlægir í öðru netinu eru ekki aðlægir í hinu. Þá má segja að annað netið sé nykur hins.

Ein leið til að finna nykur nets er að teikna fullkomið net með sama fjölda hnúta og fjarlægja alla leggi sem voru í upphaflega netinu. Segjum að finna eigi nykur nets E á mynd 12.59 án þess að vita fyrir fram að hann sé net F. Þá má byrja á fullkomnu neti með fjóra hnúta og fjarlægja leggina í neti E eins og sýnt er á mynd 12.60.