Problema podurilor Königsberg

Harta orașului Königsberg din vremea lui Euler, care arată contextul real al orașului, evidențiind râul Pregel și podurile sale

Problema celor șapte poduri din Königsberg este o problemă inspirată de un oraș real și de o situație concretă ^[1] . Königsberg , cândva în Prusia de Est și acum o exclavă rusă pe Marea Baltică cunoscută sub numele de Kaliningrad , este traversată de râul Pregel și afluenții săi și are două insule mari care sunt legate între ele și de cele două zone principale ale orașului prin șapte poduri ^[1] .

De-a lungul secolelor s-a ridicat întrebarea de mai multe ori dacă este posibil cu o plimbare să urmezi o cale care traversează fiecare pod o singură dată ^[1] . În 1736 Euler s-a confruntat cu această problemă, arătând că mersul ipotetic nu era posibil ^[1] .

Nu pare să aibă un fundament istoric, ci mai degrabă să fie o legendă urbană , afirmația că în jurul anului 1750 cetățenii bogați din Königsberg se plimbau în jurul orașului lor duminica, încercând în zadar să rezolve problema.

Setarea și soluția lui Euler

Euler are meritul de a fi formulat problema în termenii teoriei graficelor , făcând abstracție de la situația specifică a Königsberg; în primul rând a eliminat toate aspectele contingente cu excepția zonelor urbane delimitate de brațele râului și de podurile care le leagă; în al doilea rând, el a înlocuit fiecare zonă urbană cu un punct, numit acum vârf sau nod, și fiecare pod cu un segment de linie, numit margine , arc sau legătură.

→ →

Reprezentare

Euler a reprezentat aspectul celor șapte poduri care uneau cele patru zone majore ale orașului cu tot atâtea linii, ca în prima imagine. Rețineți că trei poduri pornesc (și ajung) de la nodurile A, B și D; de la nodul C, pe de altă parte, cinci poduri. Acestea sunt gradele nodurilor: respectiv, 3, 3, 5, 3.
Înainte de a ajunge la o concluzie, Euler a ipotezat diferite situații de zone și poduri (noduri și conexiuni): cu patru noduri și patru poduri este posibil să porniți, de exemplu, de la A și să reveniți prin toate podurile o singură dată. Gradul fiecărui nod este un număr par. Dacă, pe de altă parte, pornim de la A pentru a ajunge la D, fiecare nod este de grad egal cu excepția a două noduri, de grad impar (unul). Pe baza acestor observații, Euler a formulat următoarea teoremă:

Orice grafic este fezabil dacă și numai dacă are toate nodurile de grad par, sau două dintre ele sunt de grad impar; pentru a urmări un grafic „posibil” cu două noduri de grad impar, este necesar să porniți de la unul dintre ele și se va termina pe celălalt nod impar .

Euler în vârstă de 49 de ani, pictat de Emanuel Handmann (1756)

Prin urmare, este imposibil să parcurgeți Königsberg așa cum este cerut de teză, deoarece toate nodurile sunt de grad ciudat.

Trebuie remarcat faptul că teoria graficelor are legături strânse cu topologia : forma unui grafic, sau mai degrabă a unei reprezentări a unui grafic sau a variantei acestuia (vezi graficul îmbogățit ) poate fi modificată prin deplasarea vârfurilor și distorsionarea liniilor care le leagă, pentru a menține legăturile efective. Nu contează dacă o legătură este dreaptă sau curbată sau dacă un vârf este pe o parte sau pe cealaltă în legătură cu o conexiune de vârfuri învecinate.

Euler a demonstrat că pentru orice grafic este posibilă o cale cu caracteristicile dorite dacă și numai dacă graficul nu are vârfuri (punctele din reprezentarea graficului) la care se ajunge printr-un număr impar de muchii. O astfel de cale se numește circuitul eulerian . Deoarece graficul Königsberg are patru astfel de vârfuri, calea nu există.

Dacă renunțați la cerința ca punctul de plecare și punctul de încheiere să coincidă, atunci nu pot exista sau două vârfuri atinse de un număr impar de margini. O astfel de cale se numește calea euleriană .

Dintre graficele eulerianne ne amintim cu toții grafice complete de ordin ciudat, steaua lui David și cimitirele lui Allah. Niciunul dintre graficele complete în ordine pare nu este eulerian.

Pentru o examinare matematică a problemei, a se vedea. Multigraf eulerian .

Importanța în istoria matematicii

În istoria matematicii, problema podului Königsberg este una dintre primele probleme ale teoriei graficelor discutate formal; poate fi, de asemenea, considerată una dintre primele probleme legate de topologie. Pe de altă parte, nu poate fi considerată una dintre primele probleme de combinatorică , un alt domeniu al matematicii la care se referă teoria graficelor, întrucât primele probleme combinatorii au fost abordate cu câteva secole înainte de secolul al XVIII-lea (vezi Istoria combinatoriei ).

