1212 Netafræði

12.2 Gerð neta

Segulómunarmynd sýnir virka hnúta í heilanum. — **Mynd 12.16.** Taugamyndgreining sýnir virkni heilans. (mynd: „MRI Scan“ eftir NIH Image Gallery/Flickr, almenningseign)

Námsmarkmið

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

Lýst og túlkað tengsl í netum.
Sett tengsl fram með netum.

Netafræði er notuð í taugavísindum til að rannsaka tengsl ólíkra hluta heilans. Taugalíffræðingar nota starfræna segulómun (fMRI) til að mæla blóðmagn í ólíkum hlutum heilans, sem nefnast hnútar. Þegar hnútar eru virkir samtímis bendir það til starfrænna tengsla þeirra og þeir mynda net. Setja má netið fram þannig að hnútarnir séu hnútar netsins og starfrænu tengslin leggirnir. (Mikey Taylor, „Graph Theory & Machine Learning in Neuroscience“, Medium.com, 24. júní 2020.)

Mikilvægi stiga hnúta

Ein ástæða þess að vísindamenn rannsaka slík net er að kanna hve vel samskipti innan þeirra haldast þegar hnútar eða tengingar bila. Nota má net til að rannsaka þol kerfanna. (Mikey Taylor, „Graph Theory & Machine Learning in Neuroscience“, Medium.com, 24. júní 2020.)

Dæmi 12.6

Net notuð til að skilja tengsl

Netin á mynd 12.17 tákna tauganet þar sem hnútarnir eru taugahnútar og leggirnir starfræn tengsl þeirra. Hvaða net telur þú hafa mest bilanaþol? Hvaða net er líklega viðkvæmast fyrir bilun? Hvernig gæti það tengst stigum hnútanna?

Þrjú net, A, B og C, tákna líkön tauganeta. Netin hafa n leggi og hnúta. — **Mynd 12.17.** Líkön tauganeta

Lausn

Net B táknar kerfið með mesta bilanaþol því fleiri leggir tengja hnútana en í hinum netunum. Fleiri mögulegar leiðir eru því fram hjá biluðum legg eða hnút. Net A er líklega viðkvæmast vegna þess að tengslin byggjast á fáum tilteknum leggjum og hnútum. Fleiri hnútar hafa hátt stig í neti B en A vegna þess að fleiri leggir tengja hnútana.

Tengsl fjölda leggja og stiga hnúta

Í beitingu netafræði í taugavísindum og félagsfræði í dæmi 12.6 og Þínu verkefni 12.6 var fylgni milli stiga hnúta og seiglu nets. Rannsakendur á mörgum sviðum hafa einnig séð bein tengsl milli fjölda leggja og stiga hnúta. Skoðum fyrst net með fimm hnúta og engan legg eins og á mynd 12.18.

Net hefur fimm hnúta og enga leggi. Hnútarnir eru merktir 0. — **Mynd 12.18.** Net með fimm hnúta og enga leggi

Í stað nafns er hver hnútur á mynd 12.18 merktur með stigi sínu. Öll stigin eru 0 og summa þeirra því einnig 0. Bætum nú legg milli tveggja hnúta og merkjum stig þeirra. Þá fæst net með fimm hnúta og einum legg eins og á mynd 12.19.

Net hefur fimm hnúta: þrír eru merktir 0 og tveir 1. Leggur tengir hnútana sem merktir eru 1. — **Mynd 12.19.** Net með fimm hnúta og einum legg

Stig tveggja hnúta hækkuðu hvort um 1 og summa stiganna er nú 2. Höldum áfram með því að bæta við einum legg í senn og skrá fjölda leggja og summu stiga hnútanna eins og á mynd 12.20.

Fjögur net. Fyrsta netið er merkt: leggir 2, summa stiga 4. Það hefur fimm hnúta, tvo af stigi 0, tvo af stigi 1 og einn af stigi 2. Annað netið er merkt: leggir 3, summa stiga 6, og hefur fjóra hnúta af stigi 1 og einn af stigi 2. Þriðja netið er merkt: leggir 4, summa stiga 8, og hefur þrjá hnúta af stigi 1, einn af stigi 2 og einn af stigi 3. Fjórða netið er merkt: leggir 5, summa stiga 10, og hefur tvo hnúta af stigi 1, tvo af stigi 3 og einn af stigi 2. — **Mynd 12.20.** Fjöldi leggja borinn saman við summu stiga

Mynd 12.20 sýnir eiginleika sem gildir um öll net, óháð lögun og stærð. Þegar einum legg er bætt við hækkar summa stiganna um tvo. Ástæðan er að hver leggur hefur tvo enda og hvor endi hækkar stig eins hnúts um einn. Summa stiga hnúta í neti er því alltaf tvöfaldur fjöldi leggja. Þessi regla nefnist summusetning stiga.

Dæmi 12.7

Summa stiga fundin

