 |
| Reușiți să-l desenați pe ninja fără să ridicați creionul de pe hârtie? |
Cunoașteți problemele de genul celei pe care v-am propus-o în dreapta. Am compus-o singur-singurel, cu speranța că vă va amuza atât pe dumneavoastră cât și pe copiii din dotare. Și am ales în mod deliberat s-o fac aparent complicată -- la final veți vedea că în realitate nicio problemă de felul ăsta nu este de fapt complicată.
Pentru a putea găsi soluția oricărei probleme de felul acesta trebuie să înțelegeți câteva noțiuni elementare din teoria grafurilor. Vor apărea câteva cuvinte specifice acestui domeniu, dar vă rog nu vă lăsați intimidați -- cuvintele or fi noi, dar ideile din spatele lor sunt extraordinar de simple, un copil de clasa I le înțelege fără probleme (i.e. fiică-mea).
Așadar, care-i treaba cu grafurile astea? Totul a început în secolul al XVIII-lea cu problema celor șapte poduri din Königsberg. La acea vreme în Prusia, Königsberg este actualul oraș Kaliningrad din Rusia (incidental, locația geografică a regiunii rusești Kaliningrad este deosebit de suprinzătoare). Königsberg a fost o vreme capitala Prusiei (înainte de a fi mutată la Berlin), ceea ce are probabil de-a face și cu numele german al orașului: muntele regelui. În paranteză fie spus apropo de König, presupun că Hopfen König ar fi trebuit să însemne Regele hameiului, însă în germană hamei este Echte Hopfen; Hopfen simplu este o clasă mult mai largă de plante, care include și cânepa indiană: Regele hașișului. Iar dinspre Berg avem o sumedenie de nume și cuvinte simpatice din punct de vedere etimologic: aisberg, numele evreiesc Goldberg (cu ce s-or fi ocupat?) și numele șăfului de la Facebook -- Zuckerberg (devine ironic doar pentru cei care au văzut filmul).
 |
| Cele șapte poduri din Königsberg |
Aici intră în scenă Leonhard Euler. Un elvețian născut în 1707, Euler a fost un megastar polivalent al matematicii și fizicii. Euler s-a uitat la metodele cu care încercau contemporanii săi să rezolve problema și a zis după cum urmează: Nah, pentru asta trebuie să inaugurez o nouă ramură a matematicii. Mai exact, Euler și-a dat seama că aceasta nu este o problemă geometrică, ci de alt fel.
Geometria este preocupată de forma și mărimea lucrurilor. Lucru de altfel evident atât din punct de vedere etimologic cât și din punct de vedere istoric. Geometria a fost inițial folosită exclusiv în scopuri cadastrale: oamenii aveau nevoie să știe cât pământ are fiecare, unde sunt hotarele unui teren și cât teren vând și cumpără. Cu alte cuvinte, geometria a început ca o unealtă pentru măsurat pământul (lucru care încă se vede cu ochiul liber și din punct de vedere etimologic).
 |
| Diagramă echivalentă a hărții podurilor din Königsberg |
Dimpotrivă, în problema podurilor din Königsberg nu contează forma fiecăreia dintre zonele delimitate de apă și legate de poduri. Ba mai mult, nici distanțele nu ne interesează: problema nu specifică vreo limită de timp în care trebuie parcurse podurile, așa că nu ne interesează dacă străbatem insula din mijloc de sus în jos sau de la dreapta la stânga -- ne interesează doar că odată ce am ajuns pe insulă putem folosi orice pod care leagă insula de celelalte zone. Prin urmare putem întoarce geometria cu susul în jos: zonele de pământ devin puncte, podurile devin linii care unesc punctele, iar altceva nu ne mai interesează.
 |
| Toate sunt la fel |
Ei bine, rezultatul acestei simplificări (diagrama de deasupra) este un graf. Grafurile sunt pur și simplu diagrame de acest fel, care indică numai în ce fel sunt unite vârfurile albastre folosind muchii negre. Teoria grafurilor nu este deloc preocupată de forma și dimensiunea obiectelor fizice pe care le reprezintă, ci numai de relația dintre vârfuri și muchii -- care se leagă cu care, atât (diagrama din stânga reprezintă de patru ori exact același graf: două vârfuri legate cu o muchie).
Revenind la problema noastră originală (cea cu ninja), constatăm că este perfect echivalentă cu problema podurilor; în cazul podurilor, restricția "nu ridica creionul de pe hârtie" este implicită ("nu te teleporta"), dar asta nu o face mai puțin relevantă (dimpotrivă).
 |
| Ce se întâmplă cu vârfurile pe care le străbatem |
Ei bine, ce a descoperit deșteptozaurul de Euler atunci când s-a aplecat asupra problemei cu podurile? Euler a încercat să nu se uite la problemă în ansamblul ei, ci s-o descompună în multe probleme mici și să vadă ce se întâmplă cu fiecare vârf atunci când încerci să-l străbați, independent de restul grafului (diagrama din dreapta).
Iar constatarea lui este la mintea cocoșului, dacă știi ce întrebare să-ți pui. Și anume, (schița (a)) Euler a descoperit că dacă vrei să treci printr-un vârf trebuie să ai pe unde să vii (săgeata roșie) și trebuie să ai pe unde să pleci (săgeata verde). Mai mult, dacă ai nevoie să revizitezi un vârf prin care ai trecut deja (schița (b)) atunci trebuie iarăși să ai pe unde să vii (săgeata roșie) și pe unde să pleci (săgeata verde). Singurele vârfuri pentru care nu este nevoie să-ți pui întrebări de felul ăsta sunt vârful de la care începi (schița (c)) și cel la care sfârșești (schița (d)).
 |
| Gradul vârfurilor |
În teoria grafurilor, numărul de muchii conectate la un vârf este numit gradul acelui vârf. Sună un pic intimidant, dar este exact ceea ce ați auzit; am inclus în stânga și o schiță ca să verificați că ați înțeles corect. O suită de muchii care pot fi parcurse una după alta (i.e. care au două câte două un vârf comun) se numește un drum. Iar un drum care parcurge toate muchiile unui graf câte o singură dată se numește drum eulerian (ghici de unde-i vine numele). Iar noi tocmai asta căutăm, atât pentru ninja cât și pentru Königsberg: un drum eulerian.
Însă dat fiind că am parcurs aceeași rută intelectuală ca și Euler, deja știm soluția: un graf are cel puțin un drum eulerian dacă și numai dacă toate vârfurile au grad par, sau dacă exact două au grad impar și celelalte au grad par. În cazul podurilor din Königsberg este evident că graful respectiv nu are cum să aibă vreun drum eulerian, dat fiind că toate cele patru vârfuri au grade impare.
Pentru ninja însă, ca și pentru toate celelalte probleme bine construite de același fel, este util nu doar să știm că au o soluție, ci să știm și cum ajungem la soluție. Iar algoritmul de rezolvare este exact atât de simplu cum vă așteptați să fie:
- Identificați cele două vârfuri cu grad impar;
- Porniți de la unul dintre ele;
- Aveți grijă să nu ajungeți prea devreme la celălalt (pentru că odată ce ajungeți la celălalt trebuie musai să vă opriți, indiferent dacă ați terminat sau nu restul desenului).
5 comentarii:
Daa..si acolo in Rusia, la Kaliningrad, s-a nascut si a trait toata vietisoara lui si musiu Kant!
Da -- și mulți alții
Si Kirchhoff tot acolo..interesant.
Mi-a sosit cartea cu zero...ma apuc de citit :)
Ah, super -- aștept impresii! :)
Trimiteți un comentariu