Problema podurilor din Königsberg

Problema celor șapte poduri din Königsberg este o problemă de matematică de importanță istorică. Leonhard Euler a arătat în 1736 că nu există soluție, punând bazele teoriei grafurilor și prefigurând ideea de topologie.

Hartă a Königsbergului pe vremea lui Euler cu dispunerea efectivă a celor șapte poduri, figurând și râul Pregel și podurile

Orașul Königsberg din Prusia (astăzi, Kaliningrad, Rusia) se întindea pe ambele maluri ale râului Pregel^⁠(d), cuprinzând și două insule mari legate una de cealaltă, și cu diverse alte porțiune ale orașului prin șapte poduri. Problema era de a elabora un drum prin oraș, care să traverseze fiecare dintre aceste poduri o dată și numai o dată.

Pentru a enunța fără echivoc cerința logică a problemei, soluțiile care implică fie

1. ajungerea pe o insulă sau într-o parte de oraș altfel decât trecând podurile, sau
2. accesarea oricărui pod fără a-l traversa până la celălalt capăt 

sunt în mod explicit inacceptabile.

Euler a demonstrat că problema nu are soluție. Dificultatea cu care s-a confruntat a fost să dezvolte de o tehnică adecvată de analiză, și teste ulterioare, care să enunțe această afirmație cu rigoare matematică.

Analiza lui Euler

În primul rând, Euler a subliniat că alegerea drumului prin interiorul fiecărei porțiuni de oraș este irelevantă. Singura caracteristică importantă a unui traseu este șirul de poduri traversate. Acest lucru i-a permis să reformuleze problema în termeni abstracți (punând bazele teoriei grafurilor), eliminând toate caracteristicile, cu excepția listei de mase de uscat și podurile de legătură. În termeni moderni, a înlocuit fiecare masă de uscat cu un „nod” sau vârf abstract, iar fiecare pod cu o legătură abstractă, o „muchie”, care servește doar pentru a înregistra care pereche de noduri (mase de uscat) este conectată prin pod. Structura matematică rezultată se numește graf.

→ →

Deoarece numai informațiile de conectare sunt relevante, forma reprezentării picturale a grafului poate fi distorsionată în orice mod, fără a schimba graful în sine. Numai existența (sau absența) unei muchii între fiecare pereche de noduri este semnificativă. De exemplu, nu contează dacă muchiile trasate sunt drepte sau curbe, sau dacă un nod este la stânga sau la dreapta altui nod.

Apoi, Euler a observat că (cu excepția capetelor drumului), ori de câte ori se intră într-un nod de pe un pod, se iese din nod tot printr-un pod. Cu alte cuvinte, în timpul oricărui drum prin graf, numărul de intrări într-un nod neterminal este egal cu numărul de ieșiri. Acum, dacă fiecare pod este traversat exact o dată, rezultă că, pentru fiecare masă de uscat (cu excepția celor alese pentru început și sfârșit), numărul de poduri care duce în acea masă de uscat trebuie să fie par (jumătate dintre ele, în parcurgere, vor fi traversate „spre” masa de uscat; cealaltă jumătate, „dinspre” ea). Cu toate acestea, toate cele patru mase de uscat din problema inițială sunt atinse de un număr impar de poduri (unul este atins de 5 poduri, și fiecare dintre celelalte trei este atins de 3). Întrucât cel mult două mase de uscat pot servi ca puncte finale ale unui drum, propunerea de drum care să traverseze fiecare pod o singură dată conduce la o contradicție.

În limbaj modern, Euler a arătat că posibilitatea de parcurgere a unui graf, prin traversarea fiecărei muchii exact o dată, depinde de gradele nodurilor. Gradul unui nod este numărul de muchii care îl ating. Argumentul lui Euler arată că o condiție necesară pentru mersul pe jos în forma dorită este ca graful să fie conex și să aibă exact zero sau două noduri de grad impar. Această condiție se dovedește a fi și suficientă—rezultat enunțat de către Euler și demonstrat ulterior de Carl Hierholzer^⁠(d). Un astfel de drum este astăzi numit drum eulerian. Mai mult, dacă există noduri de grad impar, atunci orice drum eulerian va începe de la unul dintre ele și se va termina la celălalt. Întrucât graful corespunzător Königsbergului istoric are patru noduri de grad impar, el nu poate avea un drum eulerian.