Gerum ráð fyrir að net hafi fimm leggi.

Finndu summu stiga hnútanna.
Teiknaðu tvö ólík net sem sýna niðurstöðuna.

Lausn

Summa stiganna er tvöfaldur fjöldi leggja: 2 × 5 = 10. Summa stiganna er 10.
Sjá mynd 12.21.

Tvö net eru merkt 1 og 2. Net 1 hefur sex hnúta af stigunum 1, 2, 2, 2, 2 og 1 og fimm leggi. Net 2 hefur fjóra hnúta af stigunum 3, 2, 3 og 2 og fimm leggi. — **Mynd 12.21.** mynd 12.21

Fullkomleiki

Gerum ráð fyrir að fimm ókunnugir, A, B, C, D og E, séu í herbergi og að kynna eigi hvern þeirra fyrir öllum hinum. Hve margar kynningar þarf? Byrja má á að teikna net þar sem hver hnútur táknar einstakling og hver leggur kynningu eins og á mynd 12.22.

Fimm net bera heitin 4 leggir, 3 leggir til viðbótar, 2 leggir til viðbótar, 1 leggur til viðbótar og 4 + 3 + 2 + 1 = 10 leggir. Í síðasta netinu tengja leggir öll pör hnútanna A, B, C, D og E. — **Mynd 12.22.** Líkan af kynningum fimm ókunnugra

Skoðum fyrst hve marga nýja einstaklinga A hittir, síðan B og þannig áfram án þess að endurtaka kynningu. A hittir B, C, D og E, samtals fjórar kynningar. B á þá eftir að hitta C, D og E, þrjár kynningar til viðbótar. C hittir D og E, tvær til viðbótar, og D hittir aðeins E, eina til viðbótar. Lokanetið hefur $4 + 3 + 2 + 1 = 10$ leggi sem tákna tíu kynningar. Það er fullkomið net því leggur tengir hvert hnútapar; hver hnútur er aðlægur öllum öðrum. Mynd 12.23 sýnir fullkomin net með þrjá, fjóra, fimm og sex hnúta.

Fjögur net. Fyrsta netið hefur hnútana a, b og c og alla þrjá mögulega leggi. Annað hefur hnútana a, b, c og d og alla sex mögulega leggi. Þriðja hefur hnútana a, b, c, d og e og alla tíu mögulega leggi. Fjórða hefur hnútana a, b, c, d, e og f og alla fimmtán mögulega leggi. — **Mynd 12.23.** Fullkomin net með allt að sex hnúta

Ef sex einstaklingar eru í herberginu þarf $5 + 4 + 3 + 2 + 1 = 15$ kynningar. Það er fjöldi leggja í fullkomnu neti með sex hnúta. Almennt fæst fjöldi kynninga milli 𝑛 $n$ einstaklinga með því að leggja saman heilu tölurnar frá 1 til 𝑛 − 1 $n - 1$ .

Gerum ráð fyrir að finna þurfi fjölda kynninga meðal 500 ókunnugra, það er fjölda leggja í fullkomnu neti með 500 hnúta. Það tæki langan tíma að leggja saman allar tölur frá 1 til 499. Í næsta dæmi notum við summusetningu stiga til að einfalda verkefnið.

Dæmi 12.8

Stig summusetningin notuð

Notaðu summusetningu stiga til að finna fjölda kynninga sem þarf í herbergi með

6 ókunnuga.
10 ókunnuga.
$n$ 𝑛 n ókunnuga.

Lausn

Ókunnugir eru 6 og hnútarnir því 6. Hver einstaklingur hittir 5 aðra, svo 5 leggir mætast í hverjum hnút og stig hvers hnúts er 5. Summa stiganna er $6 \cdot 5 = 30$ . Samkvæmt summusetningu stiga er fjöldi leggja helmingur summunnar, $\frac{30}{2} = 15$ . Kynningarnar eru því 15.
Ókunnugir eru 10 og hnútarnir því 10. Hver einstaklingur hittir 9 aðra, svo 9 leggir mætast í hverjum hnút og stig hvers hnúts er 9. Summa stiganna er $10 \cdot 9 = 90$ . Samkvæmt summusetningu stiga er fjöldi leggja helmingur summunnar, $\frac{90}{2} = 45$ . Kynningarnar eru því 45.
Ókunnugir eru 𝑛 $n$ og hnútarnir því 𝑛 $n$ . Hver einstaklingur hittir 𝑛 − 1 $n - 1$ aðra, svo 𝑛 − 1 $n - 1$ leggir mætast í hverjum hnút og stig hvers hnúts er 𝑛 − 1 $n - 1$ . Summa stiganna er 𝑛(𝑛 − 1) $n$ ( $n - 1$ ). Samkvæmt summusetningu stiga $n (n - 1)$ er fjöldi leggja helmingur summunnar, 𝑛(𝑛 − 1)/2 n(n − 1)/2. Kynningarnar eru því $\frac{n (n - 1)}{2}$ 𝑛(𝑛 − 1)/2 n(n − $\frac{n (n - 1)}{2}$ 1)/2.

