Elemente de Teoria Grafurilor

INTRODUCERE IN TEORIA GRAFURILOR

Exista situatii când oameni ce lucreaza în diverse domenii ajung la reprezentarea unor cazuri concrete prin desenarea unor puncte, cu o anumita semnificatie, unite prin segmente si care simbolizeaza o anumita relatie ce exista între acele puncte. Punctele au fost denumite noduri, iar segmentele au fost denumite arce, iar o astfel de reprezentare se numeste graf. Am pomenit mai sus de ramuri diverse unde apare notiunea de graf. Voi da cateva exemple:

- in chimie: reprezentarea unei molecule este un graf (vezi fig.1.1)

fig.1.1-Reprezentarea grafica a câtorva molecule

- in biologie, de exemplu repreyentarea plana a moleculei de ADN poate fi considerata un graf infinit (de fapt are o lungime finita,dar foarte mare) ;

- reteaua de drumuri dintr-o tara, spre exemplu, impreuna cu localitatile pe care le unesc formeaza un graf;

- un circuit electric este de fapt un graf (aceasta reprezentare l-a ajutat pe Kirkhoff în experimentele sale fizice);

- calculatoarele aflate legate într-o retea formeaza de asemenea un graf;

De fapt notiunea de graf îsi are originea în lucrarile lui Euler care

în 1976 studia celebra problema a celor 7 poduri din Königsberg reprezentata in

Fig.1.2 Problema podurilor din Königsberg

Problema cere aflarea unui drum ce parcurge toate podurile o singura data si se ajunge în punctul din care s-a plecat. Euler a demonstrat ca problema nu are solutie. Astazi teoria grafurilor îsi gaseste utilitatea în multe ramuri ale matematicii, economiei etc. În continuare voi prezenta câteva notiuni teoretice de baza despre grafuri.

Definitia 1.1

Se numeste graf o pereche G=( X, U ) formata dintr-o multime X de elemente numite vârfuri si dintr-o familie U de perechi de vârfuri ale carei elemente se numesc muchii. În continuare vom presupune ca graful G este finit, adica multimea X={x1,x2,…,xn} este finita si familia U=(u1,u2,…,um) a muchiilor este un sir finit. Daca sirul U al muchiilor este o multime de perechi, adica UÍX´X graful se numeste graf orientat. (figura 1.4),iar muchiile le vom numi in acest caz arce. Daca un graf nu are bucle si nu contine doua muchii egale (în sensul teoriei multimilor), iar familia U este o submultime a lui P2(X) (multimea partilor cu doua elemente ale lui X) graful se numeste graf neorientat.(figura 1.3)