Grafuri euleriene



Adeseori suntem tentati sa credem simplul fapt de a traversa strazi sau poduri nu implica nici o idee deosebita. Iata însa ca exista o celebra problema de traversare în care singura idee implicata este aceea de “traversare”, problema celor sapte poduri din Königsberg. Aceasta banala si totusi foarte controversata problema a dus la aparitia si dezvoltarea teoriei grafurilor.

Problema se pune cam asa:
Orasul Königsberg era asezat pe coasta Marii Baltice, la gurile râului Pregel. Pe râu erau doua insule legate de tarmuri si între ele de sapte poduri ca în
figura 1.


Oamenii care cutreierau aceste insule au observat ca daca porneau de pe malul sudic al râului, nu puteau sa-si planifice plimbarea astfel încât sa traverseze fiecare pod o singura data. Se parea ca ori trebuia sa sara un pod ori sa-l traverseze de doua ori.
În anul 1735 Euler a descoperit ca nu mai are rost sa se încerce, propunând urmatoarea analiza a problemei, din punct de vedere matematic:
Sa consideram mai întâi insula estica (fig.2.):







sunt trei poduri care duc la ea. Deoarece se pleaca de pe malul sudic, înseamna ca se pleaca din afara insulei estice. Deoarece fiecare din cele trei traversari trebuie efectuate o singura data, plimbarea trebuiesa se termine pe insula estica.


Sa consideram acum insula vestica:
sunt cinci poduri care duc pe ea, iar cinci este din nou numar impar. Asadar plimbarea începe în afara

insulei, si deci trebuie sa se termine pe insula vestica.
Aceasta înseamna ca plimbarea se termina în doua locuri diferite simultan ceea ce e imposibil.
Solutia data de Euler este tipica pentru personalitatea si ingeniozitatea sa. Tot el a scris în anul 1736 prima lucrare de teorie a grafurilor despre problema acestor sapte poduri.

Un ciclu al unui graf G care contine toate muchiile lui G se numeste ciclu eulerian. Un graf G care are un ciclu eulerian se numeste graf eulerian.
Un graf G fara vârfuri izolate este eulerian daca si numai daca este conex