Problém sedmi mostů Königsberg

Problém Königsbergských mostů [ 1 ] [ 2 ] [ 3 ] _____  [9] [10] ) je starý matematický problém, který se ptal, jak je možné přejít všech sedm mostů v centru starý Königsberg , aniž by přes kterýkoli z nich dvakrát prošel. Poprvé to vyřešil v článku z roku 1736 [2] [11] matematik Leonhard Euler , který dokázal, že to není možné, a v průběhu důkazu vynalezl Eulerovy cykly . Eulerovo řešení problému Königsbergského mostu bylo vůbec první aplikací teorie grafů , ale bez použití termínu „ graf “ a bez kreslení diagramů grafů.   

Historie

V centru Königsbergu (nyní Kaliningrad ) na řece Pregel (nyní Pregolya ) jsou dva ostrovy: Kneiphof (nyní ostrov Immanuela Kanta) a Lomse (nyní Oktyabrský ostrov ). Na březích řeky Pregel na severu ostrova Kneiphof je Altstadt , na jihu - Vorstadt . Přes řeku Pregel byly postaveny mosty spojující tyto čtyři okresy [12] . Obrázek vpravo ukazuje centrum Königsbergu na mapě z roku 1652 s označením: A - Altstadt, B - Kneiphof, C - Lomse a D - Vorstadt.

Historie stavby mostů v Königsbergu

Sedm prvních mostů centra Königsbergu, spojujících Altstadt, Kneiphof, Lomse a Vorstadt, bylo postaveno v následujících letech v následujícím pořadí [12] . Počty mostů v pořadí, v jakém byly postaveny, jsou uvedeny na obrázku vpravo.

1. Obchodní most (1286)

První most v Königsbergu pochází z roku 1286. Propojený Altstadt a Kneiphof. Patřil k městu Altstadt a poskytoval městu snadný přístup na trhy Kneiphof [12] .

2. Zelený most (1322)

Druhý most Königsberg byl postaven v roce 1322. Spojoval Kneiphof s Vorstadtem a poskytoval snadný přístup do odlehlých oblastí. Most se nazýval Zelený kvůli zeleným vlnám, které slouží jako pozadí erbu Kneiphof [12] .

3. Pracovní most (1377)

Ve 14. století byla na východě Vorstadtu jatka. Pro usnadnění přepravy masa byl v roce 1377 postaven třetí most mezi Kneiphofem a Vorstadtem [12] .

4. Kovářův most (1397)

v roce 1397 byl v severovýchodní části Kneiphofu postaven čtvrtý Kovářský most, který začínal poblíž kovářských dílen v Altstadtu [12] .

Pokud je nakreslen graf přes tyto čtyři mosty , pak to bude Euler , to znamená, že všechny čtyři mosty lze jednou obejít po uzavřené trase, počínaje jakýmkoli místem. Obyvatelé mohli takové procházky podnikat [12] .

5. Dřevěný most (1404)

Dřevo se těžilo na ostrově Lomse a pátý most mezi Altstadtem a Lomse, postavený v letech 1400 až 1404, usnadnil dodávku dřeva [12] .

6. Vysoký most (1506)

Šestý most byl postaven v roce 1506, aby spojil Lomse a Vorstadt [12] .

7. Medový most (1542)

Sedmý z Eulerových mostů, spojující oba ostrovy, byl dokončen v roce 1542. Postavili ho obyvatelé Kneiphofu, aby prošel na severní břeh a obešel dva mosty z Kneiphofu ovládané Altstadtem. Podle legendy dal Kneiphof sud medu Altstadtu, aby získal povolení ke stavbě mostu [12] .

Takže v roce 1542 bylo na místě všech sedm mostů Königsberg, o kterých uvažoval Euler. Nyní obyvatelé nemohli obejít všechny mosty najednou [12] .

Historie problémů

