Problema celor șapte poduri Königsberg

Problema podurilor Königsberg [ 1 ] [ 2 ] [ 3 ] _____  [9] [10] ) este o veche problemă de matematică care a întrebat cum este posibil să traversăm toate cele șapte poduri în centrul vechiul Königsberg fără să treacă de două ori prin niciunul dintre ele. A fost rezolvată pentru prima dată într-un articol din 1736 [2] [11] de către un matematician  Leonhard Euler , care a dovedit că acest lucru este imposibil și a inventat ciclurile Euler în cursul dovezii . Soluția lui Euler a problemei podului Königsberg a fost prima aplicare a teoriei grafurilor , dar fără a folosi termenul de „ graf ” și fără a desena diagrame de grafice.

Istorie

În centrul orașului Königsberg (acum Kaliningrad ) pe râul Pregel (acum Pregolya ) se află două insule: Kneiphof (acum Insula Immanuel Kant) și Lomse (acum Insula Oktyabrsky ). Pe malurile Pregelului, la nord de insula Kneiphof, se află Altstadt , la sud - Vorstadt . Au fost construite poduri peste Pregel care leagă aceste patru districte [12] . Figura din dreapta arată centrul orașului Königsberg pe o hartă din 1652 cu desemnările: A - Altstadt, B - Kneiphof, C - Lomse și D - Vorstadt.

Istoria construcției de poduri în Königsberg

Primele șapte poduri din centrul orașului Königsberg, care leagă Altstadt, Kneiphof, Lomse și Vorstadt, au fost construite în anii următori în următoarea ordine [12] . Numărul de poduri în ordinea în care au fost construite este prezentat în figura din dreapta.

1. Pod magazin (1286)

Primul pod din Königsberg datează din 1286. Au conectat Altstadt și Kneiphof. A aparținut orașului Altstadt și a oferit orașului acces ușor la piețele din Kneiphof [12] .

2. Podul verde (1322)

Al doilea pod din Königsberg a fost construit în 1322. A conectat Kneiphof cu Vorstadt și a oferit acces ușor la zone îndepărtate. Podul a fost numit Verde din cauza valurilor verzi care servesc drept fundal stemei Kneiphof [12] .

3. Pod de lucru (1377)

În secolul al XIV-lea, în estul Vorstadt-ului exista un abator. Pentru a facilita transportul cărnii, a fost construit un al treilea pod între Kneiphof și Vorstadt în 1377 [12] .

4. Podul fierarului (1397)

în 1397, în partea de nord-est a Kneiphof a fost construit al patrulea Pod al Fierarilor, care a început în apropierea atelierelor de fierărie din Altstadt [12] .

Dacă se trasează un grafic peste aceste patru poduri , atunci acesta va fi Euler , adică toate cele patru poduri pot fi ocolite o dată de-a lungul unui traseu închis, începând din orice loc. Locuitorii puteau face astfel de plimbări [12] .

5. Pod de lemn (1404)

Cherestea a fost recoltată pe insula Lomse, iar un al cincilea pod între Altstadt și Lomse, construit între 1400 și 1404, a facilitat livrarea de cherestea [12] .

6. Pod înalt (1506)

Al șaselea pod a fost construit în 1506 pentru a lega Lomse și Vorstadt [12] .

7. Honey Bridge (1542)

Al șaptelea dintre podurile lui Euler, care leagă cele două insule, a fost finalizat în 1542. A fost construit de locuitorii din Kneiphof pentru a trece pe malul de nord, ocolind cele două poduri din Kneiphof controlate de Altstadt. Potrivit legendei, Kneiphof a dat un butoi cu miere lui Altstadt pentru a obține permisiunea de a construi un pod [12] .

Deci, în 1542, toate cele șapte poduri din Königsberg, considerate de Euler, erau la locul lor. Acum locuitorii nu puteau ocoli toate podurile la un moment dat [12] .

Istoricul problemelor

Apariția ramurii matematicii a teoriei grafurilor este asociată cu puzzle-urile matematice, iar pentru unii destul de multă vreme teoria grafurilor a fost „frivolă” și în întregime asociată cu jocurile și divertismentul. Această soartă a teoriei grafurilor repetă soarta teoriei probabilităților , care și-a găsit pentru prima dată aplicarea doar în jocurile de noroc [13] .

