1212 Netafræði

12.10 Tré

Röð lauflausra trjáa. — **Mynd 12.203.** Í netafræði eiga net sem kallast tré margt sameiginlegt með lifandi trjám. (mynd: „Row of trees in Roslev“ eftir AKA CJ/Flickr, almenningseign)

Námsmarkmið

Eftir að hafa lokið þessum hluta átt þú að geta:

Lýst trjám og borið kennsl á þau.
Fundið spannandi tré tengds nets.
Fundið léttasta spannandi tré vegins nets.
Leyst hagnýt verkefni um tré.

Við geymdum það besta þar til síðast! Í þessum síðasta hluta fjöllum við um það sem margir telja skemmtilegustu netin: tré. Hefur þú einhvern tíma rannsakað ættartréð þitt? Ættartré eru fullkomið dæmi um trén sem við rannsökum í netafræði. Eitt einkenni ættartrés er að það myndar aldrei lykkju aftur að sjálfu sér, enda er enginn sitt eigið afar- eða ömmubarn!

Hvað er tré?

Hvort sem rætt er um ættartré eða tré í skógi liggur engin grein aftur og sameinast stofninum á ný. Tré hefur því engin rásarhlutanet, það er rásalaust. Tré hefur jafnframt aðeins einn samhengisþátt. Tré er því tengt rásalaust net. Netin á mynd 12.204 hafa öll þessa eiginleika og hvert þeirra er tré.

Þrjú net. Net T hefur 15 hnúta. Leggirnir eru ab, bc, cd, ci, ij, jk, ko, de, dl, en, em, bf, fg og gh. Net P hefur sex hnúta. Leggirnir eru ts, sr, rq, qp og po. Net S hefur sjö hnúta. Leggirnir eru ut, uv, uw, ux, uy og uz. — **Mynd 12.204.** Netin T, P og S

Æfum okkur að ákvarða hvort net sé tré. Til þess athugum við hvort netið sé tengt og án rása.

Dæmi 12.46

Tré borin kennsl á

Berðu kennsl á öll tré á mynd 12.205. Ef net er ekki tré skaltu útskýra hvernig það sést.

Þrjú net. Net M hefur sjö hnúta. Leggirnir eru ab, bf, fg, fc, bc, bd og de. Net N hefur sex hnúta. Leggirnir eru ij, ih, lk og lm. Leggirnir ij og lk skerast. Net P hefur sex hnúta. Leggirnir eru st, sr, rq, qp og po. — **Mynd 12.205.** Netin M, N og P

Lausn

Net M er ekki tré því það inniheldur rásina (b, c, f).
Net N er ekki tré því það er ekki tengt. Það hefur tvo samhengisþætti, annan með hnútunum h, i og j og hinn með hnútunum k, l og m.
Net P er tré. Það er tengt og hefur engar rásir.

Gerðir trjáa

Stærðfræðingar hafa haft gaman af því að nefna net sem eru tré eða innihalda tré. Netið á mynd 12.206 er til dæmis ekki tré en hefur tvo samhengisþætti, annan með hnútunum a til d og hinn með hnútunum e til g. Hvor þáttur um sig væri tré. Slík formgerð kallast skógur. Einnig eru til sérstök heiti á trjám með tiltekna eiginleika.

Vegnet, eða línulegt net, er tré með nákvæmlega tvo hnúta af stigi 1 þar sem allir aðrir hnútar mynda einn veg á milli þeirra. Því má teikna það sem beina línu.
Stjörnutré er tré með nákvæmlega einn hnút af stigi stærra en 1, sem kallast rót, og allir aðrir hnútar liggja að honum.
Stjörnulíkt tré er tré með eina rót og nokkra vegi sem tengjast henni.
Maðktré er tré með miðlægum vegi þar sem hnútar mega hafa hvaða stig sem er. Hver hnútur utan miðlæga vegarins liggur að hnúti á honum og hefur stigið 1.
Humrartré er tré með miðlægum vegi þar sem hnútar mega hafa hvaða stig sem er og vegir með einum eða tveimur leggjum tengjast miðlæga veginum.

Dæmi um hverja þessara formgerða sjást á mynd 12.207.

Net F hefur átta hnúta, merkta a til h. Leggirnir tengja ba, bd, bc, fe, fh og fg. — **Mynd 12.206.** Skógarnetið F

Sex net. Net S hefur sjö hnúta og leggina ab, bf, fg, fc, bc, bd og de. Net N hefur sex hnúta og leggina ij, ih, lk og lm; leggirnir ij og lk skerast. Net P hefur sex hnúta og leggina st, sr, rq, qp og po. Net Z hefur 12 hnúta og leggina ab, ac, ad, ae, af, ag, ah, hi, cj, ek og kl. Net C hefur 14 hnúta og leggina mn, nz, no, eða, op, ox, oy, py, px, ps, pt, pu, pq, pv og pw. Net L hefur 26 hnúta og leggina fq, ft, fs, fe, eo, ep, pz, ed, dm, mv, dn, ny, dc, ck, ku, cl, lk, cb, bi, it, bj, jw, ba, bg og bh. — **Mynd 12.207.** Sex gerðir trjáa