O formă alternativă a problemei cere un drum care traversează toate podurile și ajunge în final în punctul de început. Un astfel de drum este numit „ciclu eulerian”. Un astfel de ciclu există dacă și numai dacă graful este conex și nu există niciun nod de grad impar. Toate ciclurile euleriene sunt și drumuri euleriene, dar nu toate drumurile euleriene sunt și cicluri euleriene.

Lucrarea lui Euler a fost prezentată la Academia din St. Petersburg pe 26 august 1735, și publicată sub titlul Solutia problematis ad geometriam situs pertinentis („Soluția unei probleme referitoare la geometria de poziție”), în revista Commentarii academiae scientiarum Petropolitanae în 1741.

Semnificația în istoria și filosofia matematicii

În istoria matematicii, soluția lui Euler a problemei podurilor din Königsberg este considerată a fi prima teoremă din teoria grafurilor și prima demonstrație adevărată în teoria rețelelor, un domeniu considerat astăzi, în general, o ramură a combinatoricii. Alte probleme de combinatorică de alte tipuri au fost analizate încă din antichitate.

În plus, recunoașterea de către Euler că informațiile-cheie sunt numărul de poduri și lista capetelor lor (mai degrabă decât poziția exactă) prevestea dezvoltarea topologiei. Diferența dintre distribuția reală și schema grafică este un bun exemplu al ideii că topologia nu se preocupă de forma rigidă a obiectelor.

Prin urmare, așa cum constata și Euler, „geometria de poziție” nu este despre „măsurători și calcule”, ci despre ceva mult mai general. Aceasta a pus sub semnul întrebării viziunea tradițională, cum că matematica este o „știință a cantității”. Deși această viziune se potrivește aritmeticii și geometriei euclidiene, ea nu se potrivește cu topologia și cu caracteristicile structurale mai abstracte studiate în matematica modernă.

Filosofii au observat că demonstrația lui Euler nu este despre o abstracție sau despre un model al realității, ci direct despre aranjamentul real al podurilor. Prin urmare, certitudinea demonstrației matematice se poate aplica direct la realitate.

Variante

Enunțul clasic al problemei, dat mai sus, folosește noduri neidentificate — adică sunt toate la fel, cu excepția modului în care sunt conectate. Există o variantă în care nodurile sunt identificate — fiecare nod primește un nume unic sau o culoare.

O variantă cu castele roșu și albastru, o biserica si un han.

Malul de nord al râului este ocupat de Schloß, sau „castelul”, Prințului Albastru; la sud, de cel al Prințului Roșu. Pe malul de est este Ritcherul podului, sau biserica; și pe o mică insulă în centru este un Gasthaus^⁠(d), sau „han”.

Se înțelege că problemele ar trebui să fie luate în ordine, și să se înceapă cu un enunț al problemei inițiale:

Cum era obiceiul printre orășeni, după câteva ore în Gasthaus, să încerce să meargă pe poduri, mulți s-au întors să mai bea ceva proclamându-și succesul. Cu toate acestea, niciunul nu a mai putut să repete isprava la lumina zilei.

Podul 8: Prințul Albastru, după ce a analizat sistemul de poduri al orașului prin teoria grafurilor, concluzionează că podurile nu pot fi parcurse. El pune la cale un plan ascuns de a construi un al optulea pod, astfel încât el să poată începe seara la Schloß, să parcurgă podurile, și să ajungă la Gasthaus să se laude cu victoria lui. Desigur, el vrea ca Prințul Roșu să nu poată face același lucru pornind de la Castelul Roșu. Unde va construi Prințul Albastru al optulea pod?

Podul 9: Prințul Roșu, înfuriat de soluția gordiană a confratelui său, vrea să construiască un nou pod, care să-i permită lui să înceapă la Schloß, să parcurgă podurile, și să ajungă la Gasthaus pentru a-i face în ciudă Prințului Albastru. Ca răzbunare suplimentară, confratele lui ar trebui să nu mai fie capabil să parcurgă podurile pornind de la Schloß și să ajungă la Gasthaus ca înainte. Unde va construi Prințul Roșu al nouălea pod?

Podul 10: Episcopul a privit furios această frenezie de construcții de poduri. Consideră ca a stricat mult Weltanschauungul orașului și, mai rău, a contribuit la proliferarea beției. El vrea să construiască un al zecelea pod care să permită tuturor locuitorilor să parcurgă podurile și să revină în propriile lor case. Unde va construi episcopul cel de al zecelea pod?