Comparația între chiar o hartă schematică a lui Königsberg și reprezentarea graficului care schematizează problema constituie un bun indiciu al ideii că topologia nu depinde de forma rigidă a obiectelor pe care le studiază.

Variații

Afirmația inițială a problemei se referă la vârfuri neidentificate, adică caracterizate numai prin conexiunile lor. Pe de altă parte, există variații pe această temă care pot fi utile pentru introducerea problemei în predare și care se preocupă de identificarea vârfurilor grafului cu personaje și roluri.

Prin urmare, se specifică faptul că pe malul nordic al orașului se află Schloß , castelul prințului albastru pentru cei care nu cunosc încă cuvântul german și că pe malul sudic se află cel al prințului roșu; cei doi prinți sunt frați, dar este cazul fraților cuțit; pe insula de est se află Kirche , biserica, sediul Episcopului; în cele din urmă pe insula centrală există un Gasthaus , o tavernă. După cum vom vedea mai târziu, relațiile dintre notabili ai orașului, printre care și gazda trebuie să fie luată în considerare în mod realist, nu sunt întotdeauna ușoare.

Urmărind cu atenție ordinea cronologică a faptelor, trebuie amintit că mulți locuitori ai orașului obișnuiau să stea mult timp în Gasthaus seara și, prin urmare, încearcă întreprinderea numită trecerea podurilor ; unii s-au întors apoi pentru a-și sărbători succesul cu alte libații, dar fără să poată explica într-un mod satisfăcător cum, spun ei, au reușit și fără să știe cum să repete mersul în lumina zilei.

Al optulea pod al Prințului Albastru

Prințul Albastru, după ce a analizat sistemul podurilor orașului cu ajutorul teoriei graficelor, devine convins de imposibilitatea traversării podurilor. Apoi decide să construiască în secret un al optulea pod care să-i permită să traverseze podurile seara începând de la Schloß-ul său și terminând la Gasthaus unde se poate lăuda cu succesul său; și, de asemenea, se asigură că Prințul Roșu nu poate face același lucru pornind de la Schloß.

Unde construiește Prințul Albastru cel de-al optulea pod?

Al nouălea pod al Prințului Roșu

Prințul Roșu, nedumerit de mișcarea fratelui său, își dă seama că nu poate reacționa decât după ce a studiat teoria graficelor; după un studiu atent, el decide și el să construiască în secret un alt pod care să-i permită să traverseze podurile pentru a ajunge la Gasthaus de la Schloß-ul său și aici să ia o plimbare pe fratele său căruia devine imposibil să traverseze podurile în felul său .

Unde construiește prințul roșu cel de-al nouălea pod?

Cel de-al zecelea pod episcopal

Episcopul a trebuit să urmărească disputa orașului scump cu o iritare crescândă. A dus la formarea a două facțiuni cu probleme și a crescut numărul de vizitatori excesivi la Gasthaus, în detrimentul păcii publice. Așa că și el, după un studiu atent al teoriei graficelor, decide să construiască un al zecelea pod care să le permită tuturor cetățenilor să traverseze toate podurile și să se întoarcă la casele lor printre afecțiunile liniștite ale familiei.

Unde construiește Episcopul cel de-al zecelea pod?

Soluții

Punctele a opta, a noua și a zecea

Prin reducerea orașului, ca mai sus, la un grafic și colorarea fiecărui nod ca în problema clasică, nu este posibilă inițial o plimbare Euler . Toate cele patru noduri au un număr impar de margini .

Graficul colorat

A opta margine

Al optulea pod al Prințului Albastru

Mersurile Euler sunt posibile dacă exact 2 noduri au un număr impar de margini, care sunt exact nodurile inițiale și finale ale mersului. Deoarece problema are doar 4 noduri, toate cu un nivel impar, ne putem imagina începând mersul la nodul albastru și terminându-l la nodul portocaliu; pentru a garanta rezolvarea problemei, un număr par de margini trebuie să convergă pe celelalte două noduri. Adăugând o legătură între ele, ne găsim în condițiile teoremei lui Euler.

A noua margine

A zecea margine

Al nouălea pod al Prințului Roșu

S-a rezolvat problema optului pod, cel de-al nouălea pod prezintă o soluție ușoară. Se solicită utilizarea nodului roșu ca punct de plecare și a portocaliului ca finisaj. Pentru a schimba paritatea nodurilor roșii și albastre, trageți o altă margine între cele două.

Al zecelea pod episcopal

Cel de-al zecelea pod merge într-o direcție ușor diferită. Episcopul dorește ca fiecare cetățean să se întoarcă la punctul de plecare. Aceasta este o cale euleriană și necesită ca toate nodurile să fie de un nivel egal. După soluția celui de-al nouălea pod, nodurile roșii și portocalii sunt de grad ciudat, așa că trebuie schimbate adăugând o nouă margine între ele.