Königsbergi sildade probleem

Königsbergi sildade probleem on üks ajalooliselt märkimisväärne ülesanne matemaatikas. Selle Leonhard Euleri poolt aastal 1735 antud negatiivne lahendus lõi aluse graafiteooriale ja tekitas mõtteid topoloogia arendamiseks.

 Probleemi teke 
Königsberg oli asutatud Pregeli jõe kallastele. Selle mõlemad kaldad ja saared jões olid ühendatud seitsme sillaga. Linna elanikud murdsid pead selle üle, kuidas korraldada jalutuskäiku nii, et ületada kõik seitse silda vaid üks kord ning jõuda tagasi kohta, kust jalutuskäiku alustati. Tehti palju praktilisi katseid, jalutuskäiku alustati erinevatest kohtadest ja liiguti erinevaid teid pidi, kuid katsed ei õnnestunud. Asja vastu hakkas huvi tundma ka Leonhard Euler.

 Euleri analüüs 
Euler pidas tollal seda probleemi geomeetriaülesandeks Euler, L. 1736. Solutio problematis. ad geometriam situs pertinentis. – Comment. Academiae I Petropolitanae 8 (1736) 128-140. Ta märkis kõigepealt, et marsruudi valik maismaal ei oma mingit tähtsust. Ainus oluline tingimus on sildade ületamise järjestus. Ülesannet formaliseerides konstrueeris ta seda iseloomustava originaalse skeemi (mida siis veel graafiks ei nimetatud).

180px →
179px →
180px

Euler pani tähele, et mööda seda skeemi liikudes peab iga marsruudi korral sillale (tippu) sisenevate ja sealt väljuvate joonte (servade, kaarte) arv olema võrdne. Kuna iga silda võib ületada vaid ühe korra, siis peab teelõikude arv mööda maad võrduma sildade arvuga. Samas on kõik neli maalõiku läbitud paaritu arvu sildade kaudu (üks viie ja teine kolme silla kaudu). Äärmisel juhul võivad kaks maalõiku osutuda selle marsruudi algus- ja lõpp-punktideks, kuid see on vastuolus põhinõudega läbida iga sild parajasti üks kord.

Graafiteooria terminites esitatult väidab Euler, et sildu parajasti üks kord läbiv marsruut sõltub tippude valentsusest (astmest). Vajalik tingimus selleks on graafi sidusus ja nulli või kahe paarituarvulise valentsusega (astmega) tipu olemasolu. See tingimus on hiljem ka piisavaks osutunud. Niisugust marsruuti nimetatakse nüüd Euleri teeks (ahelaks).

 Järelkaja 
Selle ülesande lahendamisega pani Euler aluse graafiteooriale ja selliseid skeeme käsitles ta oma töödes ka 1750., 1752. ja 1759. aastal.

Need Euleri tulemused jäid pikemaks ajaks unustusse ja graafe on korduvalt "uuesti avastatud". Nii avastas need Gustav Kirchhoff 1847. aastal oma elektrivõrkudeKirchhof, T.P., 1847. Über die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird. – Ann. Phys. Chem. 72 (1847), 497–508. ja Arthur Cayley 1857. aastal orgaaniliste isomeeride alastes uuringutesCayley, A., 1857. On the theory of the analytical forms called trees. – Phil. Mag. (4) 13 (1857), 172–176.. Sõna "graaf" võttis esimesena kasutusele James Joseph Sylvester keemiliste struktuurivalemite kujutamisel 1878. aastalSilvester, J.J., 1878. Chimistry and algebra. – Nature 17 (1878), 284..

Königsbergi ajaloolistest sildadest on tänapäeval annekteeritud Kaliningradis säilinud kaks.

 Vaata ka 
 Hamiltoni graaf

 Viited 

Kategooria:Matemaatika
Kategooria:Graafiteooria
Kategooria:Kaliningrad