Sendu inn spurningu

Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.

Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að svara öllum spurningum.

Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki nægileg deili á sér.

Spurningum sem eru ekki á verksviði vefsins er eytt.

Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!

=

Gefnir eru þrír hringir og þrír kassar. Er hægt að tengja hvern hring við hvern kassa með strikum án þess að strikin skerist?

Fullskipað 3,3-tvíhlutanet: Er hægt að teikna það án þess að leggirnir skerist?

Þessi þraut er gjarnan orðuð á þennan hátt: Leggja þarf lagnir frá gasveitu, rafveitu og vatnsveitu í þrjú hús. Er hægt að gera það án þess að nokkurs staðar þurfi ein lögn að liggja yfir aðra?

Þrautin er oft lögð fyrir jafnt börn sem fullorðna, enda prýðilegt dæmi um verkefni af því tagi sem stærðfræðingar leitast við að leysa. Svo vill reyndar til að svarið er vel þekkt meðal stærðfræðinga en það dregur á engan hátt úr gildi þess að fólk spreyti sig á henni.

Ef lesendur hafa ekki þegar gefið sér nokkurn tíma í að skoða dæmið eru þeir eindregið hvattir til að taka fram blað og penna eða hver önnur tól sem þeim detta í hug og reyna að fá tilfinningu fyrir því sjálfir áður en þeir lesa lengra.

Þrautin snertir ákaflega áhugaverða grein stærðfræðinnar er nefnist netafræði (e. graph theory). Net (e. graph) er stærðfræðilegt fyrirbæri sem samanstendur af einhverjum fjölda hnúta (e. vertices) og leggja (e. edges) sem tengja saman einhverja hnútanna, tvo og tvo. Teikna má netin á blað og þá skiptir ekki máli hvernig netið snýr eða hvernig hnútarnir liggja í afstöðu hver til annars, heldur aðeins hvaða hnútar eru tengdir saman með leggjum.

Hér sjást fjórar myndir af sama netinu. Þetta net inniheldur fjóra hnúta og fjóra leggi.

Lagnet (e. planar graph) nefnast net sem hægt er að greypa í sléttuna, ígildi þess að teikna það á blað, án þess að tveir leggir skerist. Því er spurningin hér jafngild því hvort netið á myndinni að ofan (svokallað fullskipað 3,3-tvíhlutanet, oft táknað $K_{3,3}$) sé lagnet - hvort einhver leið finnist til að teikna það svo leggirnir skerist ekki.

Þeir sem reynt hafa við þrautina hafa sjálfsagt lent í ýmsum ógöngum. Þegar allt virðist ganga vel verður skyndilega ljóst að síðasti leggurinn getur ekki annað en skorið einhvern hinna.

Hvernig sem reynt er að teikna leggina virðast þeir alltaf enda á að skerast.

Sannleikurinn er reyndar sá að þetta er ógerlegt! Það má sjá á þennan veg:

Ef við merkjum hnútana vinstra megin og hægra megin með A, B og C annars vegar og X, Y og Z hins vegar verðum við að minnsta kosti að fá einhvern veginn fram leggina sem tengja hnútana A-Y-C-X-B-Z-A og marka því eins konar hring - svokallaða rás. Það má því gera ráð fyrir að þeir hafi þegar verið teiknaðir. Án þess að tapa upplýsingum má dreifa úr hnútunum svo myndin sé greinilegri eins og gert er á hreyfimyndinni hér að neðan.

Hér er hnútunum endurraðað þannig að sjá má hvernig tveir af þremur síðustu leggjunum útiloka að sá allrasíðasti verði teiknaður.

Þegar hingað er komið er ljóst að eftir eru leggirnir A-X, B-Y og C-Z. Fyrir hvern þeirra þarf að velja hvort hann á að teiknast innan eða utan vegarins sem þegar er kominn en aðeins einn leggur getur teiknast hvorum megin! Því er óhjákvæmilegt að leggir netsins skerist einhvers staðar.

Fullskipaða netið með 5 hnúta.

Árið 1930 sýndi pólski stærðfræðingurinn Kazimierz Kuratowski í grein sinni fram á það að öll net sem ekki eru lagnet má smækka og einfalda svo annaðhvort komi út $K_{3,3}$ eða annað net, fullskipaða netið með 5 hnúta, $K_5$, sem sést hér til hliðar. Þessi niðurstaða er nefnd setning Kuratowski.

Ekki er svo erfitt að sjá að unnt er að teikna öll lagnet á flöt kúlu í stað slétts flatar. Ef gert er gat í kúluna fæst út svokallaður hjólflötur (e. torus), eins konar kleinuhringsform. Á slíkum fleti má í raun teikna þessi net með góðu móti, án þess að tveir leggir skerist. Ef gefið er eitthvert net kallast ætt (e. genus) netsins sá fjöldi gata sem gera þarf í kúlu fyrr en teikna má netið á flötinn án þess að leggir skerist. Ætt lagneta er því 0, ætt $K_5$ og $K_{3,3}$ er 1 og svo framvegis.

Áður en höfundur ráfar of langt frá upphafspunkti er rétt að taka saman: Svarið við spurningunni er nei. Þessa teikningu er ekki unnt að framkvæma á venjulegum fleti.

Heimildir og frekara lesefni:

Myndir:

  • EAH.

Útgáfudagur

19.4.2013

Spyrjandi

Ólafur Sigurðsson

Höfundur

B.S. í stærðfræði

Tilvísun

Einar Axel Helgason. „Gefnir eru þrír hringir og þrír kassar. Er hægt að tengja hvern hring við hvern kassa með strikum án þess að strikin skerist?“ Vísindavefurinn, 19. apríl 2013. Sótt 17. júní 2019. http://visindavefur.is/svar.php?id=53461.

Einar Axel Helgason. (2013, 19. apríl). Gefnir eru þrír hringir og þrír kassar. Er hægt að tengja hvern hring við hvern kassa með strikum án þess að strikin skerist? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=53461

Einar Axel Helgason. „Gefnir eru þrír hringir og þrír kassar. Er hægt að tengja hvern hring við hvern kassa með strikum án þess að strikin skerist?“ Vísindavefurinn. 19. apr. 2013. Vefsíða. 17. jún. 2019. <http://visindavefur.is/svar.php?id=53461>.

Chicago | APA | MLA

Sendu inn spurningu
eða

Vísindadagatalið

Ása L. Aradóttir

1959

Ása L. Aradóttir er prófessor við Auðlinda- og umhverfisdeild Landbúnaðarháskóla Íslands. Rannsóknir hennar snúa flestar að landgræðslu og þá einkum leiðum til að endurheimta hnignandi og skemmd vistkerfi.