marți, 11 iunie 2013

Ninja la costum, sau o scurtă introducere în teoria grafurilor

 Înainte să vă las în compania soţului şi a postărilor lui respirând matematică, hai să vă spun de ce aţi vrea voi să citiţi cele ce urmează. Că urmează frate, i-am zis şi lui B. că e luuung postul ăsta şi că bietele mame îşi vor prinde urechile în el. Motivul este acela că la sfârşit o să puteţi să vă daţi mari în faţa copilului. Eh, ziceţi şi voi că nu e un motiv destul de bun. Ideea e că dacă citiţi cu atenţie cele de mai jos, o să ştiţi apoi să-i explicaţi odraslei cum dracu poate să rezolve problemele alea idioate în care i se cere să deseneze o chestie fără să ridice creionul de pe foaie. Atenţie, orice problemă de genul ăla. Adică citiţi chestia de mai jos o dată, încă o dată ca să ţineţi minte cum se face, chemaţi copilul mai aproape şi-i spuneţi: auzi beeei, vrei să te înveţe mă-ta cum să fii cel mai grozav din clasă şi să-i rupi gura lu' ăla de ia numai FB la mate şi blondei din spate care te împunge cu pixul în oră? Come to mama. Şi începeţi să-i arătaţi. Povestea ce precede metoda e pentru voi (mie aia mi-a plăcut, m-am simţit mai cultă la sfârşit), cealaltă parte e pentru copil. Dacă nu înţelegeţi nimic, vorbiţi cu soţul, eu nu am nicio vină.


Reușiți să-l desenați pe ninja fără
să ridicați creionul de pe hârtie?


Disclaimer: acesta este un guest post scris de soț.

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
În tot cazul, în secolul al XVIII-lea s-a pus întrebarea dacă există vreo rută posibilă care să traverseze fiecare pod câte o singură dată (pesemne matematicienii erau la vremea respectivă deosebit de receptivi la problemele poștașilor). Nu vă bateți capul să căutați o astfel de rută, nu există niciuna. Însă matematicienii nu se mulțumesc să constate că nimeni nu a găsit o soluție pentru problema podurilor din Königsberg, ci vor să și demonstreze în mod riguros acest lucru (nu doar să constate că până acum nimeni nu a găsit o soluție, ci să demonstreze că nu există nicio soluție posibilă) și, dacă se poate, să analizeze întreaga clasă a acestui tip de probleme, nu doar această problemă anume.

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 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:
  1. Identificați cele două vârfuri cu grad impar;
  2. Porniți de la unul dintre ele;
  3. 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).
Chestia interesantă este că nu există alte reguli. Nu trebuie să parcurgeți vârfurile de grad par în vreo ordine anume, atâta vreme cât aveți grijă să nu ajungeți prea devreme la vârful de final. Experimentați cu ninja -- aveți o sumedenie de drumuri euleriene la dispoziție.

5 comentarii:

Anonim spunea...

Daa..si acolo in Rusia, la Kaliningrad, s-a nascut si a trait toata vietisoara lui si musiu Kant!

B. spunea...

Da -- și mulți alții

Anonim spunea...

Si Kirchhoff tot acolo..interesant.

Anonim spunea...

Mi-a sosit cartea cu zero...ma apuc de citit :)

B. spunea...

Ah, super -- aștept impresii! :)

 
Copyright 2011-2017 Așa și-așa
Blog theme by BloggerThemes