Dæmi 12.47

Gerðir trjáa bornar kennsl á

Hvort net á mynd 12.208 er ein af sérstöku trjágerðunum sem fjallað hefur verið um. Tilgreindu gerð hvers trés.

Tvö net. Net U hefur 17 hnúta og leggina oq, op, ol, ln, lk, lm, li, ij, if, fg, fh, fd, de, fb, bc og ba. Net V hefur sex hnúta og leggina rs, st, tu, uv og vw; leggirnir st og uv skerast. — **Mynd 12.208.** Netin U og V

Lausn

Net U hefur miðlæga veginn a → b → d → f → i → l → o → q. Hver hnútur utan vegarins hefur stigið 1 og liggur að hnúti á veginum. U er því maðktré.

Net V er vegnet því það er einn vegur sem tengir nákvæmlega tvo hnúta af stigi 1: r → s → u → v → w.

Eiginleikar trjáa

Við rannsóknir á trjám er gagnlegt að þekkja nokkra eiginleika þeirra. Ef legg er bætt við tré milli tveggja fyrirliggjandi hnúta myndast rás og netið er ekki lengur tré. Dæmi sjást á mynd 12.209. Þegar leggnum bj er bætt við net T myndast rásin (b, c, i, j). Þegar leggnum rt er bætt við net P myndast rásin (r, s, t). Þegar leggnum tv er bætt við net S myndast rásin (t, u, v).

Þrjú net. Net T hefur 15 hnúta og leggina ab, bc, cd, ci, ij, jk, ko, de, dl, en, em, bf, fg og gh. Leggirnir ci og ij eru bláir og strikalagður leggur tengir b og j. Net P hefur sex hnúta og leggina ts, sr, rq, qp og po. Leggirnir ts og sr eru bláir og strikalagður leggur tengir t og r. Net S hefur sjö hnúta og leggina ut, uv, uw, ux, uy og uz. Leggirnir ut og uv eru bláir og strikalagður leggur tengir t og v. — **Mynd 12.209.** Leggjum bætt við tré

Ef leggur er fjarlægður úr tré fjölgar samhengisþáttum og netið verður ótengt. Mynd 12.210 sýnir að þegar einn eða fleiri leggir eru fjarlægðir getur myndast skógur. Ef leggurinn qr er fjarlægður úr neti P myndast tveir samhengisþættir, annar með hnútunum o, p og q og hinn með hnútunum r, s og t. Ef leggurinn uw er fjarlægður úr neti S myndast tveir samhengisþættir, annar aðeins með hnútnum w og hinn með öllum öðrum hnútum. Þegar leggirnir bf og cd eru fjarlægðir úr neti T myndast þrír samhengisþættir eins og á mynd 12.210.

Þrjú net. Net T hefur 15 hnúta og leggina ab, bc, cd, ci, ij, jk, ko, de, dl, en, em, bf, fg og gh. Leggirnir dc og bf eru strikalagðir og netið skiptist í þrjá hluta. Net P hefur sex hnúta og leggina ts, sr, rq, qp og po. Leggurinn qr er strikalagður og netið skiptist í tvo hluta. Net S hefur sjö hnúta og leggina ut, uv, uw, ux, uy og uz. Leggurinn uw er strikalagður og netið skiptist í tvo hluta. — **Mynd 12.210.** Leggir fjarlægðir úr trjám

Mjög gagnlegur eiginleiki trjáa er að fjöldi leggja er alltaf einum minni en fjöldi hnúta. Sérhvert tengt net þar sem fjöldi leggja er einum minni en fjöldi hnúta er því örugglega tré. Dæmi sjást á mynd 12.211.

Sex net. Net T hefur 15 hnúta og leggina ab, bc, cd, ci, ij, jk, ko, de, dl, en, em, bf, fg og gh. Net P hefur sex hnúta og leggina ts, sr, rq, qp og po. Net S hefur sjö hnúta og leggina ut, uv, uw, ux, uy og uz. Net Z hefur 12 hnúta og leggina ab, ac, ad, ae, af, ag, ah, hi, cj, ek og kl. Net C hefur 14 hnúta og leggina mn, nz, no, eða, op, ox, oy, py, px, ps, pt, pu, pq, pv og pw. Net L hefur 26 hnúta og leggina fq, ft, fs, fe, eo, ep, pz, ed, dm, mv, dn, ny, dc, ck, ku, cl, lk, cb, bi, it, bj, jw, ba, bg og bh. — **Mynd 12.211.** Fjöldi hnúta og leggja í trjám og öðrum netum