Nú höfum við styttri leið til að reikna fjölda kynninga meðal 𝑛 $n$ ókunnugra og fjölda leggja í fullkomnu neti með 𝑛 $n$ hnúta. Uppfærum formúluna.

Hlutanet

Stundum er net hluti af stærra neti. Net flugvalla í Suður-Flórída á mynd 12.7 er til dæmis hluti af stærra neti sem einnig nær til alþjóðaflugvallarins í Orlando í Mið-Flórída, eins og sést á mynd 12.24.

Net hefur sex hnúta. Leggir tengja Tampa TPA við Key West EYW, Miami MIA, Fort Lauderdale FLL og West Palm Beach PBI. Leggur tengir Key West við Miami og annar Key West við Fort Lauderdale. Leggir frá Orlando MCO tengja við Key West, Miami og Fort Lauderdale. — **Mynd 12.24.** Orlando og flugvellir Suður-Flórída

Netið á mynd 12.24 hefur viðbótarhnútinn MCO og viðbótarleggi sem sýndir eru með strikalínum. Net beins flugs milli flugvalla Suður-Flórída á mynd 12.7 nefnist hlutanet stærra netsins sem einnig nær til Orlando. Almennt er net B hlutanet nets A ef allir hnútar og leggir B eru úr stærra netinu A.

Dæmi 12.9

Hlutanet greint

Á mynd 12.25 er net G ásamt fjórum teikningum. Ákvarðaðu hvort hver teikning sé hlutanet G og útskýrðu hvers vegna.

Fimm net. Net G hefur hnútana a, b, c, d og e og leggina ab, bc, cd, de, ea, ad og be. Teikning J hefur sömu hnúta og leggina ab, ae, ad, ec og cd. K hefur hnútana a, e, c og d og leggina ae, ad og dc. L hefur hnútana a, b, c og d og leggina ad, dc og bc. M hefur hnútana a, b, c, d og f og leggina ab, bc, cd, af og fd. — **Mynd 12.25.** Net G og möguleg hlutanet

Lausn

Teikning J er ekki hlutanet G því leggurinn ec er ekki í G.
Teikning K er hlutanet G því allir hnútar hennar og leggir eru hlutar G.
Teikning L er alls ekki net því lína liggur frá hnút a án þess að tengja hann við annan hnút. L getur því ekki verið hlutanet.
Teikning M er ekki hlutanet G því hún inniheldur hnút f sem er ekki í G.

Rásir greindar og nefndar

Mynd sýnir hringrás vatns. Vatn gufar upp úr sjó, þéttist í ský og fellur síðan sem úrkoma. Yfirborðsrennsli frá fjöllum berst í stöðuvatn og þaðan aftur til sjávar. — **Mynd 12.26.** Hringrás vatns hefst og endar með vatni. (mynd: „Diagram of the water cycle“ eftir NASA, almenningseign)

Í daglegu máli er hringrás eitthvað sem hefst og endar á sama hátt. Hringrás vatns á mynd 12.26 hefst til dæmis með vatni í stöðuvatni eða sjó. Það gufar upp, þéttist í ský og fellur síðan aftur til jarðar sem regn eða önnur úrkoma sem safnast í vötn eða sjó. Rás í netafræði er áþekk: hún er röð samhangandi leggja sem hefst og endar í sama hnút en endurtekur annars engan hnút.

Í rás er fjöldi hnúta alltaf jafn fjölda leggja og allir hnútar hafa stig 2. Rásir eru oft kenndar við hnútarfjöldann; rás með fimm hnúta nefnist 5-rás. Einnig má nefna þær eftir marghyrningum út frá fjölda leggja. Þannig er 5-rás einnig fimmhyrningur. Tafla 12.1 sýnir heitin fyrir rásir af stærð 3 til 10.

Flokkur rásar	Fjöldi leggja	Dæmi
þríhyrningur	3
ferhyrningur	4
fimmhyrningur	5
sexhyrningur	6
sjöhyrningur	7
átthyrningur	8
níuhyrningur	9
tíhyrningur	10

Til eru mun fleiri marghyrningaheiti, þar á meðal milljónhyrningur með milljón leggi og gúgólhyrningur með $10^{100}$ 10 100 leggi. Þegar 𝑛 $n$ er stærra en 10 er þó yfirleitt einfaldlega talað um 𝑛 $n$ -hyrning. Rás með 11 leggi má því kalla 11-hyrning.

Tíu rásin, eða tíhyrningurinn, virðist skarast við sjálfa sig í töflu 12.1. Mundu að teikna má net á ólíkan hátt þótt þau tákni sömu tengsl. Á mynd 12.27 er sami tíhyrningur ummyndaður þannig að hann virðist ekki skarast. Engri tengingu var breytt, svo báðar teikningar tákna sömu tengsl og teljast tíhyrningar.

