Problema podurilor din Königsberg
Cele șapte poduri din Königsberg este o problemă de matematică celebră din punct de vedere istoric. Leonhard Euler a rezolvat problema în 1735. Aceasta a dus la începutul teoriei grafurilor. Aceasta a dus apoi la dezvoltarea topologiei.
Orașul Königsberg din Prusia (în prezent Kaliningrad, Rusia) a fost așezat pe ambele maluri ale râului Pregel. Acesta includea două insule mari care erau conectate între ele și cu continentul prin șapte poduri.
Problema era de a găsi o modalitate de a traversa orașul trecând fiecare pod o dată și numai o dată. La insule nu se putea ajunge pe nicio altă rută decât podurile. Fiecare pod trebuie să fi fost traversat complet de fiecare dată. Plimbarea nu trebuia să înceapă și să se termine în același loc. Euler a demonstrat că problema nu are soluție.
Hartă a orașului Königsberg în timpul lui Euler, care arată dispunerea actuală a celor șapte poduri, cu evidențierea râului Pregel și a podurilor
Analiza lui Euler
În primul rând, Euler a arătat că alegerea traseului în interiorul fiecărei mase de uscat nu are importanță. Singura proprietate importantă a unui traseu este ordinea în care sunt traversate podurile. Astfel, el a schimbat problema în termeni abstracți. Acest lucru a pus bazele teoriei grafurilor. A eliminat toate caracteristicile, cu excepția listei de mase terestre și a podurilor care le conectează. În limbajul teoriei grafurilor, a înlocuit fiecare masă de pământ cu un "vertex" sau nod abstract. Apoi a înlocuit fiecare pod cu o conexiune abstractă, o "muchie". O muchie (drum) a înregistrat ce două verigi (mase de pământ) erau conectate. În acest fel, el a format un graf.
→
→ 
Graficul desenat este o imagine abstractă a problemei. Așadar, marginile pot fi unite în orice mod. Este important doar dacă două puncte sunt conectate sau nu. Schimbarea imaginii graficului nu schimbă graficul în sine.
În continuare, Euler a observat că (cu excepția punctelor finale ale plimbării), ori de câte ori se intră într-un vertex printr-un pod, se părăsește vertexul printr-un pod. În orice parcurs al grafului, numărul de intrări într-un vertex este egal cu numărul de ieșiri din el. Dacă fiecare pod a fost traversat exact o dată, rezultă că, pentru fiecare masă de pământ (cu excepția celor alese pentru început și sfârșit), numărul de poduri care ating masa de pământ trebuie să fie par. Acest lucru se datorează faptului că, dacă există n poduri, aceasta este traversată exact de 2n ori. Cu toate acestea, toate cele patru mase de pământ din problema inițială sunt atinse de un număr impar de poduri (unul dintre ele este atins de 5 poduri, iar celelalte trei sunt atinse de câte 3 poduri). Există cel mult două mase care pot fi punctele finale ale unei plimbări. Așadar, propunerea ca o plimbare să traverseze fiecare pod o singură dată duce la o contradicție.
În limbaj modern, Euler arată că este posibilă sau nu o plimbare printr-un graf care traversează fiecare muchie o dată, în funcție de gradele nodurilor. Gradul unui nod este numărul de muchii care îl ating. Euler arată că o condiție necesară pentru plimbare este ca graful să fie conectat și să aibă exact zero sau două noduri de grad impar. Acest rezultat enunțat de Euler a fost demonstrat ulterior de Carl Hierholzer. Un astfel de traseu se numește acum traseu Eulerian sau traseu Euler. Dacă există noduri de grad impar, atunci orice cale Euleriană va începe la unul dintre ele și se va termina la celălalt. Deoarece graful care reprezintă Königsbergul istoric are patru noduri de grad impar, nu poate avea o traiectorie euleriană.
Lucrarea lui Euler a fost prezentată Academiei din Sankt Petersburg la 26 august 1735. Ea a fost publicată ca Solutio problematis ad geometriam situs pertinentis (Soluția unei probleme referitoare la geometria poziției) în revista Commentarii academiae scientiarum Petropolitanae în 1741. Ea este disponibilă în limba engleză în The World of Mathematics.
Importanța în istoria matematicii
În istoria matematicii, soluția lui Euler la problema podului Königsberg este considerată prima teoremă a teoriei grafurilor. Teoria grafurilor este un subiect considerat în prezent, în general, ca fiind o ramură a combinatoricii.
Starea actuală a podurilor
Două dintre cele șapte poduri originale au fost distruse în timpul bombardamentului asupra Königsbergului din timpul celui de-al Doilea Război Mondial. Alte două au fost demolate ulterior. Acestea au fost înlocuite de o autostradă modernă. Celelalte trei poduri au rămas, deși doar două dintre ele sunt din vremea lui Euler (unul a fost reconstruit în 1935). Astfel, în anul 2000, în Kaliningrad existau cinci poduri.
Din punct de vedere al teoriei grafurilor, două dintre noduri au acum gradul 2, iar celelalte două au gradul 3. Prin urmare, acum este posibil un traseu eulerian, dar, deoarece trebuie să înceapă pe o insulă și să se termine pe cealaltă, nu este practic pentru turiști.
Pagini conexe
- Joc Icosian
- Calea hamiltoniană
- Apă, gaz și electricitate
- Problema vânzătorului călător
Întrebări și răspunsuri
Î: Care este problema celor Șapte Poduri din Königsberg?
R: Cele șapte poduri din Königsberg este o problemă matematică faimoasă care presupune găsirea unei modalități de a traversa orașul trecând prin fiecare dintre cele șapte poduri o dată și numai o dată.
Î: Cine a rezolvat problema celor șapte poduri din Königsberg?
R: Leonhard Euler a rezolvat problema celor șapte poduri din Königsberg în 1735.
Î: La ce a dus rezolvarea problemei celor șapte poduri din Königsberg?
R: Rezolvarea problemei celor șapte poduri din Königsberg a dus la începutul teoriei grafurilor, care a dus apoi la dezvoltarea topologiei.
Î: Unde se află Königsberg?
R: Königsberg este situat în Prusia, care în prezent face parte din Kaliningrad, Rusia.
Î: Care a fost configurația orașului Königsberg?
R: Königsberg a fost amenajat pe ambele maluri ale râului Pregel și includea două insule mari care erau conectate între ele și cu partea continentală prin șapte poduri.
Î: Care au fost cerințele pentru rezolvarea problemei celor șapte poduri din Königsberg?
R: Problema presupunea găsirea unei modalități de a traversa orașul prin traversarea fiecărui pod o dată și numai o dată, fiecare pod fiind traversat complet de fiecare dată. La insule nu se putea ajunge pe altă rută decât podurile, iar plimbarea nu trebuia să înceapă și să se termine în același loc.
Î: A demonstrat Euler că problema celor șapte poduri din Königsberg are o soluție?
R: Nu, Euler a demonstrat că problema celor șapte poduri din Königsberg nu are soluție.
