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 ^[1]. 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).

→ →

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õrkude^[2] ja Arthur Cayley 1857. aastal orgaaniliste isomeeride alastes uuringutes^[3]. Sõna "graaf" võttis esimesena kasutusele James Joseph Sylvester keemiliste struktuurivalemite kujutamisel 1878. aastal^[4].

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

Vaata ka

Hamiltoni graaf

Viited

↑ Euler, L. 1736. Solutio problematis. ad geometriam situs pertinentis. – Comment. Academiae I Petropolitanae 8 (1736) 128-140
↑ Kirchhof, 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.
↑ Cayley, A., 1857. On the theory of the analytical forms called trees. – Phil. Mag. (4) 13 (1857), 172–176.
↑ Silvester, J.J., 1878. Chimistry and algebra. – Nature 17 (1878), 284.

[1] Euler, L. 1736. Solutio problematis. ad geometriam situs pertinentis. – Comment. Academiae I Petropolitanae 8 (1736) 128-140

[2] Kirchhof, 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.

[3] Cayley, A., 1857. On the theory of the analytical forms called trees. – Phil. Mag. (4) 13 (1857), 172–176.

[4] Silvester, J.J., 1878. Chimistry and algebra. – Nature 17 (1878), 284.

[1]

[2]

[3]

[4]