Locuitorii din Koenigsberg au jucat un fel de joc: cum să treacă prin toate podurile orașului pentru ca traseul să nu treacă de două ori pe niciunul dintre ele [3] . „După cum am auzit”, a scris Leonhard Euler, „unii neagă că acest lucru se poate face, alții se îndoiesc, dar nimeni nu confirmă o astfel de posibilitate. [14] »

Istoricul publicării lucrării lui Leonhard Euler

Leonhard Euler, un remarcabil matematician și mecanic elvețian, prusac și rus , academician al Academiei de Științe din Sankt Petersburg a devenit interesat de acest joc. Istoria publicării celebrului articol de Leonhard Euler „Rezolvarea unei probleme legate de geometria poziției”, scrisă în legătură cu aceasta, are următoarele etape cunoscute din publicațiile moderne:

• mai întâi , la 26 august  ( 6 septembrie )  1735 [15] , Euler a prezentat un articol la Conferința Academiei de Științe din Sankt Petersburg [2] ;
• apoi, în 1736, Euler, ca parte a corespondenței sale științifice, a trimis următoarele două scrisori:

• 13 martie  ( 24 ),  1736 - scrisoare către Johann Jacob Marinoni , un astronom și matematician austriac, din 13 martie [24], 1736, Petersburg. Această scrisoare este dedicată în întregime problemei podului Königsberg [16] [17] ;
• 3 aprilie  ( 14 ),  1736 - o scrisoare către Karl Leonard Gottlieb Oehler , un politician și astronom german, datată 3 aprilie [14] 1736, Petersburg. La finalul acestei scrisori, vorbim despre ideile principale ale lucrării [16] [18] ;

• în 1741 la Sankt Petersburg , articolul lui Euler a fost publicat în cele din urmă în latină cu data 1736 [16] [19] :

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

Tradus [14] :

Leonard Euler. Rezolvarea unei probleme legate de geometria poziției / Proceedings of the St. Petersburg Academy of Sciences. 8 (1736). 1741, p. 128-140.

Întrucât publicarea articolului lui Leonhard Euler „Rezolvarea unei probleme legate de geometria poziției” este datată din 1736, iar ambele scrisori menționate mai sus datează din acest an, acest an este desemnat de comunitatea matematică mondială drept data nașterii secțiunea teoriei grafurilor matematice [2] .

O soluție modernă a problemei

Declarația problemei

Problema podurilor Königsberg este formulată diferit de diferiți autori.

1. Traseul este arbitrar

În legătură cu aceste poduri s-a pus întrebarea dacă este posibil să treci peste ele în așa fel încât să treci peste fiecare dintre aceste poduri, și exact o dată.

— Leonhard Euler. Rezolvarea unei probleme legate de geometria poziției [14]

Pentru locuitorii din Königsberg exista un fel de joc: să găsească un astfel de traseu de plimbare în jurul orașului care să treacă prin fiecare dintre podurile prezentate în figură o singură dată.

— Fritsch R. et al. Capitole selectate în teoria graficelor [3]

2. Traseul trebuie să fie închis

Sarcina era următoarea: să găsești un traseu de trecere prin toate cele patru părți ale pământului, care să înceapă cu oricare dintre ele, să se termine pe aceeași parte și să treacă exact o dată peste fiecare pod.

— Frank Harari. Teoria grafurilor [1]

3. Rutele bucle trebuie să înceapă în fiecare parte a orașului

De fapt, este necesar să se găsească patru rute care ocolesc podurile Königsberg, începând din patru părți ale orașului.

Întrebarea a fost, este posibil să se facă o plimbare în așa fel încât, după ce a părăsit casa, să se întoarcă, trecând exact o dată peste fiecare pod?

— Ore O. Grafice și aplicațiile lor [20]

Construirea unui grafic al sarcinii

Soluția modernă a problemei podurilor Königsberg începe cu construirea unui grafic al problemei (vezi figura din dreapta) [21] :

• vârfurile graficului sunt patru părți ale centrului Königsberg, în care orașul este împărțit de două ramuri și un canal de râu;
• nervurile graficului sunt cele șapte poduri din centrul orașului;
• vârfurile de capăt ale marginilor sunt părți ale centrului Königsberg conectate prin aceste poduri.

