Königsbergi sildade probleem

Allikas: Vikipeedia
Königsbergi plaan Euleri ajal näitab seitsme Pregeli jõge ületava silla asetust

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[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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

Konigsberg bridges.png7 bridges.svgKonigsburg graph.svg

Euler pani tähele, et iga marsruudi korral mööda seda skeemi peab silda (tippu) sisenevate ja väljuvate joonte (servade, kaarte) arvud olema võrdsed. Kuna igat silda võib ületada vaid üks kord, 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 alustus- ja lõpppunktideks, kuid see on vastuolus põhinõudega läbida iga sild parajasti üks kord.

Graafiteooria terminites esitatult väidab Euler, et sildasid parajasti üks kord läbiv marsruut sõltub tippude valentsusest (astmest). Vajalik tingimus selleks on graafi sidusus ja null 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[muuda | redigeeri lähteteksti]

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

Need Euleri tulemused jäid pikemaks ajaks unustusse ning graafe on korduvalt „uuesti avastatud”. Nii avastas need G. R. Kirchhof 1847. aastal oma elektrivõrkude[2] ning A. Cayley 1857. aastal orgaaniliste isomeeride alastes uuringutes[3]. Sõna „graaf” võttis esimesena kasutusele J. J. Sylvester keemiliste struktuurvalemite kujutamisel 1878. aastal[4].

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

Vaata ka[muuda | redigeeri lähteteksti]

Viited[muuda | redigeeri lähteteksti]

  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 Greichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanisch 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.