Matematică discretă

Lucrarea de laborator Nr. 1

Tema:Pastrarea grafurilor in memoria calculatorului

Scopul lucrarii: Studierea metodelor de definire a unui graf:matrice de incidenta, matrice de adiacenta,liste. Elaborarea unor procedure de introducere, extragere si transformare a diferitelor forme de reprezentare interna a grafurilor cu scoaterea rezultatelor la display si imprimanta.

Consideratii Teoretice:

Anul 1736 este considerat pe buna dreptate de inceput pentru teoria grafurilor. In acel an L. Euler a rezolvat problema despre podurile din Konigsberg,stabilind criteriul de existent in grafuri a unui circuit special,denumit astazi ciclu ciclu Euler.Avindusi inceputurile in rezolvarea unor jocuri distractive.astazi teoria grafurilor s-a transformat intr-un aparat simplu si accesibil, care permite rezolvarea unui cerc larg de probleme. Sub forma de grafuri pot fi reprezentate sisteme de drumuri si circuite electrice, harti geografice si molecule chimice, relatii dintre oameni si grupuri de oameni.

Teoria grafurilor a devenit o parte componenta a aparatului matematic al ciberneticii,limbajul matematicii discrete.

Def. Grafului

Se numeste graf ansamblu format dintr-o multime finite X si o aplicatie F a lui X in X. Se noteaza G=(X,F). Numarul elementelor multimilor X determina ordinal grafului finit. Daca card X=n, graful G=(X,F) se numeste graf finit de ordinul n. Elementele multimii X se numesc varfurile grafului. Geometric, varfurile unui graf le reprezentam prin puncte sau cerculete. Perechea de varfuri (x,y) se numeste arc varful x se numeste originea sau extremitatea initiala a arcului (x,y) iar varful y se numeste extremitatea finala sau terminal. Un arc (x,y) il reprezentam geometric printr-o sageata orientate de la varful x la varful y.

Daca un varf nu este extremitatea nici unui arc el se numeste varf izolat, iar daca este extremitatea a mai mult de doua arce- nod. Un arc (x,y) pentru care extremitatea initiala coincide cu cea finala se numeste bucla.Arcele unui graf le mai notam si cu u1,u2,..., iar multimea arcelor grafului o noatam cu U.

Doua arce se numesc adiacente daca sunt distncte si au o extremitate comuna.Doua varfuri se numesc adiacente daca sunt distinct si sunt unite prtr-un arc.

Un arc (x,y) se spune ca este incident cu virful x spre exterior si este incident cu varful y spre interior.

Exista 3 metode de baza de definire a unui graf:

1. Matricea de incidenta;

2. Matricea de adiacenta;

3. Lista de adiacenta(incidenta).

Vom lua cunostinta cu fiecare dintre aceste metode.

Matricea de incidenţă

Este o matrice de tipul mxn, în care m este numărul de muchii sau arce (pentru un graf orientat), iar n este numărul vârfurilor. La intersecţia liniei i cu coloana j se vor considera valori de 0 sau 1 în conformitate cu următoarea regulă:

• 1 - dacă muchia i este incidentă cu vârful j (dacă arcul i "intră" în vârful j în cazul unui graf orientat);

• 0 - dacă muchia (arcul) i şi vârful j nu sunt incidente;

• -1 - numai pentru grafuri orientate, dacă arcul i "iese" din vârful j.

Este uşor de observat că această metodă este de o eficacitate mică în sensul utilizării memoriei calculatorului: fiecare linie conţine doar două elemente diferite de zero (o muchie poate fi incidentă cu nu mai mult de două vârfuri).

Matricea de adiacenţă

Este o matrice pătrată nxn, aici n este numărul de vârfuri. Fiecare element poate fi 0, dacă vârfurile respective nu sunt adiacente, sau 1, în caz contrar. Pentru un graf fără bucle putem observa următoarele:

• diagonala principală este formată numai din zerouri;

• pentru grafuri neorientate matricea este simetrică faţă de diagonala principală.

După cum este lesne de observat şi în acest caz memoria calculatorului este utilizată nu prea eficace din care cauză matricea de adiacenţă ca şi matricea de incidenţă se vor utiliza de obicei doar în cazul în care se va rezolva o problemă concretă pentru care reprezentarea grafului în această formă aduce unele facilităţi algoritmului respectiv.Pentru păstrarea grafurilor în memoria calculatorului (în deosebi, memoria externă) se va utiliza una din posibilităţile de mai jos.

Lista de adiacenţă şi lista de incidenţă

Lista de adiacenţă este o listă cu n linii (după numărul de vârfuri n), în linia cu numărul i vor fi scrise numerele vârfurilor adiacente cu vârful i.

Lista de incidenţă se defineşte analogic cu deosebirea că în linia i vor fi scrise numerele muchiilor (arcelor) incidente cu vârful i.

Reprezentarea grafurilor prin intermediul acestor liste permite utilizarea mai eficace a memoriei calculatorului, însă aceste forme sunt mai complicate atât în realizare, cât şi în timpul procesării. Pentru a lua în consideraţie lungimea variabilă a liniilor vor fi utilizate variabile dinamice şi pointeri.

Exemplu am graf cu 5 varfuri si 7 arce ( vezi fig1)

u3

u6 u7

u2 u1

u4

u5

Fig.1 Reprezentarea grafica a grafului G

MI x1 x2 x3 x4 x5

u1 0 1 0 0 -1

u2 1 0 0 0 -1

u3 -1 1 0 0 0

u4 0 0 1 0 -1

u5 0 0 -1 1 0

u6 0 1 -1 0 0

u7 0 -1 0 1 0

MA x1 x2 x3 x4 x5

x1 0 1 0 0 0

x2 0 0 0 1 0

x3 0 1 0 1 0

x4 0 0 0 0 0

x5 1 1 1 0 0

Xi F(xi)

x1 2,0

x2 4,0

x3 2,4,0

x4 0

x5 1,2,3,0

Fig.1 Lista Fig.2 Matricea de adiacenta

Fig.3 Matricea de incidenta