Tvö net. Fyrra netið táknar tíhyrning með 10 leggi og 10 hnúta. Hið síðara hefur einnig 10 leggi og 10 hnúta en leggirnir skarast ekki. — **Mynd 12.27.** Ummyndun tíhyrnings

Rásarhlutanet og klíkur

Þegar rás kemur fyrir sem hlutanet stærra nets nefnist hún rásarhlutanet. Rásarhlutanet eru nefnd með því að skrá hnúta þeirra í röð. Ekki skiptir máli í hvaða hnút er byrjað. Net K á mynd 12.28 hefur tvær þríhyrningsrásir, (g, h, j) og (h, i, j), og eina ferhyrningsrás, (g, h, i, j).

Fjögur net. Net K hefur hnútana g, h, i og j og leggina hi, ij, jg, gh og hj. Annað netið sýnir rásina (g, h, j), það þriðja (h, i, j) og það fjórða (g, h, i, j). — **Mynd 12.28.** Rásir í neti K

Dæmi 12.10

Rásarhlutanet greind

Tilgreindu gerðir rásarhlutaneta í neti H á mynd 12.29 og nefndu þau.

Net hefur sjö hnúta, a, b, c, d, e, f og g, og leggina ab, bc, cd, de, ef, fa, bg og gf. — **Mynd 12.29.** Net H

Lausn

Til að missa ekki af rás skaltu byrja á hnút a og halda áfram í stafrófsröð. Hnútur a er í tveimur rásum, ferhyrningsrásinni (a, b, f, g) og sexhyrningsrásinni (a, b, c, d, e, f). Hnútur b er einnig í sexhyrningsrásinni (b, c, d, e, f, g). Athugun hinna hnútanna sýnir engar fleiri rásir.

Félagsfræðingar nota net til að rannsaka gerð samfélagsneta. Þar er þekkt regla um lokun þrennda: ef tveir einstaklingar eiga sameiginlegan vin aukast líkurnar á að þeir verði einnig vinir. Opin þrennd verður þá lokuð þrennd. Á mynd 12.30 eru þessar aðstæður sýndar með netum. Í opnu þrenndinni eru a og b hvort um sig vinir c. Í lokuðu þrenndinni hafa a og b einnig orðið vinir. Net lokuðu þrenndarinnar er 3-rás, eða þríhyrningur. (Chakraborty, Dutta, Mondal og Nath, „Application of Graph Theory in Social Media“, International Journal of Computer Sciences and Engineering, 6(10):722–729.)

Tvö net tákna opna og lokaða þrennd. Fyrra netið hefur hnútana a, b og c og leggina ac og cb. Hið síðara hefur sömu hnúta og leggina ac, cb og ba. — **Mynd 12.30.** Net opinnar og lokaðrar þrenndar

Klíka er annað hugtak sem vekur áhuga félagsfræðinga, tölvunarfræðinga og vísindamanna á mörgum sviðum. Í félagshópi er klíka undirhópur þar sem allir eru vinir. Þrennd er klíka þriggja einstaklinga en klíkur geta verið af hvaða stærð sem er. Í netafræði er klíka fullkomið hlutanet.

Dæmi 12.11

Þrenndir og klíkur greindar

Netin í Þínu verkefni 12.6 tákna samfélög. Hnútarnir eru einstaklingar og leggirnir félagsleg tengsl. Notaðu netin til að svara spurningunum.

Hvaða net hefur flestar þrenndir? Nefndu þríhyrningana.
Hvaða net hefur fæstar þrenndir? Nefndu þríhyrningana.
Hvaða áhrif gæti fjölgun þrennda í neti haft á seiglu samfélags? Útskýrðu rök þín.
Tilgreindu klíku með fleiri en þrjá hnúta í neti E með því að nefna hnútana.

Lausn

Net E hefur flestar þrenndir. Þríhyrningarnir eru (a, b, c), (a, c, e), (a, c, f), (a, c, g), (a, e, g), (c, e, g), (e, g, h), (e, h, i) og (f, g, i).
Net D hefur fæstar þrenndir. Engir þríhyrningar eru í netinu.
Fleiri þrenndir þýða að fleiri hnútar hafa hátt stig og benda því til meiri seiglu. Ef einn leggur er til dæmis fjarlægður úr lokaðri þrennd eru einstaklingarnir tveir sem ekki lengur eru aðlægir enn tengdir í gegnum þriðja einstaklinginn.
Hnútarnir a, e, c og g mynda klíku með fjóra hnúta.

Þrírásir í fullkomnum netum

Rétt eins og fjöldi leggja í fullkomnu neti er fyrirsjáanlegur er fjöldi rásarhlutaneta þess einnig fyrirsjáanlegur. Skoðum þrírásir í fullkomnum netum með allt að sex hnúta á mynd 12.31.