Dæmi 12.48

Eiginleikar trjáa kannaðir

Notaðu netin I og J á mynd 12.212 til að svara spurningunum.

Tvö net. Net I hefur sex hnúta, a, b, c, d, e og f. Leggirnir tengja ab, bc, be, de og ef. Net J hefur sjö hnúta, g, h, i, j, k, l og m. Leggirnir tengja gh, hi, jh, jl, kl og lm. — **Mynd 12.212.** Netin I og J

Hvaða hnútar eru í hvorum samhengisþætti sem eftir stendur þegar leggurinn be er fjarlægður úr neti I?
Finndu fjölda leggja og hnúta í neti J. Útskýrðu hvernig þetta staðfestir að net J sé tré.
Hvers konar rás myndast ef leggnum im er bætt við net J?

Lausn

Þegar leggurinn be er fjarlægður standa eftir tveir samhengisþættir. Annar inniheldur hnútana a, b og c en hinn hnútana d, e og f.
Net J hefur sjö hnúta og sex leggi. Þetta staðfestir að net J sé tré því fjöldi leggja er einum minni en fjöldi hnúta.
Fimmhyrningurinn (i, h, j, l, m) myndast þegar leggnum im er bætt við net J.

Spannandi tré

Gerum ráð fyrir að þú ætlir að setja upp tölvunet með fjórum tækjum. Einn kostur er möskvaskipanin á mynd 12.213, þar sem hvert tæki tengist beint öllum öðrum tækjum netsins.

Fjórar myndir sýna algengar uppröðanir tölvuneta. Sú fyrsta sýnir möskvaskipan þar sem sex tölvur eru samtengdar. Önnur sýnir hringtengingu þar sem fimm tölvur mynda hring. Þriðja sýnir stjörnutengingu þar sem miðlæg tölva tengist fimm tölvum umhverfis hana. Sú fjórða sýnir trjáskipan þar sem tvær greinar ganga út frá láréttum stofni. Á hvorri grein er miðlæg tölva sem tengist fimm tölvum umhverfis hana. — **Mynd 12.213.** Algengar uppröðanir tölvuneta

Möskvaskipan fjögurra tækja má tákna með fullkomna netinu A₁ á mynd 12.214, þar sem hnútarnir tákna tækin og leggirnir nettengingarnar. Tækin má þó tengja með færri tengingum. Netin A₂, A₃ og A₄ á mynd 12.214 sýna uppröðun þar sem þrír af sex leggjum hafa verið fjarlægðir. Hvert þeirra er tré því það er tengt og hefur engar rásir. Þar sem A₂, A₃ og A₄ eru jafnframt _hlutanetA₁ sem innihalda alla hnúta upphaflega netsins kallast þau spannandi tré.

Fjögur net. Net A₁ hefur hnútana a, b, c og d og leggina ab, bd, dc, ca, ad og bc. Net A₂ hefur sömu fjóra hnúta og leggina ab, bc og cd. Net A₃ hefur sömu fjóra hnúta og leggina ab, ac og cd. Net A₄ hefur sömu fjóra hnúta og leggina ab, ac og ad. — **Mynd 12.214.** Uppröðun nets með fjórum tækjum

Samkvæmt skilgreiningu spannar spannandi tré allt netið með því að innihalda alla hnúta þess. Þar sem það er hlutanet má það aðeins hafa leggi milli hnúta sem lágu saman í upphaflega netinu. Þar sem það er tré er það tengt og rásalaust. Þegar metið er hvort net sé spannandi tré skal því athuga eftirfarandi:

Allir hnútar eru með.
Engir hnútar liggja saman sem lágu ekki saman í upphaflega netinu.
Netið er tengt.
Engar rásir eru til staðar.

Dæmi 12.49

Spannandi tré borin kennsl á

Notaðu mynd 12.215 til að ákvarða hvert netanna M₁, M₂, M₃ og _M₄sé spannandi tré netsins Q.

Fimm net. Net Q hefur hnútana a, b, c, d, e og f og leggina ab, ac, ad, bd, df, cd, ce, cf og ef. Net M₁ hefur sömu sex hnúta og leggina ab, bd, dc, ce, ef og fd. Net M₂ hefur sömu hnúta og leggina ab, ad, df, fe og ec. Net M₃ hefur sömu hnúta og leggina bd, df, af, fe og ec. Net M₄ hefur sömu hnúta og leggina ab, ce, ef og fd. — **Mynd 12.215.** Netin Q, M₁, M₂, M₃ og M₄

Lausn

