Kaflayfirlit
Grunnhugtök netafræði
Notaðu myndina í eftirfarandi verkefnum.
1.Finndu fjölda hnúta í neti S.
2.Tilgreindu netið með fæsta leggi.
4.Tilgreindu öll hnútapör í neti S sem liggja ekki saman.
5.Hvaða net hefur aðeins hnúta af stigi 2?
6.Tilgreindu netið þar sem summa hnútastiganna er 16.
7.Amazon.com rekur net vöruhúsa sem flytja pakka um Bandaríkin. Vörubílar frá vöruhúsunum flytja pakka til annarra staða og sækja jafnframt pakka til að flytja aftur í heimavöruhúsið. Útskýrðu hvernig teikna mætti net eða fjölnet sem líkan af þessu með því að tilgreina hvaða hlutir gætu verið hnútar og hvaða tengsl leggir. Segðu hvort net eða fjölnet sé betra líkan.
8.Eduardo á tvo fjögurra vina hópa, A og B. Innan hvors hóps eru allir vinir hver annars en ekki fólks í hinum hópnum. Fólkið í hópi A á enga aðra vini. Hver einstaklingur í hópi B á hins vegar sinn eigin fjögurra vina hóp. Innan hvers slíks hóps eru allir vinir hver annars en enginn á vini utan síns hóps. Teiknaðu net sem táknar aðstæðurnar.
Formgerðir neta
Notaðu myndina í eftirfarandi verkefnum.
9.Útskýrðu hvers vegna net B er ekki hlutanet nets C.
10.Tilgreindu öll net sem hafa ferhyrnt rásarhlutanet og nefndu hnútana.
11.Tilgreindu klíku í neti C með því að skrá hnútana.
12.Teiknaðu net með eftirfarandi eiginleika: Stærsta klíkan hefur fjóra hnúta, netið hefur fimmhyrnt rásarhlutanet og nákvæmlega tvo hnúta af stigi 4.
13.Hve margir leggir eru í fullkomnu neti með 12 hnúta?
14.Hve margir þríhyrningar eru í fullkomnu neti með 11 hnúta?
Samanburður neta
15.Tilgreindu þrjá eiginleika sem eru ólíkir í netum 1 og 2 og sýna að þau séu ekki einsmóta.
Notaðu myndina í eftirfarandi verkefnum.
16.Ákvarðaðu hvort net 3 sé einsmóta neti 4. Ef svo er skaltu gefa samsvörun milli hnúta sem sýnir einsmótunina. Ef ekki skaltu tilgreina að minnsta kosti tvo eiginleika sem staðfesta það.
17.Ákvarðaðu hvort net 3 sé einsmóta neti 5. Ef svo er skaltu gefa samsvörun milli hnúta sem sýnir einsmótunina. Ef ekki skaltu tilgreina eiginleika sem staðfestir það.
18.Skoðaðu net 4 og 5. Ákvarðaðu hvort annað sé hlutanet hins. Ef svo er skaltu gefa samsvörun milli hnúta sem sýnir tengslin. Ef ekki skaltu tilgreina ósamrýmanlega eiginleika.
Notaðu myndina í eftirfarandi verkefnum.
19.Teiknaðu nykur neta 7 og 9. Ákvarðaðu hvort nykurnetin séu einsmóta og útskýrðu hvernig þú veist það. Notaðu niðurstöðuna til að ákvarða hvort net 7 og 8 séu einsmóta.
20.Teiknaðu nykur neta 7 og 10. Ákvarðaðu hvort nykurnetin séu einsmóta og útskýrðu hvernig þú veist það. Notaðu niðurstöðuna til að ákvarða hvort net 7 og 10 séu einsmóta.
21.Teiknaðu nykur neta 8 og 9. Ákvarðaðu hvort nykurnetin séu einsmóta og útskýrðu hvernig þú veist það. Notaðu niðurstöðuna til að ákvarða hvort net 8 og 9 séu einsmóta.
Ferðir um net
Notaðu net
A
á myndinni í eftirfarandi verkefnum. Fyrir hverja hnútarunu skaltu ákvarða hvort hún sé aðeins ganga, bæði ganga og vegur, bæði ganga og slóð, allt þrennt eða ekkert af þessu.
23.e → b → d → e → f → c → b → d
á mynd 12.352. Flokkaðu hverja hnútarunu sem lokaða göngu, rás (lokaða slóð) og/eða stefnda rás (lokaðan veg). Tilgreindu allt sem á við.
25.n → o → q → n → p → m → n
26.m → n → o → q → n → p → o → n → m
á mynd 12.352 í eftirfarandi verkefnum.
28.Eru net A og K sléttunet? Hvað segir svarið um litunartölu hvors nets?
29.Hve margir hnútar eru í stærsta fullkomna hlutaneti A? Hvað segir það um litunartölu A?
30.Búðu til litun nets A sem notar nákvæmlega fjóra liti eða útskýrðu hvers vegna það er ekki hægt.
31.Búðu til litun nets K sem notar nákvæmlega tvo liti eða útskýrðu hvers vegna það er ekki hægt.
32.Finndu litunartölu nets A og gefðu litun sem styður niðurstöðuna.
33.Finndu litunartölu nets K og gefðu litun sem styður niðurstöðuna.
Euler-rásir
Notaðu netin og fjölnetin á myndinni í eftirfarandi verkefnum. Tilgreindu þau sem hafa gefna eiginleika. Ef ekkert þeirra á við skaltu taka það fram.
Euler-slóðir
Notaðu netin og fjölnetin á mynd 12.354 í eftirfarandi verkefnum.
37.Skráðu hnútamengi hvers samhengisþáttar í neti 13.
38.Ákvarðaðu hvort leggjarunan K → L → N → M → O → S → T → Q → U → P →
R sé Euler-rás í fjölneti 15.
39.Finndu Euler-rás í neti 12 sem hefst og endar í hnúti g, ef slík rás er til. Annars skaltu útskýra hvernig þú veist að hún sé ekki til.
40.Gefðu dæmi um tvo leggi sem mætti afrita til að Euler-væða fjölnet 14.
Notaðu netin og fjölnetin á mynd 12.354 í eftirfarandi verkefnum. Tilgreindu þau sem hafa gefna eiginleika. Ef ekkert þeirra á við skaltu taka það fram.
41.Nákvæmlega tveir hnútar hafa oddatölustig
43.Hefur nákvæmlega eina staðbundna brú
Notaðu netin og fjölnetin á mynd 12.354 í eftirfarandi verkefnum. Í hverju verkefni er gefið net og hnútaruna.
44.Ákvarðaðu hvort leggjarunan A → B → C → H → G → D → F → E sé Euler-slóð, Euler-rás eða hvorugt í netinu. Ef hún er hvorugt skaltu útskýra hvers vegna.
45.Gerum ráð fyrir að legg væri bætt við net 11 milli hnútanna s og w. Ákvarðaðu hvort netið hefði Euler-slóð eða Euler-rás og finndu hana.
Hamilton-rásir
Notaðu netið á myndinni í eftirfarandi verkefnum.
46.Nemandi á að nota reiknirit Fleurys til að búa til Euler-slóð í netinu og ákveður að byrja í hnúti d. Er það góður kostur? Rökstyddu svarið.
47.Nemandi sem notar reiknirit Fleurys til að búa til Euler-slóð hefur byrjað á f → d → a → b → …. Ef byrjunin er rétt skaltu ljúka Euler-slóðinni. Ef nemandinn hefur gert mistök skaltu útskýra þau.
48.Notaðu reiknirit Fleurys til að búa til Euler-slóð í neti 16 og veldu sjálf(ur) upphafshnút.
Notaðu netin á myndunum í eftirfarandi verkefnum til að ákvarða hvort gefin hnútaruna sé Hamilton-rás, Euler-rás, hvort tveggja eða hvorugt.
49.Net F: a → b → e → c → b → d → c → a
50.Net K: m → n → q → o → p → m
51.Net A: b → d → e → f → c → b → e
Reiknaðu gildi aðfeldisins fyrir gefið gildi
54.Reiknaðu fjölda ólíkra Hamilton-rása í fullkomnu neti með 13 hnúta.
Notaðu myndina í eftirfarandi verkefnum til að finna vægi hverrar Hamilton-rásar.
55.q → t → w → x → u → y → v → s → r → q
56.w → x → y → u → v → s → r → q → t → w
Hamilton-vegir
Notaðu myndina í eftirfarandi verkefnum til að ákvarða hvort hnútarunan í gefnu neti sé Hamilton-vegur, Euler-slóð, hvort tveggja eða hvorugt.
57.Net A: e → b → c → f → e → b → e
58.Net A: b → c → f → e → d → b → e
Rifjaðu upp þrjár algengar aðstæður þar sem Hamilton-vegur getur ekki legið milli tveggja hnúta.
Aðstæður 1:
Ef leggurinn
a–b
er brú er enginn Hamilton-vegur milli hnútapars sem er sömu megin við legginn
a–b.
Aðstæður 2:
Ef leggurinn
a–b
er brú með að minnsta kosti þrjá samhengisþætti öðrum megin, þá getur Hamilton-vegur hvorki hafist né endað í
a
eða
b
.
Aðstæður 3:
Ef net er sett saman úr tveimur rásum sem tengjast aðeins í einum hnúti
p,
og
v
er einhver hnútur sem liggur
ekki
að
p,
þá getur enginn Hamilton-vegur hafist eða endað í
p.
Tilgreindu í eftirfarandi verkefnum þær aðstæður sem tryggja að enginn Hamilton-vegur sé milli gefins hnútapars í netinu.
Skólastjóri grunnskóla ætlar að heimsækja hverja kennslustofu nákvæmlega einu sinni áður en hann fer heim. Grunnmynd skólans er sýnd. Notaðu upplýsingarnar í eftirfarandi verkefnum.
63.Teiknaðu net sem táknar grunnmynd skólans, þar sem hver hnútur er herbergi og leggur milli tveggja hnúta merkir að leið liggi milli herbergjanna án þess að fara fram hjá dyrum annars herbergis.
64.Notaðu netið til að finna leið fyrir skólastjórann sem hefst á skrifstofunni í herbergi A, heimsækir hvert herbergi nákvæmlega einu sinni án þess að fara fram hjá öðru herbergi og endar í herbergi F við útganginn.
65.Er best að lýsa leiðinni sem Hamilton-vegi, Euler-slóð, hvoru tveggja eða hvorugu í netinu sem þú teiknaðir? Rökstyddu svarið.
Farandsölumannsvandinn
Ákvarðaðu í eftirfarandi verkefnum hvort lýst reiknirit sé gráðugt eða tæmandi.
66.Timburdreifingaraðili hleður vörubíla með það að markmiði að nota sem fæsta bíla. Fyrst er hlaðið lengstu vörubrettunum sem rúmast og haldið áfram þar til ekkert meira kemst fyrir. Síðan er næsti bíll hlaðinn með sömu aðferð.
67.Ferðamaður vill heimsækja fimm borgir með flugi. Hann skráir allar mögulegar raðir borganna, reiknar besta flugverð fyrir hverja ferðaáætlun og velur ódýrasta kostinn.
Skráðu í eftirfarandi verkefnum allar ólíkar Hamilton-rásir í gefnu neti sem hefjast í tilgreindum hnúti. Tilgreindu hvaða rásapör eru andhverfur hvert annars.
Finndu í eftirfarandi verkefnum Hamilton-rás með lægsta vægið í gefnu neti á mynd 12.362 með tæmandi aðferðinni og tilgreindum upphafshnúti. Hvert er vægi rásarinnar?
Finndu í eftirfarandi verkefnum Hamilton-rás með lágt vægi í gefnu neti á mynd 12.362 með aðferð næsta granna og tilgreindum upphafshnúti. Hvert er vægi rásarinnar?
74.Vörur verksmiðju eru framleiddar í áföngum. Sami búnaður er notaður í öllum áföngum en þarf að stilla hann á mismunandi hátt fyrir ólík verkefni. Tíminn til að skipta milli stillinga er gefinn í töflunni. Notaðu töfluna
| til |
|
|
|
|
|
|
|
| að |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
teikna net þar sem hnútarnir tákna verkefnin A,
C,
D,
F og G og vægi leggja umstillingartíma í mínútum. Notaðu aðferð næsta granna til að finna röð verkefnanna A, C,
D, F
og G sem heldur umstillingartíma lágum og endar með sömu stillingu og í upphafi svo verksmiðjan sé tilbúin fyrir næstu lotu. Engar skorður eru á röð verkefna. Ábending: Aðferð næsta granna getur gefið ólíkar niðurstöður eftir upphafshnúti og því þarf að prófa alla möguleika.
Tré
Teiknaðu net með gefnum eiginleikum í eftirfarandi verkefnum.
75.Tré með átta hnúta, þar af nákvæmlega tvo af stigi 3.
76.Tengt net með átta hnúta, þar af nákvæmlega tvo af stigi 3, sem er ekki tré.
Tilgreindu í eftirfarandi verkefnum allar gerðir sem eiga við um hvert net á myndinni: tré, stjörnutré, stjörnulíkt tré, línulegt net, humrartré, maðktré og/eða skóg.
Notaðu myndina í eftirfarandi verkefnum til að teikna þrjú möguleg spannandi tré sem passa við lýsinguna.
79.Þrjú spannandi tré nets A sem innihalda báða leggina be og de.
80.Þrjú spannandi tré nets K sem innihalda leggina mn og oq en ekki no.
Notaðu reiknirit Kruskals í eftirfarandi verkefnum til að finna léttasta spannandi tré gefins nets. Teiknaðu það og reiknaðu vægi þess.
