Problema podurilor din Königsberg sau calea către teoria grafurilor

Tăbărcă Angelica Ioana, profesor, informatică,  Liceul Teoretic “Ion Heliade Rădulescu” Târgoviște
Tăbîrcă Nicolae Radu, profesor, informatică, Liceul Teoretic “Ion Heliade Rădulescu” Târgoviște

„Minds are like parachutes. They only function when they are open.” Sir James Dewar, Scientist (1877-1925)

De multe ori de-a lungul timpului s-a constatat că pornind de la o întâmplare simplă sau chiar de la o joacă, să se ajungă la descoperiri importante. Condiţia ca aceasta să se întâmple era ca observaţiile să fie făcute de cineva capabil să le interpreteze, să le analizeze, să le generalizeze, să extragă esenţa fenomenului şi apoi să prelucreze ştiinţific datele. În acest context se cunoaşte proverbul: “Nu e suficient să cadă un măr din pom, mai e necesar ca lângă pom să se afle Newton.”

În continuare vom relata o asemenea poveste ale cărei începuturi datează de pe la mijlocul secolului al XVIII-lea. În acele vremuri, în orăşelul Königsberg din Prusia Orientală, locuitorii găsiseră o distracţie destul de originală. Oraşul era străbătut de râul Pregel, care pe teritoriul oraşului se bifurca într-un mod interesant, două braţe ale râului se uneau, apoi se separau din nou, ca iar să se unească, formând o insulă, numită Kneiphof. Insula era legată de maluri cu cinci poduri iar pe fiecare braţ mai avea câte un pod.

Locuitorii se îndârjeau, în zilele de promenadă, să găsească un traseu care să străbată în circuit închis cele 7 poduri o singură dată. Neputând să găsească un astfel de traseu, distracţia s-a transformat în obsesie, apoi s-a apelat la matematicieni pentru găsirea soluţiei. Problema a fost analizată de renumitul matematician Leonhard Euler (1707-1783), născut în Elveţia, la Bâle, care a avut contribuţii hotărâtoare în toate domeniile matematicii cunoscute în epoca sa, precum şi în astronomie.

Euler a cercetat în mod ştiinţific problema şi a făcut o comunicare pe această temă la Academia din St. Petersburg în anul 1736, cu titlul: “Soluţia unei probleme ce aparţine geometriei de poziţie.” El a arătat că problema, în forma în care a fost prezentată, nu are soluţie. Aceasta nu depindea de lungimea, forma sau distanţa podurilor, ci numai de poziţia lor unul faţă de altul. Pentru a putea fi rezolvată problema, Euler a propus să se mai construiască un pod, lucru care s-a înfăptuit mult mai târziu, în secolul XX.

În esenţă problema s-a redus la trasarea unei reţele cu un anumit număr de noduri, printr-un traseu continuu, pornind dintr-un anumit punct, fără a trece de mai multe ori pe acelaşi traseu. A fost definit ordinul unui nod, adică numărul de linii care pleacă din acel nod. Astfel, reţeaua noastră avea 4 noduri, din care 3 de ordinul trei şi unul de ordinul cinci.

În urma analizării tuturor situaţiilor posibile, Euler a stabilit următoarele teoreme:

1.Orice reţea închisă are un număr par de noduri impare;

2.O reţea fără noduri impare este închisă;

3.Orice reţea închisă care are mai mult de două noduri impare nu se poate parcurge complet printr-o trăsătură continuă. Figurile închise cu două noduri impare se pot trasa printr-un parcurs continuu pornind dintr-unul din noduri.

Lucrarea lui Euler, amintită mai sus, se consideră a fi “actul de naştere” a unei noi ramuri a matematicii, numită topologie, care, definită pe scurt, studiază proprietăţile mulţimilor de puncte neschimbătoare faţă de unele transformări.

O mare varietate de divertismente matematice, jocuri, trucuri şi enigme de scamator sunt strâns legate de analiza topologică.

Începând cu Problema podurilor din Königsberg, studiul lanțurilor euleriene în grafuri și-a găsit numeroase aplicații. În matematica distractivă apar figuri asemănătoare celor de mai jos, punându-se problema desenării lor fără a ridica creionul de pe hârtie și fără a desena de mai multe ori aceeași linie.

Răspunsul unor astfel de probleme se obține simplu prin transformarea rețelei respective într-un graf și testarea proprietății euleriene.

De asemenea, o alta aplicație interesantă este studiul drumurilor și circuitelor euleriene în grafuri de Bruijn, care au numeroase și fascinante aplicații, de exemplu grafurile binare de Brujin pot simula obiecte din teoria sistemelor dinamice, cum ar fi atractorul Lorenz.

   

Problema podurilor din Königsberg, în scop didactic, însoțită de exemple și aplicații pentru elevii de liceu, profil real, specializarea matematică – informatică, și nu numai, este prezentată pe

site-ul wiki: http://informat21.wikispaces.com

Bibliografie:

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *

Acest sit folosește Akismet pentru a reduce spamul. Află cum sunt procesate datele comentariilor tale.