Net _M₁er ekki spannandi tré nets Q því það hefur rásina (c, d, f, e).
Net M₂ er spannandi tré nets Q því það inniheldur alla upphaflegu hnútana, engir hnútar liggja saman í M₂ sem lágu ekki saman í Q, M₂ er tengt og hefur engar rásir.
Net M₃ er ekki spannandi tré nets Q því hnútarnir a og f liggja saman í M₃ en ekki í Q.
Net M₄ er ekki spannandi tré nets Q því það er ekki tengt.

Því er aðeins net M₂ spannandi tré nets Q.

Spannandi tré búið til með vegum

Gerum ráð fyrir að finna eigi spannandi tré inni í neti. Ein leið er að finna vegi í netinu. Hefja má göngu í hvaða hnúti sem er, fara í hvaða átt sem er og mynda veg um netið þar til ekki er hægt að halda áfram án þess að fara til baka, eins og á mynd 12.216.

Net með 23 hnúta og 35 leggi. Tíu leggir eru auðkenndir með grænum lit. Tveir hnútar eru merktir „byrjað hér“ og „stöðvað hér“. — **Mynd 12.216.** Fyrsti áfangi við gerð spannandi trés

Þegar stöðvað hefur verið skaltu velja hnút á veginum sem upphafspunkt nýs vegar. Gættu þess að heimsækja aðeins hnúta sem hafa ekki þegar verið heimsóttir, eins og á mynd 12.217.

Net með 23 hnúta og 35 leggi. Tíu leggir eru bláir og tíu grænir. Tveir hnútar eru merktir „byrjað hér“ og „stöðvað hér“. — **Mynd 12.217.** Millistig við gerð spannandi trés

Endurtaktu ferlið þar til allir hnútar hafa verið heimsóttir, eins og á mynd 12.218.

Net með 23 hnúta og 35 leggi. Tíu leggir eru bláir og tíu grænir. Tveir hnútar eru merktir „byrjað hér“ og „stöðvað hér“. Tveir leggir eru fjólubláir. — **Mynd 12.218.** Lokaáfangi við gerð spannandi trés

Niðurstaðan er tré sem spannar allt netið, eins og á mynd 12.219.

Net með 23 hnúta og 22 leggi. — **Mynd 12.219.** Spannandi tréð sem fæst

Þetta hlutanet er tré því það er tengt og rásalaust. Það inniheldur líka alla hnúta upphaflega netsins og er því spannandi tré. Þetta er þó ekki eina spannandi tré netsins. Með öðrum leiðarvölum mætti búa til mörg ólík spannandi tré.

Dæmi 12.50

Spannandi tré búin til

Búðu til tvö ólík spannandi tré fyrir netið á mynd 12.220.

Net L hefur 11 hnúta og 19 leggi. Það líkist ferningi undir þríhyrningi á hvorri hlið. Þríhyrningarnir tengjast með trapisu og hornalínur liggja í ferningunum. — **Mynd 12.220.** Net L

Lausn

Tvær mögulegar lausnir sjást á myndum 12.221 og 12.222.

Tvö net sýna leggi fjarlægða úr neti L. Fyrra netið hefur 11 hnúta og 19 leggi og líkist ferningi undir þríhyrningi á hvorri hlið. Þríhyrningarnir tengjast með trapisu og hornalínur liggja í ferningunum. Sex leggir eru grænir, tveir fjólubláir og tveir bláir. Grænt táknar áfanga 1, blátt áfanga 2 og fjólublátt áfanga 3. Seinna netið er lokatréð; svörtu leggir fyrra netsins hafa verið fjarlægðir. — **Mynd 12.221.** Fyrra spannandi tré nets L

Spannandi tré afhjúpuð

Önnur leið til að finna spannandi tré í tengdu neti er að fjarlægja óæskilega leggi og afhjúpa þannig spannandi tré. Skoðum net D á mynd 12.223.

Net D hefur tíu hnúta merkta a til j. Leggirnir eru cd, ca, da, ag, ah, gh, ab, be, bf, ef, bi, bj og ij. — **Mynd 12.223.** Net D

Net D hefur tíu hnúta. Spannandi tré þess verður að hafa níu leggi því í hverju tré er fjöldi leggja einum minni en fjöldi hnúta. Net D hefur 13 leggi og því þarf að fjarlægja fjóra. Til að ákveða hvaða fjóra leggi skal fjarlægja munum við að tré hafa engar rásir. Í D eru fjórir þríhyrningar sem þarf að rjúfa. Það má gera með því að fjarlægja einn legg úr hverjum þeirra. Þetta má gera á marga vegu og tveir þeirra sjást á mynd 12.224.

Fjögur net sýna leggi fjarlægða úr neti D. Í fyrsta netinu eru hnútarnir a til j og leggirnir cd, ca, da, ag, ah, gh, ab, be, bf, ef, bi, bj og ij. Leggirnir ac, ef, gh og bj eru strikalagðir. Annað netið er hið sama eftir að þessir leggir hafa verið fjarlægðir. Í þriðja netinu eru sömu hnútar og leggir en leggirnir ac, ag, bf og bi strikalagðir. Fjórða netið er hið sama eftir að þeir hafa verið fjarlægðir. — **Mynd 12.224.** Fjórir leggir fjarlægðir úr neti D