Vznik odvětví matematické teorie grafů je spojen s matematickými hádankami a pro některé poměrně dlouhou dobu byla teorie grafů „frivolní“ a zcela spojená s hrami a zábavou. Tento osud teorie grafů opakuje osud teorie pravděpodobnosti , která také poprvé našla své uplatnění pouze v hazardních hrách [13] .

Obyvatelé Koenigsbergu hráli jakousi hru: jak projet všechny městské mosty tak, aby trasa nepřecházela žádný z nich dvakrát [3] . „Jak jsem slyšel,“ napsal Leonhard Euler, „někteří popírají, že to lze udělat, jiní o tom pochybují, ale nikdo takovou možnost nepotvrzuje. [14] »

Historie publikace článku Leonharda Eulera

O tuto hru se začal zajímat Leonhard Euler, vynikající švýcarský, pruský a ruský matematik a mechanik , akademik Petrohradské akademie věd . Historie vydání slavného článku Leonharda Eulera „Řešení problému souvisejícího s geometrií polohy“, napsaného v této souvislosti, má následující etapy známé z moderních publikací:

• nejprve , 26. srpna  ( 6. září )  1735 [15] , Euler přednesl článek na konferenci Petrohradské akademie věd [2] ;
• pak v roce 1736 Euler v rámci své vědecké korespondence poslal tyto dva dopisy:

• 13. března  ( 24 ),  1736 - dopis Johannu Jacobovi Marinonimu , rakouskému astronomovi a matematikovi, ze dne 13. března [24] 1736, Petersburg. Tento dopis je celý věnován problému Königsbergského mostu [16] [17] ;
• 3. dubna  ( 14 ),  1736 - dopis Karlu Leonardu Gottliebovi Oehlerovi , německému politikovi a astronomovi, z 3. dubna [14] 1736, Petersburg. Na konci tohoto dopisu hovoříme o hlavních myšlenkách příspěvku [16] [18] ;

• v roce 1741 v Petrohradě konečně vyšel Eulerův článek v latině s datem 1736 [16] [19] :

Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. S. 128-140.

Přeloženo [14] :

Leonard Euler. Řešení jednoho problému týkajícího se polohové geometrie / Proceedings of the St. Petersburg Academy of Sciences. 8 (1736). 1741, s. 128-140.

Vzhledem k tomu, že vydání článku Leonharda Eulera „Řešení problému souvisejícího s geometrií polohy“ je datováno rokem 1736 a oba výše uvedené dopisy pocházejí z tohoto roku, je tento rok označen světovou matematickou komunitou jako datum narození sekce matematické teorie grafů [2] .

Moderní řešení problému

Problémové prohlášení

Problém königsberských mostů formulují různí autoři různě.

1. Trasa je libovolná

V souvislosti s těmito mosty byla vznesena otázka, zda je možné po nich projít tak, aby se přešlo přes každý z těchto mostů, a to právě jednou.

— Leonhard Euler. Řešení jednoho problému souvisejícího s polohovou geometrií [14]

Pro obyvatele Königsbergu existovala určitá hra: najít takovou trasu pro procházky městem, která by procházela každým z mostů znázorněných na obrázku právě jednou.

— Fritsch R. et al. Vybrané kapitoly z teorie grafů [3]

2. Trasa musí být uzavřena

Úkol byl následující: najít cestu pro průjezd všemi čtyřmi částmi země, která by začínala kteroukoli z nich, končila na stejné části a procházela právě jednou přes každý most.

— Frank Harari. Teorie grafů [1]

3. Objízdné trasy musí začínat v každé části města

Ve skutečnosti je nutné najít čtyři trasy obcházející Königsbergské mosty, které začínají ve čtyřech částech města.

Otázkou bylo, zda je možné udělat procházku tak, že když vyjdete z domu, vrátíte se a přejdete přes každý most právě jednou?

— Ruda O. Grafy a jejich aplikace [20]

Vytvoření grafu úkolů

Moderní řešení problému Königsbergských mostů začíná konstrukcí grafu problému (viz obrázek vpravo) [21] :

