Cele șapte poduri din Königsberg

Oamenii care trăiau în secolul al XVIII-lea în orașul Königsberg s-au frământat multă vreme cu o ghicitoare: prin oraș curge râul Pregolea, care formează două insule. Peste acest râu duc spre insule în total șapte poduri. Se poate ca, într-o singură plimbare de duminică, să treci peste toate podurile, dar peste fiecare exact o dată? Să ne uităm cum erau așezate podurile peste râu:

Se poate ca plimbarea noastră să înceapă într-un anumit loc și să trecem peste toate podurile exact o dată? Putem încerca, începem din stânga jos și mergem în sus, apoi treptat spre dreapta, așa:

Vedem că am trecut peste șase din cele șapte poduri, unul dintre ele l-am ratat. Putem încerca alt traseu…

Din nou am trecut doar peste șase din cele șapte poduri ale orașului nostru Königsberg. Aproape că pare că nu se poate trece într-o singură plimbare peste fiecare pod exact o dată. Într-o zi a dat de această problemă cunoscutul matematician Leonhard Euler. Ce să spun „cunoscut” – Euler a fost o adevărată legendă a matematicii, după care este numit chiar și numărul e. Euler și-a zis că va desluși ghicitoarea. A început prin a nota insulele sau părțile orașului spre care și dinspre care duceau podurile:

Euler a făcut acum următorul raționament: dacă la o insulă duce un număr par de poduri, putem trece peste aceste poduri într-o singură plimbare, indiferent de unde începem. Pur și simplu, pe un pod ajungem pe insulă, pe altul plecăm – numărul podurilor peste care mai avem de trecut a scăzut cu doi. Ca să putem ajunge pe insulă pe un pod și să plecăm pe altul, ne trebuie două poduri. Dacă la o insulă duc șase poduri, vom vizita insula de trei ori. De exemplu, să ne închipuim că la insula B ar duce patru poduri, așa:

Atunci putem trece într-o singură plimbare de duminică peste toate podurile, oriunde am începe. Încearcă! În figură am marcat un traseu. Să ne închipuim însă că la insula B ar duce încă un pod, dinspre insula D:

Vedem că traseul pe care l-am ales nu ne permite să trecem peste toate podurile exact o dată. Ar trebui să ne întoarcem pe vreun pod pe insula B și apoi să trecem pe insula D. Dar putem alege un alt traseu. Putem începe plimbarea pe insula B și atunci reușim să trecem peste toate podurile exact o dată:

Plimbarea noastră a început pe insula B, am mers în sus spre zona A, apoi pe pod înapoi la B, la zona C, apoi iar la insula B și, în sfârșit, la insula D. Deci, dacă începem pe o insulă cu număr impar de poduri, putem trece peste toate podurile ei exact o dată. Sau putem merge exact invers – putem începe pe insula D și termina pe insula B.

Euler a observat astfel că, pentru a se putea trece peste toate podurile exact o dată, trebuie ca fie toate insulele să aibă un număr par de poduri, fie să existe două insule cu număr impar de poduri – pe una dintre ele începem, iar pe cealaltă terminăm. Toate celelalte insule trebuie să aibă un număr par de poduri. Dacă ne uităm la cele șapte poduri originale din Königsberg:

vedem că fiecare insulă are un număr impar de poduri! Insula A are 3, B are 5, C are 3 și D are tot 3. De aceea ghicitoarea nu are soluție – nu se poate trece peste toate cele șapte poduri exact o dată într-o singură plimbare de duminică. Dacă am dărâma oricare dintre poduri, deodată ghicitoarea ar avea soluție. Să dărâmăm, de exemplu, unul dintre podurile dintre insulele B și C:

Vedem că imediat insula B are 4 poduri, iar insula C două poduri. La insulele A și D numărul podurilor nu s-a schimbat. Avem deodată două insule cu număr par de poduri și două insule cu număr impar de poduri. Dacă începem plimbarea pe una dintre insulele cu număr impar de poduri, putem trece peste toate podurile exact o dată. În figură am început pe insula A și am terminat pe insula D.

Leonhard Euler a rezolvat astfel încă o problemă matematică celebră și a pus mai mult sau mai puțin bazele a ceea ce numim astăzi teoria grafurilor, iar în cinstea lui, un graf în care putem parcurge toate muchiile exact o dată se numește, în limbajul teoriei grafurilor, graf eulerian.