Dæmi 12.51

Leggir fjarlægðir til að finna spannandi tré

Notaðu netið á mynd 12.225 til að svara spurningunum.

Net V hefur níu hnúta merkta a til i. Leggirnir eru fc, fa, ca, cd, da, ab, be, eh, hi, ig og gb. — **Mynd 12.225.** Net V

Finndu hve marga leggi þarf að fjarlægja til að afhjúpa spannandi tré.
Nefndu allar óstefndar rásir í neti V.
Finndu tvö ólík spannandi tré nets V.

Lausn

Net V hefur níu hnúta og spannandi tré þess verður því að hafa átta leggi. Þar sem V hefur ellefu leggi þarf að fjarlægja þrjá til að afhjúpa spannandi tré.
(a, c, d), (a, c, f), (a, d, c, f) og (b, e, h, i, g)
Til að finna fyrra spannandi tréð fjarlægjum við legginn ac, sem rýfur báða þríhyrningana, legginn cf, sem rýfur ferhyrninginn, og legginn be, sem rýfur fimmhyrninginn. Þá fæst spannandi tréð á mynd 12.226. Mynd 12.226 Spannandi tré sem fæst með því að fjarlægja ac, cf og

be. Til að finna annað spannandi tré fjarlægjum við ad, sem

rýfur (a, c, d) og (a, d, c, f), af til að rjúfa (a, c, f) og hi til að rjúfa (b, e, h, i, g). Þá fæst spannandi tréð á mynd 12.227. Mynd 12.227 Spannandi tré

sem fæst með því að fjarlægja ad, af og hi.

Hver hefði trúað því?

Ástarkeðjur

Hér er óvenjuleg spurning í stærðfræðitíma: Hefur þú einhvern tíma átt í sambandi við fyrrverandi maka núverandi maka fyrrverandi maka þíns? Rannsóknir benda til þess að svarið sé líklega nei. Þegar rannsakendurnir Peter S. Bearman, James Moody og Katherine Stovel báru saman gagnkynhneigð ástarsambandanet í dæmigerðum miðvesturríkjaframhaldsskóla við hermd net fundu þau nokkuð óvænt. Raunverulegu félagsnetin líktust frekar spannandi trjám en öðrum mögulegum líkönum því stuttar rásir voru mjög fáar. Einkum voru fjórrásir nær engar.

Mynd 12.228. Ástarkeðjur

„Bannið við því að kona eigi í sambandi við fyrrverandi kærasta núverandi kærustu fyrrverandi kærasta síns skýrir formgerð ástarsambandanetsins í [framhaldsskólanum].“

Í greininni „Ástarkeðjur: Formgerð ástar- og kynferðissambandaneta ungmenna“ útskýrðu rannsakendurnir síðan áhrifin á útbreiðslu kynsjúkdóma. Félagsformgerðir sem byggjast á trjám eru einkum gisnari og líklegri til að sundrast. Þessar upplýsingar geta haft áhrif á félagslega stefnumótun um sjúkdómavarnir. (Peter S. Bearman, James Moody og Katherine Stovel, „Chains of Affection: The Structure of Adolescent Romantic and Sexual Networks“, American Journal of Sociology, 110. bindi, 1. tölublað, bls. 44–91, 2004)

Reiknirit Kruskals

Í mörgum hagnýtum verkefnum með spannandi tré eru netin vegin og finna þarf spannandi tré með lægsta mögulega vægi. Net getur til dæmis táknað tölvunet og vægin kostnað við að tengja tvö tæki. Að finna spannandi tré með lægsta heildarvægið, eða léttasta spannandi tré, sparar því peninga. Aðferðin sem við notum til að finna léttasta spannandi tré vegins nets kallast reiknirit Kruskals. Skref þess eru:

Skref 1: Veldu einhvern legg með lægsta vægi allra leggja.

Skref 2: Veldu annan legg með lægsta vægi meðal þeirra sem eftir eru. Seinni leggurinn þarf ekki að tengjast þeim fyrri.

Skref 3: Veldu enn einn legg með lægsta vægi meðal þeirra sem eftir eru en veldu engan legg sem myndar rás í hlutanetinu sem verið er að byggja.

Skref 4: Endurtaktu skref 3 þar til allir hnútar upphaflega netsins eru með og spannandi tré hefur myndast.

Dæmi 12.52

Reiknirit Kruskals notað

Setja á upp tölvunet með sex tækjum. Hnútarnir á mynd 12.229 tákna tækin og leggirnir kostnað tengingar. Finndu ódýrustu uppröðun netsins. Hver er heildarkostnaðurinn?