• vrcholy grafu jsou čtyři části centra Königsbergu, na které je město rozděleno dvěma rameny a říčním kanálem;
• žebra grafu jsou sedm mostů v centru města;
• koncové vrcholy hran jsou části centra Königsbergu spojené těmito mosty.

Problém Königsbergského mostu lze přeformulovat z hlediska teorie grafů následovně [22] :

• Má graf problému Königsbergského mostu Eulerův cyklus nebo alespoň Eulerův řetězec ?

Eulerovy věty

Začněme definicemi, přejdeme k větám a skončeme důsledky [22] :

• Eulerův řetězec - posloupnost hran (sousední hrany mají společný vrchol), která jednou obejde všechny hrany grafu;
• Eulerův cyklus je uzavřený Eulerův řetězec.

Následující dvě věty se poprvé objevily v článku Leonharda Eulera o Königsbergských mostech [22] :

• První Eulerův teorém, 1736. Graf se dvěma nebo více vrcholy má Eulerův cyklus právě tehdy, když každý vrchol má sudý počet hran;
• Druhá Eulerova věta, 1736. Graf se dvěma nebo více vrcholy má jedinečnou Eulerovu cestu právě tehdy, když právě dva vrcholy mají lichý počet hran.

Z těchto dvou vět lze odvodit tři důsledky [22] :

• pokud má graf se dvěma vrcholy obsahujícími lichý počet hran Eulerův řetězec, pak jsou tyto dva vrcholy počátečními a konečnými vrcholy řetězce;
• graf se dvěma nebo více vrcholy má Eulerův řetězec právě tehdy, když má každý vrchol sudý počet hran, nebo právě dva vrcholy mají lichý počet hran;
• problém Königsbergského mostu nemá řešení, protože čtyři vrcholy v grafu tohoto problému mají lichý stupeň.

Řešení úlohy podle Leonharda Eulera

Problémové prohlášení

Leonhard Euler ve svém slavném článku formuloval problém sedmi königsberských mostů takto [14] :

2. Tento úkol, jak mi bylo řečeno, je poměrně známý a souvisí s tímto. Ve městě Königsberg v Prusku se nachází ostrov Kneiphof ; řeka, která jej obklopuje, je rozdělena na dvě ramena, což je vidět na obrázku. Ramena této řeky překonává sedm mostů a , b , c , d , e , f a g . V souvislosti s těmito mosty byla vznesena otázka, zda je možné po nich projít tak, aby se přešlo přes každý z těchto mostů, a to právě jednou.

— Leonhard Euler. Řešení jednoho problému souvisejícího s polohovou geometrií

Řešení problému

Leonhard Euler formuloval svou metodu následovně (viz obrázek výše) [23] :

4. Celá moje metoda je založena na správném zápisu jednotlivých průchodů mostů. Velká písmena A, B, C, D používám k označení jednotlivých oblastí, na které řeka pozemek rozděluje. Pokud se tedy někdo přesune z oblasti A do oblasti B přes most a nebo b, pak označuji průjezd mostem symbolem AB.

— Leonhard Euler. Řešení jednoho problému souvisejícího s polohovou geometrií

V moderním jazyce to znamená, že graf městských mostů odpovídá grafu, což je:

• čtyři vrcholy podle označení čtyř částí centra města;
• vrcholy jsou spojeny sedmi hranami-můstky podle označení sedmi mostů.

Poměrně moderní a jednoduché řešení problému mostu Königsberg od Leonharda Eulera je následující. Je třeba mít pouze na paměti, že Euler neznal moderní terminologii, nepoužíval termín "graf", nazývaný hranou "most" a vrchol - "plocha" nebo "písmeno" a nekreslil moderní obrázky grafů. [23] .

• "Je tedy zřejmé, že pokud je možné projít přes sedm mostů a každý z nich právě jednou, bude tato cesta představována osmi písmeny."
• „... Vyvinul jsem pravidlo, podle kterého lze snadno rozhodnout – jak pro tento problém, tak pro všechny podobné problémy – zda ​​lze takové uspořádání písmen provést.

