Ministerul Educaiei al Republicii MoldovaUniversitatea Tehnic a MoldoveiCatedra de Matematic Superioar

Raportla matematica discretTema: Pstrarea grafului n memoria calculatorului

A efectuat: st. gr.TI-143 Fiodor AlexandruA verificat: Dr. conf. univ. Ceban Cheorghe

Chiinu 2015

Lucrare de laborator 1. Tema: Pstrarea grafului n memoria calculatorului2.SCOPUL LUCRRII: Studierea metodelor de definire a unui graf: matrice de inciden, matrice de adiacen, liste; Elaborarea unor proceduri de introducere, extragere i transformare a diferitor forme de reprezentare intern a grafurilor cu scoaterea rezultatelor la display i imprimant.

3. Exemplu:F(x1) = { x3}, F(x2) = {x6}, F(x3) = {x2 }, F(x4) = { x5}, F(x5) = {x5 } ,F(x6) = {x4}

X4X2

X5 X1

X3

4. NOTE DE CURSMetode de reprezentare a grafuluiExist trei metode de baz de definire a unui graf:1. Matricea de inciden;2. Matricea de adiacen;3. Lista de adiacen (inciden).Vom face cunotin cu fiecare dintre aceste metode.Matricea de incidenEste o matrice de tipul mxn, n care m este numrul de muchii sau arce (pentru un graf orientat), iar n este numrul vrfurilor. La intersecia liniei i cu coloana j se vor considera valori de 0 sau 1 n conformitate cu urmtoarea regul: 1 - dac muchia i este incident cu vrful j (dac arcul i "intr" n vrful j n cazul unui graf orientat); 0 - dac muchia (arcul) i i vrful j nu sunt incidente; -1 - numai pentru grafuri orientate, dac arcul i "iese" din vrful j.

x1

x2

x3

x4

x5

u1-11000

u2-10100

u30-1010

u4000-11

u500020

u60

0

-1

10

Fig. 3

Este uor de observat c aceast metod este de o eficacitate mic n sensul utilizrii memoriei calculatorului: fiecare linie conine doar dou elemente diferite de zero (o muchie poate fi incident cu nu mai mult de dou vrfuri).Matricea de adiacenEste o matrice ptrat nxn, aici n este numrul de vrfuri. Fiecare element poate fi 0, dac vrfurile respective nu sunt adiacente, sau 1, n caz contrar. Pentru un graf fr bucle putem observa urmtoarele: diagonala principal este format numai din zerouri; pentru grafuri neorientate matricea este simetric fa de diagonala principal.x1x2x3x4x5

x101100

x200010

x300010

x400011

x500000

Fig. 4

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 faciliti algoritmului respectiv.Pentru pstrarea grafurilor n memoria calculatorului (n deosebi, memoria extern) se va utiliza una din posibilitile de mai jos.

Lista de adiacen i lista de incidenLista de adiacen este o list cu n linii (dup numrul de vrfuri n), n linia cu numrul i vor fi scrise numerele vrfurilor adiacente cu vrful i.Lista de inciden se definete analogic cu deosebirea c n linia i vor fi scrise numerele muchiilor (arcelor) incidente cu vrful i.Reprezentarea grafurilor prin intermediul acestor liste permite utilizarea mai eficace a memoriei calculatorului, ns aceste forme sunt mai complicate att n realizare, ct i n timpul procesrii. Pentru a lua n consideraie lungimea variabil a liniilor vor fi utilizate variabile dinamice i pointeri.Vom exemplifica pentru un graf cu n vrfuri. Deoarece fiecare element al listei conine numere de vrfuri este evident s considerm c vom avea un ir de variabile dinamice de tip INTEGER care se vor afla n relaia respectiv de precedare (succedare). Aceast relaie se va realiza prin pointeri, unii mpreun cu variabila de tip ntreg n nregistrarea (Pascal: record). Pentru a pstra indicatorii de intrare n aceste iruri se va folosi un tablou unidimensional de indicatori de lungime n. n calitate de simbol de terminare a irului se va utiliza un simbol care nu a fost folosit la numeraia vrfurilor (de exemplu 0), care va fi introdus n calitate de variabil de tip ntreg al ultimului bloc.De exemplu, lista de adiacen (fig.1.1):1 : 2_3 _02 : 4_03 : 4_ 04 : 4_5_ 05 : 0

5.Programul in C:#include #include #include

#define p1 printf("Introdu numarul de arce: ");#define s1 scanf("%d",&u);#define p2 printf("Introdu numarul de virfuri: ");#define s2 scanf("%d",&x);

typedef struct{ int inc; int sfr;}arc;//functia pentru alocarea a memoriei dinamiceint** aloc(int n,int m){int **vect=NULL;int i; vect=(int**)malloc(n*sizeof(int*)); if(vect==NULL) return vect; for(i=0;i