Șapte poduri din Königsberg - Seven Bridges of Königsberg
Cele șapte poduri din Königsberg sunt o problemă istorică notabilă în matematică. Rezoluția sa negativă a lui Leonhard Euler în 1736 a pus bazele teoriei grafurilor și a prefigurat ideea topologiei .
Orașul Königsberg din Prusia (acum Kaliningrad , Rusia ) a fost așezat pe ambele maluri ale râului Pregel și a inclus două mari insule - Kneiphof și Lomse - care erau conectate între ele sau cu cele două porțiuni continentale ale orașului, prin șapte poduri. Problema a fost de a concepe o plimbare prin oraș care să traverseze fiecare dintre aceste poduri o singură dată.
Prin specificarea sarcinii logice fără echivoc, soluții care implică oricare dintre acestea
- - să ajungă la o altă insulă sau la un continent, altul decât prin unul dintre poduri sau
- accesând orice pod fără a trece la celălalt capăt al acestuia
sunt explicit inacceptabile.
Euler a dovedit că problema nu are nicio soluție. Dificultatea cu care s-a confruntat a fost dezvoltarea unei tehnici adecvate de analiză și a testelor ulterioare care au stabilit această afirmație cu rigoare matematică.
Analiza lui Euler
În primul rând, Euler a subliniat că alegerea traseului în interiorul fiecărei mase terestre este irelevantă. Singura caracteristică importantă a unui traseu este secvența de poduri traversate. Acest lucru i-a permis să reformuleze problema în termeni abstracte (punând bazele teoriei graficelor ), eliminând toate caracteristicile, cu excepția listei maselor de pământ și a podurilor care le leagă. În termeni moderni, unul înlocuiește fiecare masă terestră cu un „ vârf ” sau nod abstract , iar fiecare pod cu o conexiune abstractă, o „ margine ”, care servește doar pentru a înregistra ce pereche de vârfuri (mase terestre) este conectată prin acel pod. Structura matematică rezultată este un grafic .
→
→
Deoarece numai informațiile de conexiune sunt relevante, forma reprezentărilor picturale ale unui grafic poate fi distorsionată în orice mod, fără a modifica graficul în sine. Doar existența (sau absența) unei margini între fiecare pereche de noduri este semnificativă. De exemplu, nu contează dacă marginile desenate sunt drepte sau curbate sau dacă un nod este la stânga sau la dreapta altui.
Apoi, Euler a observat că (cu excepția punctelor finale ale mersului), ori de câte ori se pătrunde într-un vârf printr-un pod, se părăsește vârful prin un pod. Cu alte cuvinte, în timpul oricărei plimbări în grafic, de câte ori se intră într-un vârf non-terminal este egal cu câte ori se părăsește. Acum, dacă fiecare pod a fost parcurs exact o singură dată, rezultă că, pentru fiecare masă terestră (cu excepția celor alese pentru start și sosire), numărul de poduri care ating această masă terestră trebuie să fie egal (jumătate dintre ele, în traversare specială, va fi parcursă „spre„ masa de pământ; cealaltă jumătate, „departe” de ea). Cu toate acestea, toate cele patru mase terestre din problema inițială sunt atinse de un număr impar de poduri (unul este atins de 5 poduri, iar fiecare dintre celelalte trei este atins de 3). Deoarece, cel mult, două mase terestre pot servi drept puncte finale ale unei plimbări, propunerea unei plimbări care traversează fiecare pod duce odată la o contradicție.
În limbajul modern, Euler arată că posibilitatea unei plimbări printr-un grafic, care traversează fiecare margine exact o dată, depinde de gradele nodurilor. Gradul unui nod este numărul de margini care îl ating. Argumentul lui Euler arată că o condiție necesară pentru mersul formei dorite este ca graficul să fie conectat și să aibă exact zero sau două noduri de grad impar. Această condiție se dovedește, de asemenea, a fi suficientă - un rezultat afirmat de Euler și dovedit ulterior de Carl Hierholzer . O astfel de plimbare este acum numită o cale euleriană sau plimbare Euler în onoarea sa. Mai mult, dacă există noduri de grad impar, atunci orice cale euleriană va începe la unul dintre ele și se va termina la cealaltă. Deoarece graficul corespunzător istoricului Königsberg are patru noduri de grad impar, nu poate avea o cale euleriană.
O formă alternativă a problemei solicită o cale care traversează toate podurile și are, de asemenea, același punct de pornire și sfârșit. O astfel de plimbare se numește circuit eulerian sau tur Euler . Un astfel de circuit există dacă și numai dacă graficul este conectat și nu există deloc noduri de grad impar. Toate circuitele euleriană sunt, de asemenea, căi euleriene, dar nu toate căile euleriene sunt circuite euleriene.
Lucrarea lui Euler a fost prezentată Academiei din Sankt Petersburg la 26 august 1735 și 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. Este disponibilă în traducere în limba engleză în The World of Mathematics de James R. Newman .
Semnificație în istoria și filozofia matematicii
În istoria matematicii , soluția lui Euler a problemei podului Königsberg este considerată a fi prima teoremă a teoriei graficelor și prima dovadă adevărată în teoria rețelelor, un subiect considerat acum în general ca o ramură a combinatoricii . Probleme combinatorii de alte tipuri au fost luate în considerare încă din antichitate.
În plus, recunoașterea lui Euler că informațiile cheie au fost numărul de poduri și lista punctelor finale (mai degrabă decât pozițiile lor exacte) au prezis dezvoltarea topologiei . Diferența dintre aspectul real și schema grafică este un bun exemplu al ideii că topologia nu este preocupată de forma rigidă a obiectelor.
Prin urmare, după cum a recunoscut Euler, „geometria poziției” nu se referă la „măsurători și calcule”, ci la ceva mai general. Aceasta a pus sub semnul întrebării viziunea aristotelică tradițională conform căreia matematica este „știința cantității ”. Deși această viziune se potrivește geometriei aritmetice și euclidiene, nu se potrivea topologiei și caracteristicilor structurale mai abstracte studiate în matematica modernă.
Filosofii au observat că dovada lui Euler nu este despre o abstractizare sau un model de realitate, ci direct despre aranjarea reală a podurilor. Prin urmare, certitudinea dovezilor matematice se poate aplica direct realității. Dovada este, de asemenea, explicativă, oferind informații despre motivul pentru care rezultatul trebuie să fie adevărat.
Starea actuală a podurilor
Două dintre cele șapte poduri originale nu au supraviețuit bombardamentului de la Königsberg în cel de-al doilea război mondial . Alte două au fost ulterior demolate și înlocuite cu o autostradă modernă. Celelalte trei poduri rămân, deși doar două dintre ele sunt din timpul lui Euler (unul a fost reconstruit în 1935). Astfel, începând cu 2021, există cinci poduri pe aceleași locuri care au fost implicate în problema lui Euler. În ceea ce privește teoria graficelor, două dintre noduri au acum gradul 2, iar celelalte două au gradul 3. Prin urmare, o cale euleriană este acum posibilă, dar trebuie să înceapă pe o insulă și să se termine pe cealaltă.
Universitatea din Canterbury din Christchurch a încorporat un model de poduri într - o zonă de iarbă între vechea fizică biblioteconomie și clădirea Erskine, găzduind Departamentele de Matematică, Statistică și Informatică. Râurile sunt înlocuite cu tufișuri scurte, iar insula centrală are un tōrō de piatră . Institutul de Tehnologie Rochester a încorporat puzzle-ul în trotuarul din fața Centrului Gene Polisseni , o arenă de hochei pe gheață care a fost deschisă în 2014.
Vezi si
- Calea euleriană
- Puzzle cu cinci camere
- Glosar al teoriei graficelor
- Calea hamiltoniană
- Joc Icosian
- Apă, gaz și electricitate
Referințe
linkuri externe
- Kaliningrad și problema podului Konigsberg la convergență
- Publicația originală a lui Euler (în latină)
- Podurile din Königsberg
- Cum ajută podurile din Königsberg să înțeleagă creierul
- Problema Podurilor lui Königsberg a lui Euler la Departamentul de Matematică Colegiul Contra Costa
- Pregel - Un instrument de graficare Google numit după această problemă
- [1] Problema graficului actual
Coordonate : 54 ° 42′12 ″ N 20 ° 30′56 ″ E / 54,70333 ° N 20,51556 ° E