“ 8. Pro odvození takového pravidla uvažuji nějakou konkrétní oblast, do které může vést libovolný počet mostů atd. Z těchto mostů budu nejprve uvažovat konkrétní most vedoucí do oblasti . Pokud cestovatel překročí tento most, buď byl v oblasti předtím, než přešel tento most, nebo bude v oblasti poté. Proto, aby bylo možné označit tento průchod přes most, jak je popsáno výše, je nutné, aby se písmeno objevilo jednou .

• „Pokud do oblasti vedou například tři mosty a cestující projede všemi třemi mosty, pak se písmeno objeví v popisu jeho pohybu po mostech dvakrát, bez ohledu na to, zda jeho trasa začínala nebo ne. Stejně tak, pokud do oblasti vede pět mostů, pak by se při popisu pohybu mělo písmeno objevit třikrát. A když je počet můstků libovolné liché číslo, pak pokud jej zvýšíte o jednu, polovina výsledného čísla ukazuje, kolikrát se písmeno musí vyskytovat .
• “ 9. Proto v případě Königsbergských mostů, protože na ostrov vede pět mostů , je nutné, aby se písmeno v popisu pohybu po těchto mostech vyskytlo třikrát. Navíc se dopis musí potkat dvakrát , protože do oblasti vedou tři mosty a dopisy se musí potkat každý dvakrát. Proto se v posloupnosti osmi písmen, která popisuje danou trasu, procházející sedmi mosty, musí písmeno vyskytovat třikrát a každé z písmen dvakrát. To však nemůže být v sekvenci osmi písmen. Je tedy jasné, že taková procházka po sedmi mostech Königsbergu je nemožná.“

Zobecnění řešení problému

Při řešení problému obecně Leonhard Euler dokázal, že pro jakýkoli graf je počet vrcholů s lichým počtem hran sudý [24] :

• „Nejprve poznamenám, že všechny počty mostů“ vedoucích do regionu „sečteny dohromady dávají dvojnásobný počet všech mostů. Důvodem je, že každý most se při tomto počítání započítává dvakrát, takže se započítají všechny mosty vedoucí do dané oblasti, pro každý most vede do dvou oblastí, které spojuje.

17. Z tohoto pozorování vyplývá, že součet [čísel] všech mostů vedoucích do každého regionu je sudé číslo, protože polovina tohoto součtu je přesně počet mostů. Nemůže se tedy stát, že mezi počtem mostů vedoucích do jakékoli oblasti je právě jeden lichý; také se nemůže stát, že jsou lichá čísla tři, pět atd. Je-li tedy počet mostů vedoucích do kraje "lichá čísla, je jejich součet sudý."

Na konci článku Leonhard Euler sepsal obecné závěry pro jakýkoli graf v docela moderním jazyce [24] :

20. Následující pravidlo tedy v každém možném případě umožňuje přímo a bez obtíží zjistit, zda je možné provést procházku přes všechny mosty bez opakování:

Pokud jsou více než dvě oblasti, do kterých vede lichý počet mostů, lze s jistotou říci, že taková procházka je nemožná.

Pokud však existují pouze dva regiony, do kterých vede lichý počet mostů, je procházka proveditelná za předpokladu, že začíná v jednom z těchto dvou regionů.

Pokud konečně neexistuje oblast, do které vede lichý počet mostů, je procházka s požadovanými podmínkami proveditelná a může začít v jakékoli oblasti.

S pomocí tohoto pravidla lze tedy vzniklý problém zcela vyřešit.

— Leonhard Euler. Řešení jednoho problému souvisejícího s polohovou geometrií

Viz také

• Problém tahu rytíře
• teorie grafů
• Eulerův cyklus
• Topologie
• Kaliningradské mosty
• Problém cestujícího prodejce

Poznámky