Net táknar tengikostnað milli sex tækja, A til F. Leggir frá A til B, C, D, E og F eru merktir 250, 210, 300, 200 og 100 dölum; frá B til C, D, E og F 220, 120, 160 og 170 dölum; frá C til D, E og F 310, 180 og 330 dölum; frá D til E og F 270 og 150 dölum; og leggurinn EF 350 dölum. — **Mynd 12.229.** Net kostnaðar við nettengingar

Lausn

Léttasta spannandi tréð samsvarar ódýrustu uppröðun netsins. Við finnum það með reikniriti Kruskals. Þar sem netið hefur sex hnúta hefur spannandi tréð sex hnúta og fimm leggi.

Skref 1: Veldu legg með lægsta vægið. Vægin hafa verið röðuð í stærðarröð. Lægsta vægið er 100 dalir og eini leggurinn með það vægi er AF, eins og á mynd 12.230.

Skref 2: Veldu legginn með lægsta vægi meðal þeirra sem eftir eru, BD með vægið 120 dalir. Leggirnir tveir sem valdir eru þurfa ekki að liggja saman, eins og sést á mynd 12.231.

Skref 3: Veldu legginn með lægsta vægi meðal þeirra sem eftir eru, svo framarlega sem hann myndar ekki rás. Við veljum DF með vægið 150 dalir því hann myndar ekki rás, eins og á mynd 12.232.

Endurtaktu skref 3: Veldu BE, legginn með lægsta vægi meðal þeirra sem eftir eru, 160 dali. Hann myndar ekki rás, eins og á mynd 12.233. Nú hafa fjórir leggir verið valdir og aðeins þarf að endurtaka skref 3 einu sinni til að fá fimmta legginn.

Endurtaktu skref 3: Lægsta vægi leggja sem eftir eru er 170 dalir. Bæði BF og CE hafa vægið 170 en BF myndi mynda rásina (b, d, f), sem spannandi tré má ekki innihalda, eins og á mynd 12.234.

Við veljum því CE og fullgerum spannandi tréð, eins og á mynd 12.235.

Léttasta spannandi tréð sést á mynd 12.236. Þetta er ódýrasta uppröðun netsins. Heildarvægi trésins er 100 + 120 + 150 + 160 $$ 100 + $ 120 + $ 150 + $ 160 + $ 170 = $ 700$ + 170 = 700 dalir, sem er heildarkostnaður nettengingarinnar.

Net hefur sex hnúta merkta A til F. Leggirnir eru bogni leggurinn AF, 100 dalir; BE, 160 dalir; BD, 120 dalir; CE, 170 dalir; og DF, 150 dalir. — **Mynd 12.236.** Léttasta spannandi tréð

Athugaðu skilning þinn

Fjöldi rása í spannandi tré er einum minni en fjöldi hnúta.

Satt
Ósatt

Spannandi tré inniheldur enga þríhyrninga.

Satt
Ósatt

Spannandi tré inniheldur alla hnúta upphaflega netsins.

Satt
Ósatt

Í spannandi tré liggur nákvæmlega einn vegur milli sérhvers hnútapars.

Satt
Ósatt

Spannandi tré verður að vera tengt.

Satt
Ósatt

Reiknirit Kruskals er aðferð til að finna öll ólík spannandi tré tiltekins nets.

Satt
Ósatt

Aðeins net sem eru sjálf tré hafa spannandi tré.

Satt
Ósatt

Finna má léttasta spannandi tré tiltekins nets með reikniriti Kruskals.

Satt
Ósatt

Léttasta spannandi tré tiltekins nets er hlutanet sem er tré, inniheldur alla hnúta upphaflega netsins og hefur lægsta vægi allra spannandi trjáa.

Satt
Ósatt

Ef net inniheldur brýr verða þær að vera í sérhverju spannandi tré þess.

Satt
Ósatt

Verkefni úr hluta 12.10

Notaðu myndina í eftirfarandi verkefnum.

Fjögur net. Net M hefur hnútana p, q, t, u og r og leggina qt, pu og ur. Net W hefur ellefu hnúta, a til k, og leggina ae, af, ab, bg, bh, bc, ci, cd, ck, aj og jk. Net R hefur sjö hnúta, a, b, c, d, e, f og h. Bogleggu leggirnir eru ab, bc, cd, de og ef og beinn leggur tengir b og h. Net X hefur tíu hnúta, a til j, og leggina ba, bc, bd, bi, bf, ie, ig, ih og ij.

Hvaða net eru tré, ef einhver?

Hvaða net eru ekki tré vegna þess að þau eru ekki tengd, ef einhver?

Hvaða net eru ekki tré vegna þess að þau innihalda rás, ef einhver?