Skráum alla þríhyrninga í hverju neti. Þar sem hvert hnútapar er aðlægt mynda hvaða þrír hnútar sem er í fullkomnu neti þríhyrning. Fullkomið net með þrjá hnúta hefur aðeins þríhyrninginn (a, b, c). Fyrir stærri net þarf skipulegt verklag. Byrjaðu á bókstafnum sem kemur fyrst í stafrófi og skráðu í stafrófsröð alla þríhyrninga sem innihalda hann. Haltu síðan áfram með næsta bókstaf en slepptu þríhyrningum sem þegar hafa verið skráðir, eins og sýnt er í töflu 12.2.

Fullkomið net með:	3 hnúta	4 hnúta	5 hnúta	6 hnúta
Allir þríhyrningar með a	$(a, b, c)$	$(a, b, c), (a, b, d), (a, c, d)$	( a, b, c ), ( a, b, d ), ( a, b, e ) ( a, c, d ), ( a, c, e ) ( a, d, e )	( a, b, c ), ( a, b, d ), ( a, b, e ), ( a, b, f ) ( a, c, d ), ( a, c, e ), ( a, c, f ) ( a, d, e ), ( a, d, f ) ( a, e, f )
Aðrir þríhyrningar með b	Engir	$(b, c, d)$	$(b, c, d), (b, c, e), (b, d, e)$	( b, c, d ), ( b, c, e ), ( b, c, f ) ( b, d, e ), ( b, d, f ) ( b, e, f )
Aðrir þríhyrningar með c	Engir	Engir	$(c, d, e)$	$(c, d, e), (c, d, f) (c, e, f)$
Aðrir þríhyrningar með d	Engir	Engir	Engir	$(d, e, f)$
Samtals	1	( 2 + 1 ) + 1 = 3 + 1 = 4 ( 2 + 1 ) + 1 = 3 + 1 = 4	( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 = 6 + 3 + 1 = 1 0 ( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 = 6 + 3 + 1 = 10	( 4 + 3 + 2 + 1 ) + ( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 = 1 0 + 6 + 3 + 1 = 2 0 ( 4 + 3 + 2 + 1 ) + ( 3 + 2 + 1 ) + ( 2 + 1 ) + 1 = 10 + 6 + 3 + 1 = 20

Skoðaðu síðustu línu töflu 12.2. Sérðu mynstur í fjölda þríhyrninga í fullkomnu neti? Án þess að teikna fullkomið net með sjö hnúta má spá að það hafi $(5 + 4 + 3 + 2 + 1) + (4 + 3 + 2 + 1) + (3 + 2 + 1) + (2 + 1) + 1 = 35$ þríhyrninga. Mynstrið birtist einnig í frægri talnamynd sem vestrænir stærðfræðingar nefna þríhyrning Pascals. Mynd 12.32 sýnir fyrstu ellefu línurnar. Lína 0 inniheldur aðeins töluna 1 og fyrsta og síðasta stak annarra lína er einnig 1. Önnur stök fást með því að leggja saman tvö stök úr fyrri línu. Í línu 6 er stak 1 til dæmis 6, sem fæst úr 1 + 5, og stak 2 er 15, sem fæst úr 5 + 10.

Þríhyrningur Pascals með línum 0 til 10. Lína 0: 1. Lína 1: 1, 1. Lína 2: 1, 2, 1. Lína 3: 1, 3, 3, 1. Lína 4: 1, 4, 6, 4, 1. Lína 5: 1, 5, 10, 10, 5, 1. Lína 6: 1, 6, 15, 20, 15, 6, 1. Lína 7: 1, 7, 21, 35, 35, 21, 7, 1. Lína 8: 1, 8, 28, 56, 70, 56, 28, 8, 1. Lína 9: 1, 9, 36, 84, 126, 126, 84, 36, 9, 1. Lína 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1. Talan 6 í línu 6 fæst með því að leggja saman 1 og 5 úr línu 5 og 15 með því að leggja saman 5 og 10. Lína 7 og skálínan með staki 3 eru auðkenndar. Stak 3 í línu 7 er 35, fjöldi þríhyrninga í fullkomnu neti með sjö hnúta. — **Mynd 12.32.** Þríhyrningur Pascals

Ef stök númer 3 í línum þríhyrnings Pascals eru skráð ofan frá fást 1, 4, 10, 20, 35 og svo framvegis. Þetta er einmitt fjöldi þríhyrninga í fullkomnum netum með 3, 4, 5, 6 og 7 hnúta. Stak 3 í línu 7 er 35, fjöldi þríhyrninga í fullkomnu neti með sjö hnúta. Æfum nú notkun þríhyrnings Pascals til að finna þríhyrningafjölda í fullkomnu neti af tiltekinni stærð.

SKREF TIL AÐ FINNA FJÖLDA ÞRÍHYRNINGA Í FULLKOMNU NETI MEÐ n HNÚTA

Skref 1: Reiknaðu stök línu n í þríhyrningi Pascals með því að leggja saman stakapör úr fyrri línum eftir þörfum.

Skref 2: Fjöldi þríhyrninga er stak 3 í línu n. Mundu að telja stökin 0, 1, 2 og 3 frá vinstri.

Dæmi 12.12

Þríhyrningur Pascals notaður til að finna fjölda þríhyrninga í fullkomnu neti

Notaðu þríhyrning Pascals á mynd 12.32 til að finna fjölda þríhyrninga í fullkomnu neti með 11 hnúta.

Lausn

Skref 1: Finndu númer línunnar og reiknaðu stök hennar. Þar sem netið hefur 11 hnúta þarf línu 11 í þríhyrningi Pascals. Notaðu línu 10 á mynd 12.32 til að finna stök línu 11 eins og á mynd 12.33.

Línur 10 og 11 í þríhyrningi Pascals. Lína 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10 og 1. Lína 11: 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11 og 1. Örvar sýna hvernig samliggjandi tölur línu 10 leggja saman í tölur línu 11. — **Mynd 12.33.** Línur 10 og 11 í þríhyrningi Pascals

Skref 2: Finndu stak 3. Fjöldi þríhyrninga er í staki 3. Mundu að byrja talningu á staki 0 eins og á mynd 12.34.

Línur 10 og 11 í þríhyrningi Pascals. Lína 10: 1, 10, 45, 120, 210, 252, 210, 120, 45, 10 og 1. Lína 11: 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11 og 1. Stök línu 11 eru númeruð frá 0 til 11 og örvar sýna samlagninguna úr línu 10. — **Mynd 12.34.** Stak í þríhyrningi Pascals greint

Stak 3 í línu 11 er 165. Fullkomið net með 11 hnúta hefur því 165 þríhyrninga.

Kannaðu skilning þinn

Fullkomið net með fjóra hnúta hlýtur að hafa nákvæmlega fjóra leggi.

Satt
Ósatt

Í rás hefur hver hnútur stig 2.

Satt
Ósatt

Fjöldi hnúta í neti er tvöfaldur fjöldi leggja.

Satt
Ósatt

Rásina (a, b, c, d) má einnig nefna (c, b, a, d).

Satt
Ósatt

Rásina (a, b, c, d) má einnig nefna (a, b, d, c).

Satt
Ósatt

Einu klíkurnar sem eru rásir eru klíkur með þrjá hnúta.

Satt
Ósatt

Nemandi fann að summa stiga hnúta í neti væri 13. Hvers vegna er það ómögulegt?

Nemandi finnur fjölda leggja í fullkomnu neti með því að helminga fjölda hnúta, draga einn frá hnútarfjöldanum og margfalda niðurstöðurnar. Fær nemandinn rétt svar?

Æfingar úr kafla 12.2

Notaðu myndina til að svara eftirfarandi æfingum.

Fimm net eru merkt S, T, U, V og W. Net S hefur hnútana a, b, c, d og e og leggina ab, ac, bc, cd, ce og de. T hefur hnútana a, b, d og e og leggina ab, ae, bd og de. U hefur hnútana a, b, f, c, d og e og leggina ab, af, fd, bc, cd, de, ce og ac. V hefur hnútana a, b, d og e og leggina ab, ad, ae, bd og de. W hefur sömu hnúta og leggina ab, ad og de.

Skráðu öll net sem eru hlutanet nets U.

Skráðu öll net sem eru hlutanet nets V.

Útskýrðu hvers vegna net T er ekki hlutanet nets S.

Skráðu öll net með ferhyrningsrás sem hlutanet og nefndu ferhyrningana.

Notaðu summusetningu stiga eftir þörfum til að svara eftirfarandi æfingum.

Hve margir leggir eru í neti ef summa stiga hnútanna er 18?

Teiknaðu tvö möguleg net sem sýna að summa stiga hnúta í neti með 7 leggi er 14. Merktu stig hnútanna.

Hver er summa stiga hnúta í neti með 122 leggi?

Net hefur 3 hnúta af stigi 2, 4 hnúta af stigi 1 og 2 hnúta af stigi 3. Hve margir leggir eru í netinu?

Net hefur 6 hnúta og 11 leggi: 2 hnúta af stigi 5, einn af stigi 4 og 2 af stigi 3. Hvert er stig hnútsins sem eftir er?

10.

Fullkomið net hefur 5 hnúta. Hver er summa stiga hnútanna?

11.

Fullkomið net hefur 120 leggi. Hve marga hnúta hefur það?

Notaðu myndina til að svara eftirfarandi æfingum. Tilgreindu netið eða netin með gefinn eiginleika.

Fjögur net. Net 1 hefur hnútana a, b, c, d, e og f og leggina ab, bc, be, de og ef. Net 2 hefur hnútana p, q, r, s, t, u og v og leggina pq, qr, ps, qs, rt, qt, su og tv. Net 3 hefur átta hnúta, g, h, i, j, k, o, m og n, og allir tengjast hver öðrum. Net 4 hefur hnútana a, b, c, d, e, f, g, h og i og leggina ab, bc, cf, ad, dg, gh, eh, ef og ei.

12.

Summa stiga hnútanna er 16.

13.

Netið er fullkomið.

14.

Netið hefur engin rásarhlutanet.

15.

Netið inniheldur að minnsta kosti einn átthyrning.

16.

Netið inniheldur nákvæmlega tvær 3-rásir.

Notaðu myndina til að svara eftirfarandi æfingum. Tilgreindu netið eða netin með gefinn eiginleika.

Fjögur net. Net 5 hefur hnútana p, q, r, s, t og u og leggina pq, qr, pt, rt, st og tu. Net 6 hefur sjö hnúta, a, b, c, d, e, f og g, sem allir tengjast hver öðrum. Net 7 hefur hnútana h, i, j, k, m, n, o og p og leggina pi, im, mp, oh, hj, jk, kn og no. Net 8 hefur hnútana q, r, s, t, u, v, w, x og y og leggina qr, rs, sv, vy, yx, xw, wt, tq, qx og rv.

17.

Netið er hlutanet nets 6.

18.

Summa stiga hnútanna er 16.

19.

Netið er fullkomið.

20.

Netið hefur enga fimmhyrninga.

21.

Netið inniheldur að minnsta kosti einn átthyrning.

22.

Netið inniheldur nákvæmlega tvö rásarhlutanet.

23.

Notaðu töflu 12.1 til að nefna sjöhyrning í neti 8.

Notaðu myndina til að svara eftirfarandi æfingum. Tilgreindu netið eða netin með gefinn eiginleika.

Fjögur net. Net 9 hefur sex hnúta, i, j, k, m, n og o, sem allir tengjast hver öðrum. Net 10 hefur hnútana t, w, y, u, v, x og z og leggina tw, wy, vx, xz, uw, ux og xy. Net 11 hefur hnútana a, b, c, d, e, f, g og h og leggina ab, bc, cd, de, ef, fg, gh og ha. Net 12 hefur hnútana p, q, r, s, t, u, v, w og x og leggina pq, qr, ru, ux, xw, wv, vs, sp, pt, tx, rt, tv, st, tu, qt og tw.

24.

Summa stiga hnútanna er 16.

25.

Netið er fullkomið.

26.

Netið inniheldur nákvæmlega einn ferhyrning.

27.

Netið inniheldur að minnsta kosti einn átthyrning.

28.

Netið inniheldur nákvæmlega eitt rásarhlutanet.

Notaðu töflu 12.1 og myndina hér á eftir til að svara æfingunum.

29.

Skráðu alla ferhyrninga í neti 12.

30.

Skráðu alla ferhyrninga í neti 10.

31.

Finndu fjölda ferhyrninga í neti 9.

Notaðu myndina til að svara eftirfarandi æfingum.

Net hefur sex hnúta, A, B, C, D, E og F, og leggina AB, BC, CD, AC, CE, DF, EF, DE og CF.

32.

Nefndu fimm þríhyrninga í netinu.

33.

Tilgreindu klíku með fleiri en þrjá hnúta með því að skrá hnúta hennar.

Teiknaðu net með gefnum eiginleikum í eftirfarandi æfingum.

34.

4 hnútar, 6 leggir og hlutanet sem er 4-rás.

35.

11 hnútar og einu rásarhlutanetin eru þríhyrningar.

36.

Fullkomið net án ferhyrningshlutanets.

37.

4 hnútar, 4 leggir og engin rásarhlutanet.

38.

Fullkomið net þar sem summa stiga hnútanna er 20.

39.

7 hnútar og stærsta klíkan hefur 5 hnúta.

40.

Í skák getur riddari færst í hvaða átt sem er, en hann færist tvo reiti og beygir síðan um einn reit. Átta mögulegar færslur riddara af miðjureit fimm sinnum fimm reita borðs sjást á fyrri myndinni. Teiknaðu net sem táknar allar löglegar færslur riddara á þriggja sinnum þriggja reita borði með upphaf í neðra vinstra horni eins og á síðari myndinni. Hnútarnir tákna reiti sem riddarinn stendur á og leggirnir færslu milli reita.

Fimm sinnum fimm reita skákborð. Riddari er á miðjureit og átta örvar sýna L-laga færslur hans: tvo reiti lárétt og einn lóðrétt eða tvo lóðrétt og einn lárétt.

Þriggja sinnum þriggja reita skákborð. Riddarinn er í neðra vinstra horni.

41.

Hvers konar rás er netið sem þú teiknaðir í æfingu 40?

42.

Notaðu þríhyrning Pascals til að finna fjölda þríhyrninga í fullkomnu neti með 14 hnúta.

43.

Telur þú líklegt að net sem táknar vinatengsl á Facebook sé fullkomið? Útskýrðu rök þín.

44.

Myndi net ættartrés, þar sem leggir tákna tengsl foreldris og barns, innihalda rásir? Hvers vegna eða hvers vegna ekki?

45.

Við höfum séð að fjöldi þríhyrninga í fullkomnu neti með 7 hnúta fæst með mynstrinu

(5 + 4 + 3 + 2 + 1) + \left( {4 + 3 + 2 + 1} \right) + (3 + 2 + 1) + \left( {2 + 1} \right) + 1 = 35

. Mynstrið verður mjög langt fyrir stærri net, en við höfum áður notað styttri leið fyrir summu talna frá 1 upp að tiltekinni tölu. Úr dæmi 12.8 vitum við að 1 + 2 + 3 + ⋯ +

1 + 2 + 3 + \cdots + (n - 1) = \frac{{n(n - 1)}}{2}

(𝑛 − 1) = 𝑛(𝑛 − 1)/2. Hverja summu má

n - 1

því skrifa á forminu 𝑛(𝑛 − 1)/2. Fyrir summuna 1 til 5 er 𝑛 −

\frac{{n(n - 1)}}{2}

1
= 5 og því 𝑛 = 6: 1 + 2

n - 1 = 5

n = 6{:}

1 + 2 + 3 + 4 + 5 = \frac{{6(5)}}{2}

3 + 4 + 5 = 6(5)/2. Á sama hátt

n - 1 = 4

fæst

n = 5{:}

1 + 2 + 3 + 4 = \frac{{5(4)}}{2}

1 + 2 + 3 + 4 = 5(4)/2, 1 +

n - 1 = 3

n = 4{:}

1 + 2 + 3 = \frac{{4(3)}}{2}

+ 3 = 4(3)/2, 1 + 2 = 3(2)/2 og

n - 1 = 2

n = 3{:}

1 + 2 = \frac{{3(2)}}{2}

= 2(1)/2. Notaðu þetta til að endurskrifa útreikning þríhyrningafjöldans fyrir sjö hnúta: (5 + 4 + 3 + 2 + 1)

n - 1 = 1

n = 2{:}

1 = \frac{{2(1)}}{2}

(4 + 3 + 2 + 1) + (3 + 2 + 1) + (2 + 1) + 1 =

\begin{gathered} (5 + 4 + 3 + 2 + 1) + \left( {4 + 3 + 2 + 1} \right) + (3 + 2 + 1) + \left( {2 + 1} \right) + 1 \hfill \\ = \underbrace 1_{\frac{{2(1)}}{2}} + \underbrace {(1 + 2)}_{\frac{{3(2)}}{2}} + \underbrace {(1 + 2 + 3)}_{\frac{{4(3)}}{2}} + \underbrace {(1 + 2 + 3 + 4)}_{\frac{{5(4)}}{2}} + \underbrace {(1 + 2 + 3 + 4 + 5)}_{\frac{{6(5)}}{2}} \hfill \\ = \frac{{2(1)}}{2} + \frac{{3(2)}}{2} + \frac{{4(3)}}{2} + \frac{{5(4)}}{2} + \frac{{6(5)}}{2}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad \hfill \\ {\text{ = }}\underbrace {\frac{{1\left( 2 \right) + 2\left( 3 \right) + 3\left( 4 \right) + 4\left( 5 \right) + 5\left( 6 \right)}}{2}}_{{\text{The number of triangles in complete graph with 7 vertices}}{\text{.}}} = 35\quad\quad\quad\quad\quad\quad\,\, \hfill \\ \end{gathered}

2(1)/2 + 3(2)/2 + 4(3)/2 + 5(4)/2 + 6(5)/2 = 35. Fyrir fullkomið net með 8 hnúta má

(6 + 5 + 4 + 3 + 2 + 1) + (5 + 4 + 3 + 2 + 1) + \left( {4 + 3 + 2 + 1} \right) + (3 + 2 + 1) + \left( {2 + 1} \right) + 1 = 56

á sama hátt nota styttri

\frac{{1\left( 2 \right) \,+\, 2\left( 3 \right) \,+\, 3\left( 4 \right) \,+\, 4\left( 5 \right) \,+\, 5\left( 6 \right) \,+\, 6(7)}}{2} = 56

formúluna
[1(2) + 2(3) + 3(4) + 4(5) + 5(6) + 6(7)]/2 = 56. Notaðu mynstrið til að finna fjölda þríhyrninga í fullkomnu neti með 10 hnúta. Í hvaða línu og staki þríhyrnings Pascals finnst sama niðurstaða?

46.

Notaðu að summan frá 1 til 𝑛 − 1

n - 1

\frac{{n(n - 1)}}{2}

𝑛(𝑛 − 1)/2 n(n − 1)/2 til að skrifa formúlu fyrir fjölda þríhyrninga í fullkomnu neti með n hnúta.