Problema podului Königsberg poate fi reformulată în termeni de teoria grafurilor după cum urmează [22] :

• Graficul problemei podului Königsberg are un ciclu Euler sau cel puțin un lanț Euler ?

Teoremele lui Euler

Să începem cu definiții, să trecem la teoreme și să terminăm cu corolare [22] :

• Lanțul Euler - o succesiune de muchii (marginile învecinate au un vârf comun) care ocolește toate muchiile graficului o dată;
• Ciclul Euler este un lanț Euler închis.

Următoarele două teoreme au apărut pentru prima dată în lucrarea lui Leonhard Euler despre podurile Königsberg [22] :

• Prima teoremă a lui Euler, 1736. Un grafic cu două sau mai multe vârfuri are un ciclu Euler dacă și numai dacă fiecare vârf are un număr par de muchii;
• A doua teoremă a lui Euler, 1736. Un grafic cu două sau mai multe vârfuri are o cale Euler unică dacă și numai dacă exact două vârfuri au un număr impar de muchii.

Din aceste două teoreme pot fi deduse trei consecințe [22] :

• dacă un graf cu două vârfuri care conțin un număr impar de muchii are un lanț Euler, atunci aceste două vârfuri sunt vârfurile inițiale și finale ale lanțului;
• un grafic cu două sau mai multe vârfuri are un lanț Euler dacă și numai dacă fie fiecare vârf are un număr par de muchii, fie exact două vârfuri au un număr impar de muchii;
• problema podului Königsberg nu are soluție, deoarece patru vârfuri din graficul acestei probleme au un grad impar.

Rezolvarea problemei după Leonhard Euler

Declarația problemei

Leonhard Euler, în celebrul său articol, a formulat problema celor șapte poduri Königsberg după cum urmează [14] :

2. Această sarcină, mi s-a spus, este destul de cunoscută și are legătură cu aceasta. În orașul Königsberg, în Prusia, există o insulă numită Kneiphof ; râul care îl înconjoară este împărțit în două ramuri, care pot fi văzute în figură. Ramurile acestui râu sunt străbătute de șapte poduri a , b , c , d , e , f și g . În legătură cu aceste poduri s-a pus întrebarea dacă este posibil să treci peste ele în așa fel încât să treci peste fiecare dintre aceste poduri, și exact o dată.

— Leonhard Euler. Rezolvarea unei probleme legate de geometria poziției

Rezolvarea problemei

Leonhard Euler și-a formulat metoda după cum urmează (vezi figura de mai sus) [23] :

4. Întreaga mea metodă se bazează pe notarea corectă pentru pasajele individuale ale podurilor. Folosesc majusculele A, B, C, D pentru a indica zonele individuale în care râul împarte pământul. Astfel, dacă cineva se deplasează din zona A în zona B printr-un pod a sau b, atunci notez trecerea podului cu simbolul AB.

— Leonhard Euler. Rezolvarea unei probleme legate de geometria poziției

În limbajul modern, aceasta înseamnă că graficul podurilor orașului corespunde graficului, care este:

• patru vârfuri după denumirile celor patru părți ale centrului orașului;
• vârfurile sunt conectate prin șapte muchii-punți conform denumirilor a șapte poduri.

O soluție destul de modernă și simplă de Leonhard Euler a problemei podului Königsberg este următoarea. Trebuie reținut doar că Euler nu cunoștea terminologia modernă, nu folosea termenul „graf”, numit marginea „punte”, iar vârful - „zonă” sau „litera” și nu a desenat imagini moderne ale graficelor. [23] .

• „Astfel, devine evident că, dacă este posibil să treci peste șapte poduri și fiecare dintre ele exact o dată, atunci această rută va fi reprezentată de opt litere.”
• „... Am elaborat o regulă prin care se poate decide cu ușurință - atât pentru această problemă, cât și pentru toate problemele similare - dacă un astfel de aranjament de scrisori poate fi realizat.

„ 8. Pentru a deriva o astfel de regulă, am în vedere o zonă specifică în care poate duce un număr arbitrar de poduri etc. Din aceste poduri, voi lua în considerare mai întâi un pod specific care duce în zonă . Dacă un călător traversează acest pod, fie a fost în zonă înainte de a traversa acest pod, fie va fi în zonă după aceea. Prin urmare, pentru a desemna acest pasaj peste pod, așa cum este descris mai sus, este necesar ca litera să apară o dată .

