Königsbergi sildade probleem: erinevus redaktsioonide vahel

[[Königsberg]] oli asutatud [[Pregel]]i 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.

Euler pani tähele, et iga marsruudi korral mööda seda skeemi liikudes peab sildaiga marsruudi korral sillale (tippu) sisenevate ja sealt väljuvate joonte (servade, kaarte) arvudarv olema võrdsedvõrdne. Kuna igatiga silda võib ületada vaid üksühe kordkorra, 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 alustusalgus- ja lõpppunktidekslõpp-punktideks, kuid see on vastuolus põhinõudega läbida iga sild parajasti üks kord.

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

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

Need Euleri tulemused jäid pikemaks ajaks unustusse ningja graafe on korduvalt „uuesti avastatud”. Nii avastas need [[Gustav Kirchhoff|G. R. Kirchhoff]] [[1847]]. aastal oma elektrivõrkude<ref>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.</ref> ningja A. Cayley [[1857]]. aastal orgaaniliste [[isomeerid]]e alastes uuringutes<ref>Cayley, A., 1857. ''On the theory of the analytical forms called trees''. – Phil. Mag. (4) 13 (1857), 172–176.</ref>. Sõna „graaf” võttis esimesena kasutusele J. J. Sylvester keemiliste struktuurvalemitestruktuurivalemite kujutamisel [[1878]]. aastal<ref>Silvester, J.J., 1878. ''Chimistry and algebra''. – Nature 17 (1878), 284.</ref>.