1212 Netafræði
Lykilatriði
Lykilatriði
12.1 Grunnhugtök netafræði
- Net og fjölnet tákna hluti með hnútum og tengsl hlutanna með leggjum.
- Stig hnúts er fjöldi leggja sem mætast í honum og getur verið núll.
- Leggur verður að hafa hnút við hvorn enda.
- Fjölnet mega innihalda lykkjur og tvöfalda leggi en einföld net ekki.
12.2 Formgerðir neta
- Summa stiga hnúta í neti er tvöfaldur fjöldi leggja.
- Í fullkomnu neti liggur sérhvert hnútapar saman.
- Hlutanet er hluti af stærra neti.
- Rás er runa tengdra hnúta sem hefst og endar í sama hnúti án þess að heimsækja nokkurn annan hnút oftar en einu sinni.
12.3 Samanburður neta
- Tvö net eru einsmóta ef þau hafa sömu formgerð.
- Þegar net eru fremur lítil má greina einsmótun með sjónskoðun og umbreyta öðru netinu í hitt án þess að rjúfa tengsl eða bæta við nýjum.
- Einsmótun tveggja neta varðveitir aðlægni.
- Ef tvö net hafa ólíkan fjölda hnúta, ólíkan fjölda leggja, ólík hnútastig eða ólíkar gerðir hlutaneta geta þau ekki verið einsmóta.
- Ef nykur tveggja neta eru einsmóta eru netin sjálf það einnig.
12.4 Ferðir um net
- Göngur, slóðir og vegir eru leiðir til að ferðast um net eftir runu tengdra hnúta og leggja.
- Lokaðar göngur, rásir og stefndar rásir eru leiðir til að leggja af stað frá hnúti og snúa aftur í sama hnút.
- Litun flokkar hnúta nets þannig að engir tveir hnútar í sama flokki liggi saman.
- Kort má tákna með sléttunetum sem alltaf má lita með fjórum eða færri litum.
12.5 Euler-rásir
- Tengt net hefur aðeins einn samhengisþátt.
- Setningin um Euler-rásir segir að Euler-rás sé til í sérhverju tengdu neti þar sem allir hnútar hafa slétt stig, en ekki í ótengdu neti eða neti með einn eða fleiri hnúta af oddatölustigi.
- Kínverska póstburðarmannsvandamálið spyr hvernig finna megi stystu lokuðu slóðina sem fer að minnsta kosti einu sinni um hvern legg.
- Ef Euler-rás er til er hún alltaf besta lausn kínverska póstburðarmannsvandamálsins.
- Euler-væðing felst í að afrita leggi nets þannig að nýja fjölnetið hafi Euler-rás.
- Lágmarksfjöldi afritaðra leggja sem þarf til að Euler-væða net er helmingur fjölda hnúta af oddatölustigi eða meiri.
12.6 Euler-slóðir
- Euler-slóð er til þegar net hefur nákvæmlega tvo hnúta af oddatölustigi.
- Þegar brú er fjarlægð úr neti fjölgar samhengisþáttum.
- Brú er aldrei hluti af rás.
- Þegar staðbundin brú er fjarlægð úr neti eykst fjarlægð milli hnúta.
- Leggur sem er hluti af þríhyrningi er aldrei staðbundin brú.
12.7 Hamilton-rásir
- Hamilton-rás er stefnd rás sem heimsækir hvern hnút nákvæmlega einu sinni.
- Sumar Hamilton-rásir eru einnig Euler-rásir en aðrar ekki.
- Hamilton-rásir sem fylgja sömu óstefndu rás í sömu átt teljast sama rás þótt þær hefjist í ólíkum hnútum.
- Fjöldi ólíkra Hamilton-rása í fullkomnu neti með n hnúta er jafnmikill fjölda umraðana n − 1 ólíkra hluta.
- Í vegnu neti fær hver leggur tölugildi sem getur táknað fjarlægð, tíma, kostnað eða aðra stærð.
12.8 Hamilton-vegir
- Hamilton-vegur heimsækir hvern hnút nákvæmlega einu sinni.
- Sumir Hamilton-vegir eru einnig Euler-slóðir en aðrir ekki.
12.9 Farandsölumannsvandinn
- Tæmandi reiknirit finnur alltaf bestu lausnina en getur verið óhentugt, en gráðugt reiknirit er skilvirkt og leiðir yfirleitt ekki til bestu lausnarinnar.
- Hamilton-rás með lægsta vægið er lausn farandsölumannsvandans.
- Tæmandi aðferðin finnur Hamilton-rás með lægsta vægið í fullkomnu neti.
- Aðferð næsta granna er gráðugt reiknirit sem finnur Hamilton-rás með tiltölulega lágt vægi í fullkomnu neti.
12.10 Tré
- Tæmandi reiknirit finnur alltaf bestu lausnina en getur verið óhentugt, en gráðugt reiknirit er skilvirkt og leiðir yfirleitt ekki til bestu lausnarinnar.
- Hamilton-rás með lægsta vægið er lausn farandsölumannsvandans.
- Tæmandi aðferðin finnur Hamilton-rás með lægsta vægið í fullkomnu neti.
- Aðferð næsta granna er gráðugt reiknirit sem finnur Hamilton-rás með tiltölulega lágt vægi í fullkomnu neti.