Notaðu myndina í eftirfarandi verkefnum. Tilgreindu þau net sem passa við lýsinguna.

Sex net. Net T₁ hefur 16 hnúta merkta a, b, c, d, e, f, g, h, i, j, k, m, n, o, r og s og leggina bd, bc, ba, an, br, bf, rs, ri, eo, oi, ij, jk, ih, ig og gm. Net T₂ hefur sex hnúta, a til f, og leggina ab, ac, ad, ae og af. Net T₃ hefur ellefu hnúta, a til k, og leggina bd, fk, kb, bi, ic, aj, jb, bh, hg og ge. Net T₄ hefur átta hnúta, a til h, og leggina ab, bc, cd, de, ef, fg og gh. Net T₅ hefur 15 hnúta, a til o, og leggina ab, bc, bd, be, ef, eg, eh, ei, em, mj, mk, ml, mn og no. Net T₆ hefur tíu hnúta, a til j, og leggina ab, ac, ad, ae, af, jh, hg og hi.

Tré

Stjörnutré

Stjörnulíkt tré

Línulegt net (eða vegnet)

Humrartré

Maðktré

10.

Skógur

Notaðu myndina í eftirfarandi verkefnum til að svara spurningunum.

Tvö net. Net H hefur sjö hnúta, a til g, og leggina ab, ae, bd, ed, dc, df, fg og cg. Net Q hefur sjö hnúta, h til n, og leggina hi, hj, ij, ik, km, mn, ml, kl og nl.

11.

Ákvarðaðu hvort net H₁ sé spannandi tré nets H. Ef ekki skaltu útskýra hvernig það sést.

Net H₁ hefur sjö hnúta merkta a til g og leggina ab, bd, ed, df, fg og gc.

12.

Ákvarðaðu hvort net H₂ sé spannandi tré nets H. Ef ekki skaltu útskýra hvernig það sést.

Net H₂ hefur sjö hnúta merkta a til g og leggina ae, ed, db, dc, cf og fg.

13.

Ákvarðaðu hvort net H₃ sé spannandi tré nets H. Ef ekki skaltu útskýra hvernig það sést.

Net H₃ hefur sjö hnúta merkta a til g og leggina ab, ae, cd, df og cg.

14.

Ákvarðaðu hvort net Q₁ sé spannandi tré nets Q. Ef ekki skaltu útskýra hvernig það sést.

Net Q₁ hefur sjö hnúta merkta h til n og leggina jh, hi, ik, kl, km, lm og mn.

15.

Ákvarðaðu hvort net Q₂ sé spannandi tré nets Q. Ef ekki skaltu útskýra hvernig það sést.

Net Q₂ hefur sjö hnúta merkta h til n og leggina jh, hi, ik, km og ml.

16.

Ákvarðaðu hvort net Q₃ sé spannandi tré nets Q. Ef ekki skaltu útskýra hvernig það sést.

Net Q₃ hefur sjö hnúta merkta h til n og leggina hi, ij, ik, kl, lm og ln.

Í eftirfarandi verkefnum á nemandi að búa til spannandi tré nets

eins og sýnt er á myndinni. Strikalögðu leggirnir sýna fyrsta skref nemandans, þar sem vegur er myndaður frá hnúti

að hnúti

Net O hefur átta hnúta merkta a til h. Leggirnir eru af, ae, gf, ge, gh, he, ef, fb, bc, fc, cd, fd og de. Leggirnir he, ef, fb, bc og cd eru strikalagðir.

17.

Hve marga leggi til viðbótar þarf að taka með strikalögðu leggjunum til að mynda spannandi tré?

18.

Nefndu þrjá ónotaða, heila leggi í neti O sem ekki má nota til að fullgera spannandi tréð.

19.

Gefðu dæmi um mengi leggja þar sem e er ekki endahnútur og sem fullgerir spannandi tréð.

20.

Gefðu dæmi um mengi leggja þar sem f er ekki endahnútur og sem fullgerir spannandi tréð.

Í eftirfarandi verkefnum á nemandi að búa til spannandi tré nets

eins og sýnt er á myndinni. Strikalögðu leggirnir sýna fyrsta skref nemandans, þar sem vegur er myndaður frá hnúti

að hnúti

Net O hefur átta hnúta merkta a til h. Leggirnir eru af, ae, gf, ge, gh, he, ef, fb, bc, fc, cd, fd og de. Leggirnir gf, ge, eh og fc eru strikalagðir.

21.

Hve marga leggi til viðbótar þarf að taka með strikalögðu leggjunum til að mynda spannandi tré?

22.

Nefndu tvo ónotaða leggi í neti O sem ekki má nota til að fullgera spannandi tréð.

23.

Gefðu dæmi um mengi leggja þar sem f er ekki endahnútur og sem fullgerir spannandi tréð.

24.