Soluții

Colorarea grafului

A opta muchie

Se reduce orașul, ca și mai înainte, la un graf. Se colorează fiecare nod. Ca și în problema clasică, nu există drum eulerian; colorarea nu afectează acest lucru. Toate cele patru noduri au un număr impar de muchii.

Podul 8: Drumuri euleriene sunt posibile dacă exact zero sau două noduri au un număr impar de muchii. Dacă avem 2 noduri cu un număr impar de muchii, drumul trebuie să înceapă la un astfel de nod și să se termine la celălalt. Deoarece există doar 4 noduri în problemă, soluția este simplă. Drumul dorit trebuie să înceapă la nodul albastru și să se termine la cel portocaliu. Astfel, se trasează o nouă muchie între celelalte două noduri. Deoarece fiecare din ele avea anterior un număr impar de muchii, acestea trebuie să aibă acum un număr par de muchii, care îndeplinesc toate condițiile. Aceasta este o schimbare în paritate^⁠(d) de un grad impar la unul par.

A 9-a muchie

A 10-a muchie

Podul 9: Al nouălea pod este ușor de plasat odată ce este rezolvată cerința celui de al optulea. Dorința este de a face castelul roșu punct de plecare și de a-l împiedica pe cel albastru să fie punct de plecare; nodul portocaliu rămâne la sfârșitul drumului și nodul alb rămâne neafectat. Pentru a schimba paritatea nodurilor roșu și albastru noduri, se trasează o nouă muchie între ele.

Podul 10: Al zecelea pod vine cu o cerință ușor diferită. Episcopul dorește ca fiecare cetățean să se întoarcă la punctul de plecare. Acesta este un ciclu eulerian și necesită ca toate nodurile să fie de grad par. După rezolvarea celui de al 9-lea pod, nodurile roșu și portocaliu au grad impar, iar paritatea acestora trebuie să fie schimbată prin adăugarea unei noi muchii între ele.

Podurile 8, 9, și 10

Starea actuală a podurilor

Hartă modernă a Kaliningradului. Locațiile celorlalte poduri sunt evidențiate cu verde, în timp ce cele distruse sunt evidențiate în roșu.

Două dintre cele șapte poduri inițiale nu au supraviețuit bombardamentelor Königsbergului în al Doilea Război Mondial^⁠(d). Altele două au fost ulterior demolate și înlocuite cu o autostradă modernă. Au mai rămas alte trei poduri, deși numai două dintre ele sunt din vremea lui Euler (unul a fost reconstruit în anul 1935). Astfel, actualmente există în Kaliningrad cinci poduri care au făcut parte din problema lui Euler.

În termeni de teoria grafurilor, două dintre noduri au acum gradul 2, iar alte două au gradul 3. Prin urmare, astăzi este posibil un drum eulerian, dar acesta trebuie să înceapă pe o insulă și să se termine pe cealaltă.

Universitatea Canterbury^⁠(d) din Christchurch, Noua Zeelandă, are încorporat un model al podurilor într-o pajiște între fosta Bibliotecă de Științe Fizice și Clădirea Erskine, unde își au sediul Departamentele de Matematică, Statistică și Informatică. Râurile sunt înlocuite cu scurte tufișuri și pe insula centrală se află o piatră Stone lantern^⁠(d). Institutul de Tehnologie Rochester a încorporat problmea în pavajul din fața Gene Polisseni Center^⁠(d), o arenă de hochei pe gheață, deschisă în 2014.

Comparație între graficele celor șapte poduri din Konigsberg (sus) și puzzle-ul Cinci-room-uri (partea de jos). Numerele indica numărul de muchii conectate la fiecare nod. Noduri cu un număr impar de muchii sunt umbrite de portocale.

Vezi și

• Drum eulerian
• Glosar de teoria grafurilor
• Drum hamiltonian

Legături externe

• Kaliningrad și problema podurilor din Königsberg la Convergence Arhivat în 8 august 2013, la Wayback Machine.
• Publicația inițială a lui Euler (în limba latină)
• Podurile din Königsberg Arhivat în 18 ianuarie 2007, la Wayback Machine.
• Cum ne ajută podurile din Königsberg să înțelegem creierul
• Problema podurilor din Königsberg a lui Euler Arhivat în 1 iunie 2012, la Wayback Machine. la departamentul de matematică de la Contra Costa College
• Pregel – o unealtă grafică de la Google numită după această problemă