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?

Nafn þitt

Netfang þitt

Netfang móttakanda

Ruslpóstvörn =

Svar

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?

Þ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.

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.

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.

Þ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.

Á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:

• Utility Graph -- from Wolfram MathWorld. (Skoðað 3.8.2012).
• Water, gas and electricity - Wikipedia, the free encyclopedia. (Skoðað 3.8.2012).

Myndir:

• EAH.

...