• „Dacă trei poduri duc în zonă, de exemplu , iar călătorul trece prin toate cele trei poduri, atunci litera va apărea în descrierea mișcării sale pe poduri de două ori, indiferent dacă traseul său a pornit sau nu. În același mod, dacă există cinci poduri care duc în zonă, atunci litera ar trebui să apară de trei ori atunci când descrie mișcarea acesteia. Și când numărul de punți este un număr impar arbitrar, atunci dacă îl creșteți cu unu, jumătate din numărul rezultat arată de câte ori trebuie să apară litera .
• „ 9. Prin urmare, în cazul podurilor Königsberg, deoarece cinci poduri duc la insulă , este necesar ca litera să apară în descrierea mișcării de-a lungul acestor poduri de trei ori. În plus, scrisoarea trebuie să se întâlnească de două ori , deoarece există trei poduri care duc în zonă, iar literele trebuie să se întâlnească de două ori fiecare. Prin urmare, într-o succesiune de opt litere care descrie traseul în cauză, trecând prin șapte poduri, litera trebuie să apară de trei ori, iar fiecare dintre litere de două ori. Aceasta, însă, nu poate fi într-o succesiune de opt litere. Astfel, este clar că o astfel de plimbare de-a lungul celor șapte poduri din Königsberg este imposibilă.”

Generalizarea soluției problemei

Rezolvând problema în termeni generali, Leonhard Euler a demonstrat pe parcurs că pentru orice graf, numărul de vârfuri cu un număr impar de muchii este par [24] :

• „Voi observa mai întâi că toate numărul de poduri” care duc în regiune, „adunate împreună, dau de două ori numărul tuturor podurilor. Motivul este că fiecare pod este numărat de două ori în acest număr, astfel încât toate podurile care duc într-o anumită zonă sunt numărate, pentru că fiecare pod duce în cele două zone pe care le conectează.

17. Din această observație rezultă că suma [numerelor] tuturor podurilor care duc la fiecare regiune este un număr par, deoarece jumătate din această sumă este exact numărul de poduri. Prin urmare, nu se poate întâmpla ca dintre numărul de poduri care duc spre orice zonă, exact unul să fie impar; de asemenea, nu se poate întâmpla ca să existe trei, cinci, etc. de numere impare. Prin urmare, dacă numărul de poduri" care duc la regiune "sunt numere impare, suma lor este pară".

La sfârșitul articolului, Leonhard Euler a notat concluziile generale pentru orice grafic într-un limbaj destul de modern [24] :

20. Prin urmare, în fiecare caz posibil, următoarea regulă face posibil să se afle direct și fără dificultate dacă este posibil să se efectueze o plimbare pe toate podurile fără repetare:

Dacă există mai mult de două zone către care duc un număr impar de poduri, se poate spune cu certitudine că o astfel de plimbare este imposibilă.

Dacă, totuși, există doar două regiuni către care duc un număr impar de poduri, atunci mersul este fezabil, cu condiția să înceapă într-una dintre aceste două regiuni.

Dacă, în sfârșit, nu există nicio zonă spre care să ducă un număr impar de poduri, o plimbare cu condițiile cerute este fezabilă și poate începe în orice zonă.

Prin urmare, cu ajutorul acestei reguli, problema pusă poate fi rezolvată complet.

— Leonhard Euler. Rezolvarea unei probleme legate de geometria poziției

Vezi și

• Problema mișcării cavalerului
• teoria grafurilor
• Ciclul Euler
• Topologie
• Podurile din Kaliningrad
• Problema vânzătorului ambulant

Note

