12. kafli
12. kafli
Þitt verkefni
12.1
Í neti eru hlutir táknaðir með punktum og tengsl þeirra með línum. Punktarnir eru hnútar. Hnútarnir eru
p
,
q
,
r
,
s
, og
t
. Strikin sem tengja hnútana kallast leggir. Leggirnir eru
pq
,
pr
,
pt
,
qr
,
qs
,
qt
,
rs
, og
st
.
Hnútarnir eru
p
,
q
,
r
,
s
, og
t
. Leggirnir eru
pq
,
pr
,
pt
,
qr
,
qs
,
qt
,
rs
, og
st
.
12.2
Aðlægir hnútar eiga sameiginlegan legg. Hnútar sem eru ekki aðlægir eiga engan sameiginlegan legg. Hnútarnir
p
og
s
eiga engan sameiginlegan legg og eru því ekki aðlægir. Á sama hátt eiga hnútarnir
r
og
t
engan sameiginlegan legg og eru því ekki aðlægir.
Pörin sem eru ekki aðlæg eru
p
og
s
, og
r
og
t
.
12.3
Gráða hnúts er fjöldi leggja sem tengjast honum. Hnúturinn
q
tengist fjórum leggjum. Hugsaðu þér að þú standir á götuhorni og teljir göturnar sem liggja frá horninu.
Hnútur
q
12.4
Teiknaðu hnút fyrir hvert svæði og merktu hann með upphafsstaf svæðisins: N fyrir North Shore, L fyrir Leeward Coast, C fyrir Central, S fyrir South og W fyrir Windward Coast. Tengdu með leggjum svæði sem eiga sameiginleg landamæri. North Shore á landamæri að Leeward Coast, Central og Windward Coast og því eru leggir dregnir frá N til L, C og W.
Leeward Coast á landamæri að North Shore og Central. Leggurinn milli N og L er þegar til og því þarf aðeins að bæta við leggnum milli L og C.
Central á landamæri að hinum svæðunum fjórum. Bættu við leggjum til W og S.
Windward Coast á landamæri að North Shore, Central og South. Leggirnir til N og C eru þegar til og því er leggnum til S bætt við.
South á landamæri að Central og Windward Coast. Báðir leggirnir eru þegar til og netið er fullgert.
Farðu aftur yfir teikninguna og kortið. Teldu gráðu hnútanna og berðu hana saman við gráðu hvers svæðis á kortinu.
12.5
Hnútarnir tákna pókerspilara. Leggur milli tveggja hnúta sýnir að spilararnir kepptu við sama borð. Net hentar vel því spilarar frá sama borði mætast ekki aftur og enginn getur keppt við sjálfan sig; því þarf enga lykkju.
12.6
Vísindamenn telja samfélög með fleiri tengingar þolnari gegn bilunum því þau hafa fleiri valkosti. Net slíks samfélags hefur hærri gráðusummu.
| Gráða | Net | ||
|---|---|---|---|
| Hnútur | C | D | E |
| 3 | 3 | 5 | |
| 3 | 1 | 3 | |
| 2 | 1 | 5 | |
| d | 3 | 1 | 1 |
| e | 3 | 4 | 5 |
| 2 | 2 | 4 | |
| g | 2 | 2 | 4 |
| h | 2 | 1 | 4 |
| i | 3 | 3 | 3 |
| Summa | 23 | 18 | 34 |
Net E hefur hæstu gráðuna. Gráðusumma hnúta þess er 34.
Net
E
, 34
Vísindamenn telja samfélög með fleiri tengingar þolnari gegn bilunum því þau hafa fleiri valkosti. Net slíks samfélags hefur hærri gráðusummu.
| Gráða | Net | ||
|---|---|---|---|
| Hnútur | C | D | E |
| 3 | 3 | 5 | |
| 3 | 1 | 3 | |
| 2 | 1 | 5 | |
| d | 3 | 1 | 1 |
| e | 3 | 4 | 5 |
| 2 | 2 | 4 | |
| g | 2 | 2 | 4 |
| h | 2 | 1 | 4 |
| i | 3 | 3 | 3 |
| Summa | 23 | 18 | 34 |
Net D hefur lægstu gráðuna. Gráðusumma hnúta þess er 18.
Net
D
, 18
Vísindamenn telja samfélög með fleiri tengingar þolnari gegn bilunum því þau hafa fleiri valkosti. Net slíks samfélags hefur hærri gráðusummu.
hærri
12.7
Fjöldi leggja er helmingur gráðusummunnar. Ef gráðusumman er 6 eru leggirnir 3.
3
Möguleg net með 3 leggi og gráðusummuna 6.
eða
Svör geta verið breytileg. Tvö möguleg net eru sýnd.
Net 1:
Net 2:
12.8
Hnútarnir eru 500. Hver einstaklingur þarf að hitta 499 ókunnuga og því tengjast 499 leggir hverjum hnút. Þar sem 500 hnútar hafa gráðuna 499 er gráðusumman 500(499) = 249.500.
Samkvæmt setningunni um gráðusummu er fjöldi leggja = gráðusumma/2 = 249.500/2 = 124.750 kynningar.
124.750 kynningar
12.9
12.10
Rás er röð tengdra leggja sem byrjar og endar í sama hnút en endurtekur annars engan hnút. Rásir sem birtast sem undirnet í stærra neti kallast rásaundirnet og eru nefndar með hnútunum í röð. Gagnlegt er að byrja á stafnum sem kemur fyrst í stafrófinu. Heitið ræðst af fjölda leggja: þríhyrningur hefur þrjár hliðar, ferhyrningur fjórar og fimmhyrningur fimm.
| Þríhyrningur: (a, b, e) | Annað mögulegt svar fyrir þríhyrning: (a, d, e) |
| Ferhyrningur: (a, b, e, d) | Annað mögulegt svar fyrir ferhyrning: (b, c, d, e) |
| Fimmhyrningur: (a, b, c, d, e) |
Þríhyrningur: (
a
,
b
,
e
eða
a
,
d
,
e
)
Ferhyrningur: (
b
,
c
,
d
,
e
eða
a
,
b
,
e
,
d
)
Fimmhyrningur: (
a
,
b
,
c
,
d
,
e
)
12.11
Rás er röð tengdra leggja sem byrjar og endar í sama hnút en endurtekur annars engan hnút. Sem undirnet í stærra neti kallast hún rásaundirnet og er nefnd með hnútunum í röð, helst frá stafnum sem kemur fyrst í stafrófinu. Heitið ræðst af fjölda leggja.
Fimmhyrningur hefur fimm hliðar. Ef hnútarnir eru nefndir með upphafsstöfum einstaklinga er fimmhyrningsrásin (B, D, C, E, F).
Annað mögulegt svar: Einnig má fara rásina í hina áttina.
(B, F, E, C, D). Líklegra er að svörin samsvari lausnunum ef næsti hnútur er valinn eftir stafrófsröð.
(
B
,
D
,
C
,
E
,
F
)
12.12
Finna þarf þriðja stak í 13. röð, en 13. röð Pascals-þríhyrningsins er ekki sýnd og því þarf að mynda hana. Ekki þarf alla röðina; hvert nýtt stak er summa stakanna á „öxlum“ þess.
| 10. röð | 1 | 10 | 45 | 120 | 210 | … | ||||||||
| 11. röð | 1 | 11 | 55 | 165 | 330 | … | ||||||||
| 12. röð | 1 | 12 | 66 | 220 | 495 | … | ||||||||
| 13. röð | 1 | 13 | 78 | 286 | 781 | … | ||||||||
| 0 | 1 | 2 | 3 |
Þriðja stak í 13. röð er 286.
286
12.13
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
Net C1 hefur 6 leggi en net C2 hefur 8.
Net C1 hefur 4 hnúta en net C2 hefur 5.
Net C1 hefur engan hnút af gráðu 4 en net C2 hefur einn.
Netin hafa ekki sömu rásir. Net C2 hefur til dæmis fimmhyrningsrás en C1 ekki.
Net
C
1
hefur 6 leggi en net
C
2
hefur 8.
Net
C
1
hefur 4 hnúta en net
C
2
hefur 5.
Net
C
1
hefur engan hnút af gráðu 4 en net
C
2
hefur einn hnút af gráðu 4.
Netin hafa ekki sömu rásir. Til dæmis hefur net
C
2
fimmhyrningsrás en net
C
1
ekki.
12.14
Svör geta verið breytileg.
12.15
Svör geta verið breytileg. Fjórar einsmótanir eru mögulegar:
12.16
Gættu þess að gera ekki sömu villu og Javier. Hann auðkenndi skurðpunkt sem er ekki hnútur. Ekkert rásaundirnet er í neti E.
Maubi hefur rangt fyrir sér því rekja má net E frá hnút a aftur til a. Net E er ferhyrningur, fjögurra hliða rásin (a, b, c, d). Net T er einnig fjögurra hliða rásin (p, q, r, s).
Bæði net hafa 4 hnúta, 4 leggi og engin rásaundirnet. Allir hnútar hafa gráðu 2.
Með því að sveigja hnút d um c má umbreyta neti E í myndræna samsvörun nets T.
Caden hefur rétt fyrir sér því net
E
mætti greiða úr þannig að
d
væri vinstra megin við
c
og leggirnir
bc
og
ad
skerist ekki lengur. Maubi hefur rangt fyrir sér því (
a
,
b
,
c
,
d
) er ferhyrningur í neti
E
. Javier hefur rangt fyrir sér því auðkenndi hluti netsins hefur ekki 3 hnúta og er ekki þríhyrningur.
12.17
Ein leið til að finna fyllinet er að teikna fullnet með sama hnútafjölda og fjarlægja alla leggi sem voru í upprunalega netinu.
Hnútur A hefur gráðu 0.
Hinir hnútarnir tengjast í línu, C–E–B–D. Hver þeirra hefur gráðu 2.
Leggirnir eru BD, CE og EB.
12.18
Vitað er að gráðurnar verða 0.
Ein leið til að finna fyllinet er að teikna fullnet með sama hnútafjölda og fjarlægja alla leggi upprunalega netsins. Þar sem upprunalega netið er fullnet hefur fyllinetið enga leggi.
Gráðurnar eru 0. Engir aðlægir hnútar eru í neti
N
því allir hnútar eru aðlægir í neti
M
.
12.19
b
a) Ef farið er frá B til V er komið í Brooklyn og leiðin endar þar.
b) Þessi ganga fer nákvæmlega einu sinni yfir allar brýrnar.
c) Ef farið er frá C til V er komið í Brooklyn og leiðin endar þar.
d) Ef farið er frá G til V er komið í Brooklyn og leiðin endar þar.
Aðeins
V
→
C
→
B
→
G
→
C
er ganga.
12.20
Athugaðu hvort hnútarnir séu samliggjandi til að staðfesta að þetta sé ganga.
Hnútarnir eru samliggjandi og því er þetta ganga.
Slóð endurtekur engan legg.
Vegur endurtekur engan hnút.
Þar sem hvorki leggir né hnútar eru endurteknir er þetta ganga, vegur og slóð.
ganga, vegur og slóð
Athugaðu hvort hnútarnir séu samliggjandi til að staðfesta að þetta sé ganga.
Hnútarnir eru samliggjandi og því er þetta ganga.
Slóð endurtekur enga leggi. Teiknaðu netið og rekðu síðan leiðina með öðrum lit. Þá sést að enginn leggur er endurtekinn og þetta er slóð.
Vegur endurtekur enga hnúta. Hnúturinn n er notaður tvisvar og því er þetta ekki vegur. Þetta er ganga og slóð en ekki vegur.
ganga og slóð en ekki vegur
Síðustu hnútarnir tveir,
p
og
q,
eru ekki aðlægir. Allir hnútar göngu verða að vera samliggjandi. Þetta er ekki ganga og því hvorki slóð né vegur.
ekkert þessara
12.21
Göngur sem fara tvisvar um sama legg eru ekki lokaðar slóðir. Til að fljúga frá Palm Beach til annarrar borgar þarf að taka flugið frá PBI til TPA og á bakaleið frá TPA til PBI. Sérhver ferð sem byrjar og endar á PBI fer því tvisvar um sama legg og er ekki lokuð slóð.
Til að fljúga frá Palm Beach til annarrar borgar þarf að taka flugið frá PBI til TPA og á bakaleið frá TPA til PBI. Sérhver ferð sem byrjar og endar á PBI fer því tvisvar um sama legg og er ekki lokuð slóð.
Göngur sem fara tvisvar um sama legg eru ekki lokaðar slóðir. Til að byrja og enda á PBI þarf að nota legginn milli TPA og PBI tvisvar. Gráða PBI er 2. Lokuð slóð getur ekki byrjað í slíkum hnút í þessari ferð.
Gráða PBI er 1 og því tengir aðeins einn leggur PBI við aðra hluta netsins.
12.22
Já, netið er flatt. Flatt net má teikna á flöt þannig að engir leggir skerist og hér skerast engir leggir. Litunartala flats nets er fjórir eða lægri.
Já. Litunartalan er 4 eða lægri.
Netið hefur þríhyrningsklíkur. Litunartala nets er að minnsta kosti fjöldi hnúta í stærstu klíku þess og því að minnsta kosti 3.
3
Þar sem netið er flatt er litunartalan í mesta lagi 4. Stærsta klíkan er þríhyrningur og því er hún að minnsta kosti 3. Litunartalan er því annaðhvort 3 eða 4.
3 eða 4
Net 1 og 3 eru gild. Net 2 er ógilt því tveir aðlægir hnútar hafa sama lit. Net 3 er gilt þótt þar séu notaðir fleiri litir en þörf er á.
Net 1 og 3
Svör geta verið breytileg. Hér er dæmi um 3-litun:
12.23
Þar sem netið er flatt er litunartalan í mesta lagi 4 og þar sem stærsta klíkan er þríhyrningur er hún að minnsta kosti 3. Hægt er að lita netið með 3 litum og því er litunartalan 3.
Litunartalan er 3. Hér er 3-litun netsins:
12.24
Net er samhangandi ef það hefur aðeins einn þátt. Netin G, H og I eru samhangandi og hafa því hvert einn þátt með hnútunum {a, b, c, d}.
Net er ósamhangandi ef það hefur fleiri en einn þátt. Net F hefur tvo þætti: {a, c, d} og {b}. Net J hefur tvo þætti: {a, d} og {b, c}. Net K hefur þrjá þætti: {a}, {b, d} og {c}.
Net
G
,
H
, og
I
eru samhangandi og hafa því hvert einn þátt með hnútunum {
a
,
b
,
c
,
d
}. Graph
F
is disconnected with two components, {
a
,
c
,
d
} and {
b
}. Graph
J
is disconnected with two components, {
a
,
d
} and {
b
,
c
}. Graph
K
is disconnected with three components, {
a
}, {
b
,
d
}, and {
c
}.
12.25
Net er samhangandi ef vegur tengir hvert par hnúta. Hvert par hér tengdist með vegi sem var í mesta lagi sex leggir og því er netið samhangandi.
Hvert par hnúta tengdist með vegi sem var í mesta lagi 6 leggir og því er netið samhangandi.
12.26
Fjölnet hverfisins er sýnt:
Þáttur nets er undirnet þar sem vegur liggur milli hvers hnúta pars en enginn leggur tengir hnút í undirnetinu við hnút utan þess. Net er samhangandi ef það hefur aðeins einn þátt. Hér tengir einnig vegur hvert par hnúta.
Já, netið er samhangandi. Það hefur aðeins einn þátt.
Fjórir hornhnútar hafa gráðu 2 en hinir tólf gráðu 4.
Öll gráðugildi hnúta í Euler-neti eru slétt. Hér hafa allir hnútar gráðu 2 eða 4 og netið er því Euler-net.
Já
Já, Euler-net hefur Euler-rás og því er þetta mögulegt.
12.27
Í Euler-rás er byrjað í einum hnút, farið nákvæmlega einu sinni um alla leggi og endað í upphafshnútnum. Þetta er ómögulegt í neti X því það er ósamhangandi.
Net
X
hefur enga Euler-rás því það er ósamhangandi.
Í Euler-rás er byrjað í einum hnút, farið nákvæmlega einu sinni um alla leggi og endað í upphafshnútnum. Euler-rásin í neti Y er
a
→
b
→
g
→
d
→
f
→
c
→
g
→
e
→
a
.
a
→
b
→
g
→
d
→
f
→
c
→
g
→
e
→
a
12.28
Bæta á við sem fæstum leggjum og aðeins má tvítaka fyrirliggjandi leggi. Skilvirkast er að Euler-væða netið með því að tvítaka
a-d
.
12.29
Teiknaðu netið lauslega og rekðu síðan leggi þess með öðrum lit. Þar sem farið er nákvæmlega einu sinni um alla leggi er þetta Euler-rás.
Já.
Teiknaðu netið lauslega og rekðu síðan leggi þess með öðrum lit. Ekki er farið nákvæmlega einu sinni um alla leggi og þetta er því ekki Euler-rás. Leggirnir sem vantar eru
cd
og
de
.
Nei. Ekki er farið um alla leggi.
Teiknaðu netið lauslega og rekðu síðan leggi þess með öðrum lit. Ekki er farið nákvæmlega einu sinni um alla leggi og þetta er því ekki Euler-rás. Röðin er raunar ómöguleg því hnútarnir
b
og
e
eru ekki aðlægir.
Nei. Þetta er ekki ganga því hnútarnir
b
og
e
eru ekki aðlægir.
12.30
Í fullneti með þrjá eða fleiri hnúta mynda sérhverjir þrír hnútar þríhyrningsrás. Leggur í rás getur hvorki verið brú né staðbundin brú. Því eru engar brýr eða staðbundnar brýr í fullneti.
12.31
Skref 1: Ef oddahnútarnir eru tveir skaltu byrja í öðrum og enda í hinum.
Oddahnútarnir eru m og s. Settu m í eyðuna.
m
Skref 1: Ef oddahnútarnir eru tveir skaltu byrja í öðrum og enda í hinum.
Þú byrjaðir í s.
Skref 2: Fjarlægðu legg frá hnútinum til aðlægs hnúts sem er ekki brú, nema ekkert annað sé hægt, og skráðu legginn. Endurtaktu þar til allir leggir eru fjarlægðir.
Þú fjarlægðir sq og ert nú í q. Leggirnir frá q eru qr, qt og qn. Settu qn og qt í fyrstu eyðurnar í hvaða röð sem er. Ekki má velja qn því hann er brú. Skrifaðu qn í þriðju eyðuna og „brú“ í þá síðustu.
qn, qt; qn
brú
Enn er unnið með hægri helming myndarinnar. Fjarlægja þarf leggina sem þar eru eftir. Teiknaðu myndina og litaðu leggina um leið og þeir eru fjarlægðir.
Hingað til hafa sq og qr verið fjarlægðir.
Nú má fara hringinn um hægri helming netsins. Gerðu allt sem unnt er áður en farið er yfir brú.
sq, qr, rs, st, tq
Nú er hægt að fara yfir brúna.
nq
rs, st, tq, qn
Nú er hægri helmingur myndarinnar fullunninn. Fjarlægja þarf leggina í vinstri helmingnum. Teiknaðu myndina og litaðu leggina um leið og þeir eru fjarlægðir.
Það sem þegar hefur verið gert: sq, qr, rs, st, tq, nq
Þú ert í hnút n.
Nú eru þrír valkostir: no, nm eða np.
nm, np
Nú er hægri helmingur myndarinnar fullunninn. Fjarlægja þarf leggina í vinstri helmingnum. Teiknaðu myndina og litaðu leggina um leið og þeir eru fjarlægðir.
Það sem þegar hefur verið gert: sq, qr, rs, st, tq, nq, no
Eini leggurinn frá o sem hefur verið notaður er om.
Héðan má fara um þríhyrninginn til n og p í hvora áttina sem er og enda aftur í m.
om, mp, pn, nm.
Annað mögulegt svar:
om, mn, np, pm
om, mp, pn, nm
Nú er hægri helmingur myndarinnar fullunninn. Fjarlægja þarf leggina í vinstri helmingnum. Teiknaðu myndina og litaðu leggina um leið og þeir eru fjarlægðir.
Það sem þegar hefur verið gert: sq, qr, rs, st, tq, nq, no
Eini leggurinn frá o sem hefur verið notaður er om.
Héðan má fara um þríhyrninginn til n og p í hvora áttina sem er og enda aftur í m.
om, mp, pn, nm.
Annað mögulegt svar:
om, mn, np, pm
Skref 3: Skrifaðu Euler-slóðina með röð hnúta og leggja sem fundust.
s → q → r → s → t → q → n → o → m → p → n → m
Önnur svör eru möguleg.
s
→
q
→
r
→
s
→
t
→
q
→
n
→
o
→
m
→
p
→
n
→
m
12.32
Skref 1: Ef oddahnútarnir eru tveir skaltu byrja í öðrum og enda í hinum.
Hnútarnir u og v eru oddahnútar og því verður að byrja í öðrum og enda í hinum. Ekki skiptir máli hvor er upphafshnútur.
Skref 2: Fjarlægðu legg frá hnútinum til aðlægs hnúts sem er ekki brú, nema ekkert annað sé hægt, og skráðu legginn. Endurtaktu þar til allir leggir eru fjarlægðir.
Skref 3: Skrifaðu Euler-slóðina með röð hnúta og leggja sem fundust.
v → w → x → u → z → y → w → u
Önnur tilbrigði eru möguleg.
Netið hefur Euler-slóðir. Þær verða að byrja og enda í hnútunum
u
og
v
. Dæmi er
v
→
w
→
x
→
u
→
z
→
y
→
w
→
u
12.33
Euler-rásir fara nákvæmlega einu sinni um hvern legg en Hamilton-rásir nákvæmlega einu sinni um hvern hnút. Þessi rás gerir hvort tveggja og er því bæði Euler-rás og Hamilton-rás.
bæði
12.34
𝑛
!
=
6
!
=
6
⋅
5
⋅
4
⋅
3
⋅
2
⋅
1
=
7
2
0
n
!
=
6
!
=
6
⋅
5
⋅
4
⋅
3
⋅
2
⋅
1
=
720
og
(
𝑛
−
1
)
!
=
(
6
−
1
)
!
=
5
!
=
5
⋅
4
⋅
3
⋅
2
⋅
1
=
1
2
0
(
n
−
1
)
!
=
(
6
−
1
)
!
=
5
!
=
5
⋅
4
⋅
3
⋅
2
⋅
1
=
120
12.35
Fjöldi umraðana n ólíkra hluta er n!.
Stafirnir eru 5 og því eru 5! umraðanir.
5
!
=
5
⋅
4
⋅
3
⋅
2
⋅
1
=
1
2
0
5
!
=
5
⋅
4
⋅
3
⋅
2
⋅
1
=
120
12.36
Fjöldi ólíkra Hamilton-rása í fullneti með n hnúta er (n − 1)!.
Netið hefur sex hnúta og því (6 − 1)! ólíkar Hamilton-rásir.
120
12.37
Leggðu saman vægi einstakra leggja.
| mo | op | pn | nq | qm | Summa |
| 3 | 5 | 5 | 8 | 5 | 26 |
Heildarvægi Hamilton-rásarinnar er 26.
26
12.38
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja og þarf ekki að byrja og enda í sama hnút.
Röðin er ómöguleg því c og d eru ekki aðlægir.
Nei
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja og þarf ekki að byrja og enda í sama hnút.
Röðin er ekki Hamilton-vegur því hnútur b kemur fyrir inni í veginum og er jafnframt upphafs- og endahnútur.
Nei
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja og þarf ekki að byrja og enda í sama hnút.
Röðin er Hamilton-vegur.
Já
12.39
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja og þarf ekki að byrja og enda í sama hnút.
Þar sem byrjað er í C verður A að koma næst. Hingað til er röðin:
Ef næst væri farið til F væri ekki hægt að komast til B án þess að heimsækja F tvisvar. Því þarf að fara frá A til B og síðan frá B til F.
→
Þú þarft að enda í E og heimsækir því D næst.
→ → D
Að lokum er endað í E.
→ →
C
→
A
→
B
→
F
→
D
→
E
12.40
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja og þarf ekki að byrja og enda í sama hnút.
Til að finna brú skaltu forðast brýr þar til nauðsynlegt er að fara yfir þær. Netið hefur brúna nq og því skal halda sig sem lengst frá henni.
Þar sem byrjað er í p skaltu forðast brúna og velja m. Hingað til er röðin:
p → m
Þar sem brúin er enn forðuð er næst farið til o.
p → m → o
Nú þarf að fara yfir brúna.
p → m → o → n → q
Enda þarf í r og því er farið um hnútana þannig að þar sé endað.
p → m → o → n → q → t → s → r
p
→
m
→
o
→
n
→
q
→
t
→
s
→
r
Ekki er hægt að finna Hamilton-veg sem byrjar í
m
og endar í
p
því þeir eru sömu megin við brúna
nq
.
enginn
Ekki er hægt að finna Hamilton-veg sem byrjar í
o
og endar í
q
því röðin endar við annan enda brúarinnar
nq
. Hamilton-vegurinn þyrfti að fara um fjögurra rása undirnetið vinstra megin, yfir brúna (
nq
) og síðan um fjögurra rása undirnetið hægra megin. Hamilton-vegur getur hvorki byrjað né endað í hnútum brúarinnar. Hann byrjar í hnút sem er aðlægur brúnni öðrum megin og endar í aðlægum hnút hinum megin.
enginn
12.41
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja. Euler-slóð fer nákvæmlega einu sinni um hvern legg.
Hann þarf ekki að byrja og enda í sama hnút.
Þetta er Hamilton-vegur en ekki Euler-slóð því ekki er farið um alla leggi; bc og ae eru ekki notaðir.
Hamilton-vegur
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja. Euler-slóð fer nákvæmlega einu sinni um hvern legg.
Þetta er Euler-slóð því farið er nákvæmlega einu sinni um hvern legg. Hún er ekki Hamilton-vegur því hnútar eru heimsóttir oftar en einu sinni.
Euler-slóð
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja. Euler-slóð fer nákvæmlega einu sinni um hvern legg.
Þetta er hvorugt. Hvorki er farið um alla leggi né allir hnútar heimsóttir.
hvorugt
12.42
Tæmandi reiknirit telur upp allar mögulegar lausnir og ber þær saman til að finna þá bestu. Þetta dæmi notar tæmandi reiknirit.
Gráðugt reiknirit velur besta kostinn við hverja kvísl leiðarinnar, heldur áfram að velja besta kostinn á hverju stigi og tengir valin að lokum í heildarlausn. Það getur misst af bestu lausninni en finnur hana stundum.
Tæmandi reiknirit tryggir bestu lausnina en getur tekið langan tíma.
tæmandi reiknirit
12.43
12.44
Til að tryggja að stysta leiðin finnist þarf að reikna lengd allra mögulegra leiða.
Hnútarnir eru 4 og því eru (4 − 1)! = 3! = 3·2·1 = 6 mögulegar rásir, en helmingur þeirra er öfug röð hinna.
T = Travis, B = Beal, E = Edwards, L = Los Angeles
| Leið | EL | LT | Summa | ||
| Fjarlægð | 84 | 410 | 106 | 396 | 996 |
| Leið | TE | LT | Summa | ||
| Fjarlægð | 370 | 410 | 439 | 396 | 1,615 |
| Leið | LE | ET | Summa | ||
| Fjarlægð | 84 | 439 | 106 | 370 | 999 |
Hinar þrjár leiðirnar eru öfug röð þessara þriggja rása.
Stysta leiðin liggur frá Travis til Beal, þaðan til Edwards og Los Angeles Air Force Base og loks aftur til Travis.
Yfirmaðurinn ætti að fara frá Travis Air Force Base til Beal Air Force Base, þaðan til Edwards Air Force Base og Los Angeles Air Force Base og aftur til Travis.
12.45
D
→
B
→
E
→
A
→
C
→
F
→
D
; 550 mínútur, eða 9 klukkustundir og 10 mínútur.
12.46
Stjörnu- og trjágrannfræðin eru tré; þær eru samhangandi og hafa engin rásaundirnet.
Hringgrannfræðin er ekki tré því hún myndar rás.
Möskvagrannfræðin er ekki tré því hún hefur rásaundirnet.
Stjörnu- og trjágrannfræðin eru tré. Hring- og möskvagrannfræðin eru ekki tré því þær innihalda rásir.
12.47
Stjörnuuppsetningin er stjörnutré.
Stjörnutré hefur nákvæmlega einn hnút af gráðu yfir 1, sem kallast rót, og allir hinir hnútarnir eru aðlægir honum.
stjörnuuppsetning
Trjáuppsetningin er maðktré.
Maðktré hefur miðlægan veg með hnútum af hvaða gráðu sem er. Hver hnútur utan miðvegarins er aðlægur hnút á honum og hefur gráðu 1.
trjáuppsetning
Engin uppsetningin er vegnet. Vegnet, eða línulegt net, er tré með nákvæmlega tvo hnúta af gráðu 1 og allir aðrir hnútar mynda einn veg milli þeirra; því má teikna það sem beina línu.
enginn
12.48
Ef leggurinn ji er fjarlægður skiptist tréð í tvo þætti og er því ekki lengur tré.
Annar þátturinn: g, h, i, j
Hinn þátturinn: k, l, m
Hnútarnir
k, l
, og
m
eru í öðrum þættinum og hnútarnir
g, h, i
, og
j
í hinum.
Fjöldi leggja í tré með n hnúta er n − 1.
Netið hefur 6 hnúta og 5 leggi. Það samræmist formúlunni fyrir tré: ef n = 6 er n − 1 = 5.
Hnútarnir eru 6 og leggirnir 5, sem staðfestir að net
I
er tré því leggirnir eru einum færri en hnútarnir.
Ef leggnum
cf,
er bætt við myndast ferhyrningur (
b, c, f, e
).
ferhyrningur
12.49
a
Til að N sé spanntré nets H
1
verður það að vera undirnet H. Það getur ekki verið undirnet ef leggurinn
sq
er ekki í neti H.
Satt
b
Spanntré má ekki innihalda rás. Þetta net inniheldur þríhyrningsrás (
r, s, t
).
Ósatt
a
Allir hnútar eru með, netið er samhangandi og engar rásir eru í því. Engir hnútar eru heldur aðlægir sem voru ekki aðlægir í H.
Satt
a
Netið er ósamhangandi. Spanntré er samhangandi net.
Satt
12.50
Svör geta verið breytileg. Hér eru þrjú möguleg spanntré nets
J
:
12.51
Mundu að fjöldi leggja í tré með n hnúta er n − 1.
Net V hefur 9 hnúta og 11 leggi. Spanntré þess hefur 8 leggi og því þarf að fjarlægja 3 leggi úr V.
Í dæminu voru ac, cf og be fjarlægðir.
Mynda á spanntré með því að fjarlægja þrjá leggi. Rjúfa þarf rásirnar þrjár því spanntré má ekki hafa rásir.
Leggirnir þrír verða að innihalda einn legg úr lista A og par úr lista B.
Listi A: be, eh, hi, gi, bg
Listi B: ac og ad, ac og af, ac og cd, ac og cf, ad og af, ad og cd, ad og cf, af og cd, af og cf eða cd og cf
Leggirnir þrír verða að innihalda einn legg úr lista A og eitt par úr lista B.
Listi A:
be
,
eh
,
hi
,
gi
,
bg
Listi B:
ac
og
ad
,
ac
og
af
,
ac
og
cd
,
ac
og
cf
,
ad
og
af
,
ad
og
cd
,
ad
og
cf
,
af
og
cd
,
af
og
cf
, eða
cd
og
cf
.
12.52
Raðaðu vægjunum: 24, 37, 45, 49, 68, 68, 89
Skref 1: Veldu legginn með minnsta vægið af öllum leggjum.
VY hefur vægið 24.
Skref 2: Veldu annan legg með minnsta vægi af þeim sem eftir eru. Hann þarf ekki að tengjast fyrsta leggnum.
UW hefur vægið 37.
Skref 3: Veldu annan legg með minnsta vægi af þeim sem eftir eru, en engan sem myndar rás í undirnetinu.
WX hefur vægið 45.
Skref 4: Endurtaktu skref 3 þar til allir hnútar upprunalega netsins eru með og spanntré hefur myndast.
UX hefur vægið 48. UX myndar rás og er því ekki notaður.
Endurtaktu skref 3: Veldu annan legg með minnsta vægi af þeim sem eftir eru, en engan sem myndar rás í undirnetinu.
Tveir leggir hafa vægið 68. Setja má annan hvorn í netið: VW eða YX, en ekki báða.
Verkinu er lokið. Nú eru fimm hnútar í netinu.
Leggðu saman vægin: 24 + 37 + 45 + 68 = 174.
Vægi spanntrésins er 174.
Tvö lágmarksspanntré eru möguleg og hvort hefur heildarvægið 174:
Athugaðu skilning þinn
a
Satt
b
Hugsaðu um net sem táknar kort þar sem héruð eru hnútar og sameiginleg landamæri leggir. Eyja án sameiginlegra landamæra væri einangraður hnútur af gráðu 0.
Ósatt
a
Satt
b
Fjölnet getur haft lykkjur eða tvöfalda leggi og því getur net með þrjá hnúta haft fleiri en þrjá leggi.
Ósatt
b
Hnúturinn gæti verið aðlægur en þarf ekki að vera það. Hugsaðu um 1, 2 og 3 á reglustiku sem hnúta. Tengdu 1 við 2 og 2 við 3. Þá eru 1 og 2 aðlæg og 2 og 3 aðlæg, en 1 og 3 ekki.
Ósatt
b
Í fullneti er hver hnútur aðlægur öllum hinum. Fjöldi leggja í fullneti með
n
hnúta er summa heiltalnanna frá 1 til
n
− 1. Í dæmi kennslustundarinnar hafði fullnet með 6 hnúta 15 leggi.
Ósatt
a
Rás er röð tengdra leggja sem byrjar og endar í sama hnút en endurtekur annars engan hnút. Allir hnútar hennar hafa gráðu 2.
Satt
b
Sum net hafa enga leggi.
Ósatt
a
Upphafshnúturinn skiptir ekki máli en skrá verður hnútana í röð. Auðveldara er að halda utan um röðina ef byrjað er á stafnum sem kemur fyrst í stafrófinu.
Satt
b
Upphafshnúturinn skiptir ekki máli en skrá verður hnútana í röð. Rásirnar fara ekki sömu leið frá
b
til
d
.
Ósatt
a
Satt
Gráðusumman er alltaf tvöfaldur fjöldi leggja og verður því að vera slétt tala, en 13 er oddatala.
Ef n er fjöldi hnúta í fullneti tengist hver hnútur n − 1 öðrum hnútum og hefur því gráðu n − 1.
Heildargráðusumma netsins er því n(n − 1).
Samkvæmt setningunni um gráðusummu er fjöldi leggja = gráðusumma/2 = n(n − 1)/2.
Síðasta stæðan er jafngild því sem nemandinn sagði: n/2 · (n − 1).
Já. Ef
n
er fjöldi hnúta í fullneti er fjöldi leggja
𝑛
(
𝑛
−
1
)
2
=
𝑛
2
(
𝑛
−
1
)
n
(
n
−
1
)
2
=
n
2
(
n
−
1
)
sem er helmingur hnútafjöldans margfaldaður með einum færra en hnútafjöldanum.
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
alltaf satt
Full samsvörun milli hnútanna getur ekki verið til staðar.
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
aldrei satt
Netin gætu verið einsmóta en þurfa ekki að vera það. Bæði gætu haft gráðusummuna 6; annað þrjá hnúta af gráðu 2 en hitt tvo hnúta af gráðu 3.
stundum satt
Full samsvörun milli leggja getur ekki verið til staðar.
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
aldrei satt
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
alltaf satt
Oft eru fleiri en ein einsmótun milli tveggja einsmóta neta, en ekki alltaf.
stundum satt
Þau gætu verið einsmóta en eru það ekki alltaf. Hér er dæmi þar sem þau eru ekki einsmóta.
Bæði net gætu haft tvo hnúta. Í neti 1 tengir einn leggur hnútana en í neti 2 tveir leggir. Hnútarnir í neti 1 hafa gráðu 1 en í neti 2 gráðu 2 og netin eru því ekki einsmóta.
stundum satt
Þetta stangast á við skilgreiningu einsmótunar.
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
aldrei satt
stundum satt
Samsvörun hnútanna tryggir að gráðusummurnar eru jafnar.
Tvö net eru einsmóta ef annað eftirfarandi skilyrða gildir:
alltaf satt
Ein leið til að finna fyllinet er að teikna fullnet með sama hnútafjölda og fjarlægja alla leggi sem voru í upprunalega netinu.
alltaf satt
Allir vegir eru slóðir en ekki allar slóðir vegir. Sumar slóðir heimsækja sama hnút oftar en einu sinni en vegur endurtekur engan hnút.
stundum satt
Allar slóðir eru göngur. Slóðir nota tengda hnúta, sem er skilyrði göngu.
alltaf satt
Allir vegir eru göngur en ekki allar göngur vegir. Sumar göngur heimsækja sama hnút oftar en einu sinni en vegur endurtekur engan hnút.
stundum satt
Samkvæmt skilgreiningu er lokuð slóð slóð sem byrjar og endar í sama hnút.
alltaf satt
Samkvæmt skilgreiningu er stefnd rás vegur sem byrjar og endar í sama hnút.
alltaf satt
Stefnd rás er samkvæmt skilgreiningu vegur sem byrjar og endar í sama hnút. Lokuð slóð byrjar og endar einnig í sama hnút.
Stefnd rás byrjar ekki endilega og endar í sama hnút og því eru ekki allar stefndar rásir lokaðar slóðir.
stundum satt
Samkvæmt skilgreiningu er stefnd rás vegur sem byrjar og endar í sama hnút.
Lokuð slóð er slóð sem byrjar og endar í sama hnút. Stefnd rás er því lokuð slóð.
alltaf satt
Lita má net með fleiri litum en lágmarksfjöldanum. Nota mætti til dæmis annan lit fyrir hvern hnút ferhyrningsrásar; netið hefði litunartöluna 2 en notaði 4 liti.
stundum satt
Þetta er skilgreining litunartölu.
alltaf satt
alltaf satt
hefur enga endurtekna leggi
er lokuð
hefur enga endurtekna hnúta
hefur enga endurtekna leggi
𝑛
n
að minnsta kosti
Þáttur nets er undirnet þar sem vegur tengir hvert par hnúta en enginn leggur tengir hnút í undirnetinu við hnút utan þess. Ósamhangandi net hefur að minnsta kosti tvo þætti.
aldrei satt
Net gæti haft tvo þætti þar sem allir hnútar hafa slétta gráðu. Það gæti einnig verið einn þáttur með hnúta af sléttri gráðu.
stundum satt
Net bæjarins hafði fjóra hnúta af oddagráðu. Euler-rás krefst þess að allir hnútar hafi slétta gráðu.
aldrei satt
Net gæti haft tvo þætti þar sem allir hnútar hafa slétta gráðu. Ef netið er ósamhangandi getur það ekki haft Euler-rás. Það gæti hins vegar verið einn þáttur með sléttar gráður og haft Euler-rás.
stundum satt
Euler sannaði að allir hnútar nets verða að hafa slétta gráðu til að netið geti haft Euler-rás.
alltaf satt
Samkvæmt skilgreiningu er Euler-rás lokuð slóð sem fer nákvæmlega einu sinni um hvern legg nets.
alltaf satt
Euler-rás heimsækir stundum sama hnút oftar en einu sinni. Hnútur af gráðu 4 er til dæmis heimsóttur tvisvar.
stundum satt
Ekki má bæta leggjum milli hnúta sem voru ekki aðlægir.
aldrei satt
Þetta er rétta aðferðin til að Euler-væða net.
alltaf satt
Fjöldi hnúta af oddagráðu gæti verið oddatala. Ef þeir væru til dæmis þrír væri ekki hægt að bæta við 1,5 legg.
stundum satt
leggur
Fleury-aðferð
lokuð slóð, slóð
þættir
staðbundin brú
brú
hnútur
fullt
Lokuð slóð er slóð sem byrjar og endar í sama hnút og endurtekur engan legg. Hamilton-rás er lokuð slóð því hún byrjar og endar í sama hnút og endurtekur engan legg.
er
Euler-rás fer nákvæmlega einu sinni um hvern legg en Hamilton-rás heimsækir hvern hnút nákvæmlega einu sinni. Hamilton-rás sem fer um hvern legg er einnig Euler-rás. Sumar Hamilton-rásir eru Euler-rásir og sumar Euler-rásir Hamilton-rásir, en ekki allar.
er
Rás byrjar og endar í sama hnút. Lokuð slóð gerir það einnig en endurtekur engan legg. Heitið Hamilton merkir að hnútar eru ekki endurteknir og því eru Hamilton-rás og lokuð Hamilton-slóð jafngild.
er ekki
er
Vægi slóðar fæst með því að leggja saman vægi allra leggja sem farið er um.
er
Vegið net getur verið af hvaða gerð sem er, fullt eða ófullt. Heitið merkir aðeins að tölugildi, yfirleitt tengd raunverulegu viðfangsefni, eru sett á leggina.
er ekki
Fjöldi umraðana
n
ólíkra hluta er
n
!.
er ekki
Rás byrjar og endar í sama hnút. Lokuð slóð gerir það einnig en endurtekur engan legg. Rás getur endurtekið leggi eða ekki.
er ekki
Hamilton-vegur þarf ekki að byrja og enda í sama hnút.
ólíkt
Hamilton-vegur þarf ekki að byrja og enda í sama hnút en hann þarf að heimsækja hvern hnút nákvæmlega einu sinni. Fjöldi skráðra hnúta er því alltaf jafn hnútafjölda netsins.
hið sama og
Vegur sem heimsækir hvern hnút nákvæmlega einu sinni er Hamilton-vegur. Vegur er ganga án endurtekinna hnúta eða leggja en Euler-slóð fer nákvæmlega einu sinni um hvern legg. Aðferðirnar eru því ólíkar enda markmiðin ólík.
ólíkt
Ef net hefur brú byrjar Hamilton-vegur öðrum megin hennar og endar hinum megin. Forðast skal brúna þar til enginn annar kostur er eftir.
ólíkt
b
Þetta er Hamilton-vegur.
Ósatt
b
Netið gæti verið ósamhangandi.
Ósatt
b
Netið gæti haft Hamilton-veg sem byrjar á annarri rásinni í hnút sem er aðlægur
p
og endar í
p.
Hann getur farið um fyrri rásina, yfir í þá síðari við
p
og síðan um síðari rásina.
Ósatt
a
Hamilton-vegur er mögulegur en ekki með upphafs- og endahnút í endum brúarinnar. Ef brú er til staðar þarf að forðast hana þar til hún er eini kosturinn.
Satt
a
Tæmandi reiknirit telur upp allar mögulegar lausnir og ber þær saman til að finna þá bestu. Það getur tekið mikinn tíma þegar valkostir í raunverulegu verkefni eru margir.
Gráðugt reiknirit velur besta kostinn við hverja kvísl og á hverju stigi og tengir valin í heildarlausn. Það getur misst af bestu heildarlausninni en er mun hraðara en tæmandi reiknirit.
Satt
b
Tæmandi reiknirit telur upp allar mögulegar lausnir og ber þær saman. Það getur tekið langan tíma en finnur alltaf bestu lausnina.
Ósatt
b
Tæmandi reiknirit telur upp allar mögulegar lausnir og ber þær saman til að finna þá bestu. Það getur tekið mikinn tíma þegar valkostir í raunverulegu verkefni eru margir.
Næsta nágranna reikniritið velur besta kostinn við hverja kvísl og á hverju stigi og tengir valin í heildarlausn. Það getur misst af bestu heildarlausninni en er mun hraðara en tæmandi reiknirit.
Ósatt
b
Tæmandi reiknirit telur upp allar mögulegar lausnir og ber þær saman til að finna þá bestu. Það getur tekið mikinn tíma þegar valkostir í raunverulegu verkefni eru margir.
Gráðugt reiknirit velur besta kostinn við hverja kvísl og á hverju stigi og tengir valin í heildarlausn. Það getur misst af bestu heildarlausninni en er mun hraðara en tæmandi reiknirit.
Ósatt
a
Tæmandi reiknirit telur upp allar mögulegar vegnar Hamilton-rásir og ber þær saman til að finna rásina með minnsta vægið.
Satt
b
Næsta nágranna reikniritið velur besta kostinn við hverja kvísl og á hverju stigi og tengir valin í heildarlausn. Það getur misst af bestu heildarlausninni en er mun hraðara en tæmandi reiknirit.
Ósatt
b
Farandsölumannsvandinn felst í að finna stystu leið um marga staði og aftur á upphafsstað.
Ósatt
a
Satt
a
Satt
b
Fjöldi ólíkra Hamilton-rása í fullneti með n hnúta er (n − 1)!.
Þar sem helmingur rásanna er öfug röð hinna eru aðeins (n − 1)!/2 ólíkar vegnar rásir.
Ósatt
b
Spanntré hefur engar rásir. Samkvæmt skilgreiningu er það rásalaust.
Ósatt
a
Spanntré hefur engar rásir og því heldur enga þríhyrninga.
Satt
a
Spanntré þarf samkvæmt skilgreiningu að spanna allt netið með því að innihalda hvern hnút þess.
Satt
a
Spanntré eru samhangandi, rásalaus og innihalda alla hnúta nets. Í tré liggur nákvæmlega einn vegur milli sérhverra tveggja hnúta.
Satt
a
Öll tré eru samhangandi.
Satt
b
Reiknirit Kruskals finnur lágmarksspanntré í vegnu neti en ekki öll möguleg spanntré.
Ósatt
b
Í dæmum kennslustundarinnar voru fundin spanntré neta með rásaundirnetum.
Ósatt
a
Reiknirit Kruskals finnur lágmarksspanntré í vegnu neti og nýtist til dæmis við að finna hagkvæmustu leið til að leggja tölvunet.
Satt
a
Reiknirit Kruskals finnur lágmarksspanntré í vegnu neti. Tréð inniheldur alla hnúta upprunalega netsins og leggina með minnstu vægin sem mynda ekki rás.
Satt
a
Sniðleggur er annað heiti á brú. Ef hann er fjarlægður úr spanntré rofnar samhengið. Því má ekki fjarlægja sniðlegg eða brú úr spanntré, sem verður að vera samhangandi.
Satt