1. ↑ 1 2 Harari Frank. Teorie grafů, 2003 , str. 13.
2. ↑ 1 2 3 4 Fleischner G. Eulerovy grafy a související problémy, 2002 , str. jedenáct.
3. ↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů, 2008 , s. jeden.
4. ↑ Fleischner G. Eulerovy grafy a související problémy, 2002 , str. 17.
5. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 , str. 129.
6. ↑ Frank Harary Graph Theory, 2007 , str. jeden.
7. ↑ Problém mostu Königsberg // Britannica .
8. ↑ Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů, 2008 , s. vii.
9. ↑ Denes König. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24.
10. ↑ Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů, 2008 , s. ix.
11. ↑ Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů, 2008 , s. 151.
12. ↑ 1 2 3 4 5 6 7 8 9 10 11 Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg, 2007 .
13. ↑ Ruda O. Grafy a jejich aplikace, 1965 , s. 6.
14. ↑ 1 2 3 4 Fleischner G. Eulerovy grafy a související problémy, 2002 , str. 26.
15. ↑ Zápisy ze schůzí konference Císařské akademie věd z let 1725 až 1803. Svazek I. 1725-1743, 1897 , str. 220-221.
16. ↑ 1 2 3 Fleischner G. Eulerovy grafy a související problémy, 2002 , str. patnáct.
17. ↑ Dopisy vědcům, 1963 , s. 152-158.
18. ↑ Dopisy vědcům, 1963 , s. 330-353.
19. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 .
20. ↑ Ruda O. Grafy a jejich aplikace, 1965 , s. 33.
21. ↑ Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů, 2008 , s. čtyři.
22. ↑ 1 2 3 4 Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů, 2008 , s. 8-12.
23. ↑ 1 2 Fleischner G. Eulerovy grafy a související problémy, 2002 , s. 27-28.
24. ↑ 1 2 Fleischner G. Eulerovy grafy a související problémy, 2002 , s. 31-32.

Literatura

• Ruda O. Grafy a jejich aplikace / Per. z angličtiny. L. I. Golovina. Ed. I. M. Yagloma. M.: Mir, 1965. 174 s.: ill.
• Zápisy ze schůzí konference Císařské akademie věd z let 1725 až 1803. Svazek I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Petrohrad: Tiskárna IAN, 1897. 883 s.
• Harary Frank. Teorie grafů / Per. z angličtiny. V. P. Kozyreva. Ed. G. P. Gavrilová. 2. vydání. M.: Editorial URSS, 2003. 296 s.: ill. ISBN 5-354-00301-6 .
• Fleishner G. Eulerovy grafy a související problémy. M.: Mir, 2002. 335 s.: ill. ISBN 5-03-003115-4 (ruština). ISBN 0-444-88395-9 . [Fleischner H. Eulerovské grafy a příbuzná témata. S. 1, V. 1. Amsterdam: North-Holland, 1990.]
• Frich R., Peregud E. E., Matsievsky S. V. Vybrané kapitoly z teorie grafů: učebnice / Per. s ním. E. E. Pereguda; Paul ed. S. V. Matsievskij. Kaliningrad: Vydavatelství Ruské státní univerzity. I. Kant, 2008. 192 s.: ill. ISBN 978-5-88874-880-0 .
• Leonard Euler. Dopisy vědcům / Ed. Akademik V. I. Smirnov . - Moskva-Leningrad: Nakladatelství Akademie věd SSSR , 1963. Obsahuje původní latinský text dopisů a překlad do ruštiny od Yu.Kh.Koteleviče (dopis Marinonimu) a T. A. Lukina (dopis Elerovi).
• Problém mostu Konigsberg // Britannica. * Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Petropolitanae. 8 (1736) 1741, 128–140.
• Gribkovskaia I., Halskau Ø., Laporte G. The Bridges of Königsberg – Historical Perspective // ​​​​Networks. 2007. 49(3):199–203.
• Frank Harary teorie grafů. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283 s.
• Denes König. Theorie der endlichen und unendlichen Graphen. Kombinatorische Topologie der Streckenkokomplexe. Lipsko: Akademische Verlagsgesellschaft MBH, 1936.

Slovníky a encyklopedie	Velká dánština Britannica (online)