1. ↑ 1 2 Harari Frank. Teoria grafurilor, 2003 , p. 13.
2. ↑ 1 2 3 4 Fleischner G. Euler graphs and related issues, 2002 , p. unsprezece.
3. ↑ 1 2 3 Frich R., Peregud E. E., Matsievsky S. V. Selectate capitole ale teoriei grafurilor, 2008 , p. unu.
4. ↑ Fleischner G. Euler graphs and related issues, 2002 , p. 17.
5. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 , p. 129.
6. ↑ Frank Harary , Teoria graficelor, 2007 , p. unu.
7. ↑ Problema podului Königsberg // Britannica .
8. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selectate capitole ale teoriei grafurilor, 2008 , p. vii.
9. ↑ Denes Konig. Theorie der endlichen und unendlichen Graphen, 1936 , s. 24.
10. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selectate capitole ale teoriei grafurilor, 2008 , p. ix.
11. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selectate capitole ale teoriei grafurilor, 2008 , p. 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. ↑ Ore O. Grafice și aplicarea lor, 1965 , p. 6.
14. ↑ 1 2 3 4 Fleischner G. Euler graphs and related issues, 2002 , p. 26.
15. ↑ Procesele verbale ale ședințelor Conferinței Academiei Imperiale de Științe din 1725 până în 1803. Volumul I. 1725-1743, 1897 , p. 220-221.
16. ↑ 1 2 3 Fleischner G. Euler graphs and related issues, 2002 , p. cincisprezece.
17. ↑ Scrisori către oameni de știință, 1963 , p. 152-158.
18. ↑ Scrisori către oameni de știință, 1963 , p. 330-353.
19. ↑ Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis, 1736 .
20. ↑ Ore O. Grafice și aplicarea lor, 1965 , p. 33.
21. ↑ Frich R., Peregud E. E., Matsievsky S. V. Selectate capitole ale teoriei grafurilor, 2008 , p. patru.
22. ↑ 1 2 3 4 Frich R., Peregud E. E., Matsievsky S. V. Selectate capitole ale teoriei grafurilor, 2008 , p. 8-12.
23. ↑ 1 2 Fleischner G. Euler graphs and related issues, 2002 , p. 27-28.
24. ↑ 1 2 Fleischner G. Euler graphs and related issues, 2002 , p. 31-32.

Literatură

• Ore O. Grafice și aplicarea lor / Per. din engleza. L. I. Golovina. Ed. I. M. Yagloma. M.: Mir, 1965. 174 p.: ill.
• Procesele-verbale ale ședințelor Conferinței Academiei Imperiale de Științe din 1725 până în 1803. Volumul I. 1725-1743 / Procès-verbaux des l'Académie Impériale des Sciences depuis sa fondation jusqu'à 1803. Sankt Petersburg: Tipografia IAN, 1897. 883 p.
• Harary Frank. Teoria grafurilor / Per. din engleza. V. P. Kozyreva. Ed. G. P. Gavrilova. editia a 2-a. M.: Editorial URSS, 2003. 296 p.: ill. ISBN 5-354-00301-6 .
• Fleishner G. Euler grafice și probleme conexe. M.: Mir, 2002. 335 p.: ill. ISBN 5-03-003115-4 (rusă). ISBN 0-444-88395-9 . [Fleischner H. Grafice euleriene și subiecte înrudite. P. 1, V. 1. Amsterdam: Olanda de Nord, 1990.]
• Frich R., Peregud E. E., Matsievsky S. V. Selected Chapters of Graph Theory: Textbook / Per. cu el. E. E. Pereguda; Paul ed. S. V. Matsievski. Kaliningrad: Editura Universității de Stat din Rusia. I. Kant, 2008. 192 p.: ill. ISBN 978-5-88874-880-0 .
• Leonard Euler. Scrisori către oameni de știință / Ed. Academician V. I. Smirnov . - Moscova-Leningrad: Editura Academiei de Științe a URSS , 1963. Conține textul original latin al scrisorilor și traducerea în rusă de Yu. Kh. Kopelevich (scrisoare către Marinoni) și T. A. Lukina (scrisoare către Eler).
• Problema podului Konigsberg // Britannica. * Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis // Commentarii Academiae Scientiarum Petropolitanae. 8 (1736) 1741, 128–140.
• Gribkovskaia I., Halskau Ø., Laporte G. Podurile din Königsberg–O perspectivă istorică // ​​Rețele. 2007. 49(3):199–203.
• Frank Harary Teoria grafurilor. Reading, Massachusetts: Addison-Wesley Publishing Company, 1969. 283 p.
• Denes Konig. Theorie der endlichen und unendlichen Graphen. Topologie combinată de Streckenkomplexe. Leipzig: Akademische Verlagsgesellschaft MBH, 1936.

Dicționare și enciclopedii	mare danez Britannica (online)