Gefðu dæmi um mengi leggja þar sem hvorki c né e er endahnútur og sem fullgerir spannandi tréð.

Notaðu netin í eftirfarandi verkefnum.

Þrjú net. Net A hefur tvo ferhyrninga sem skarast, stuv og wxyz, og leggur tengir w við u. Net B hefur tvo ferhyrninga sem skarast, stzy og rvwx, og hnúturinn u er á milli rv og tz. Net C hefur sex hnúta og leggina st, tv, vw, wx, xu, wu, us og ut.

25.

Hve marga leggi þarf að fjarlægja úr neti A til að mynda spannandi tré?

26.

Hve marga leggi þarf að fjarlægja úr neti B til að mynda spannandi tré?

27.

Hve marga leggi þarf að fjarlægja úr neti C til að mynda spannandi tré?

28.

Tilgreindu öll ólík rásarhlutanet nets A.

29.

Tilgreindu öll rásarhlutanet nets B.

30.

Tilgreindu öll rásarhlutanet nets C.

31.

Teiknaðu fjögur spannandi tré nets A sem hvert inniheldur leggina vs, uv, wz og xy.

32.

Teiknaðu fjögur spannandi tré nets B sem innihalda legginn ut en ekki ur.

33.

Teiknaðu fjögur spannandi tré nets C sem hvert hefur aðeins einn legg með endahnútinn u.

Notaðu myndina í eftirfarandi verkefnum. Teiknaðu net sem passar við lýsinguna.

Fjögur net. Hvert net hefur hnútana a, b, c og d. Fyrsta netið hefur leggina ac, cd og cb. Annað hefur leggina ab, bd og dc. Þriðja hefur leggina ba, ac og cd. Fjórða hefur leggina ad, bd og cd.

34.

S₁, S₂, S₃ og S₄ eru öll spannandi tré.

35.

_S₁og S₂ eru spannandi tré en S₄ er það ekki.

36.

_S₃og S₄ eru spannandi tré en S₁ er það ekki.

37.

_S₂og S₃ eru spannandi tré en S₁ er það ekki.

38.

_S₂og S₃ eru spannandi tré en S₄ er það ekki.

39.

_S₁,_S₂og S₃ eru spannandi tré en S₄ er það ekki.

40.

_S₂,S₃ og S₄ eru spannandi tré en S₁ er það ekki.

41.

_S₁og S₄ eru spannandi tré en S₂ og S₃ _eruþað ekki.

Notaðu myndina í eftirfarandi verkefnum til að finna vægi gefins spannandi trés.

Net Z hefur níu hnúta í þremur röðum og þremur dálkum. Fyrsta röð er q, r, s; önnur t, u, v; og þriðja w, x, y. Leggirnir og vægi þeirra eru qt, 1; sv, 2; rs, 3; qu, 4; uy, 5; rv, 6; ru, 7; vy, 8; wx, 9; xy, 10; ux, 11; tw, 12; qr, 13; tu, 14; og uv, 15.

42.

Net hefur níu hnúta í þremur röðum og þremur dálkum: q, r, s; t, u, v; og w, x, y. Leggirnir eru qu, ru, rs, tu, uv, tw, ux og xy.

43.

Net hefur níu hnúta í þremur röðum og þremur dálkum: q, r, s; t, u, v; og w, x, y. Leggirnir eru qr, ru, rs, tu, uv, tw, wx og vy.

44.

Net hefur níu hnúta í þremur röðum og þremur dálkum: q, r, s; t, u, v; og w, x, y. Leggirnir eru qr, rs, ru, tu, uv, ux, wx og xy.

45.

Notaðu reiknirit Kruskals til að teikna léttasta spannandi tré nets Z á myndinni. Finndu vægi þess.

Teiknaðu léttasta spannandi tré gefins nets í eftirfarandi verkefnum og reiknaðu vægi þess.

46.

Net A

47.

Net C

48.

Net B

49.

Net D

Teiknaðu vegið net sem táknar gefnar upplýsingar í eftirfarandi verkefnum. Notaðu netið síðan til að finna léttasta spannandi tré og vægi þess. Útskýrðu hvað vægið táknar í aðstæðunum.

50.

Borgarskipuleggjendur eiga að leggja vegi milli staðanna A, B, C og D. Kostnaður við veg milli sérhverra tveggja


	staða
er
gefinn		í
	töflunni.

Byggingarkostnaður í þúsundum milli staða.

51.

Í tölvuleik er markmiðið að heimsækja löndin fimm V, W, X, Y og Z án þess að missa öll lífin. Leiðir milli landanna hafa hættueinkunn frá 1, sem er minnst hætta, til 10, sem er mest. Þegar leið hefur verið farin með góðum


				er
				hún
*hættulaus.*				Einkunnirnar
	eru
	gefnar	í	töflunni.

Hættueinkunnir leiða milli landa.