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

1

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

Fig.1 Lista Fig.2 Matricea de adiacenta

Fig.3 Matricea de incidenta

2

X3

X5

X4

X1

X2

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

Xi F(xi)x1 2,0x2 4,0x3 2,4,0x4 0x5 1,2,3,0

Sarcina de baza

1. Elaboram procedura introducerii unui graf în memoria calculatorului în formă de matrice de incidenţă, matrice de adiacenţă şi listă de adiacenţă cu posibilităţi de analiză a corectitudinii.

2. Elaboram proceduri de transformare dintr-o formă de reprezentare în alta.

3. Folosind procedurile menţionate elaboram programul care va permite: introducerea grafului reprezentat sub oricare din cele trei forme cu posibilităţi de corecţie a datelor; păstrarea grafului în memoria externă în formă de listă de adiacenţă;

extragerea informaţiei într-una din cele trei forme la imprimantă şi display(pentru detail vezi anexe)

Anexe

Fisierul arc.h

typedef struct{ int inc; int sfr;}arc;

int** aloc_vec(int n,int m);int** free_vec(int** vec,int n);

void intro_arc(arc* a,int u,int x);void print_arc(arc* a,int u);void modif_arc(arc* a,int u,int x,int mod);void add_arc(arc* a,int *u,int x,int u2);void del_arc(arc* a,int *u,int x,int u3);void add_virf(arc* a,int u,int *x,int x1);arc* dell_virf(arc* a,int u,int *x,int x2);

void matr_inc(arc* a,int** vec,int u,int x);void print_matr_inc(int** vec,int u,int x);

void matr_adc(arc* a,int** vec,int u,int x);void print_matr_adc(int** vec,int u,int x);

void list_ad(arc* a,int** vec,int u,int x);void print_list_ad(int** vec,int u,int x);

Fisierul functii.c

#include <stdio.h>#include <stdlib.h>#include "arc.h"

//Alocarea dinamica a matricelor.int** aloc_vec(int n,int m){

int** vec=NULL;

3

int i;vec=(int**)malloc(n*sizeof(int*));if(!vec){

printf("\a\nNu sa alocat memorie!\n"); system("pause"); exit(1);

}for(i=0;i<n;i++){

vec[i]=(int*)malloc(m*sizeof(int));if(!vec){

printf("\a\nNu sa alocat memorie!\n"); system("pause"); exit(1);

}}

return vec;}

int** free_vec(int** vec,int n){

int i;if(vec==NULL)

return vec;for(i=0;i<n;i++){

free(vec[i]);free(vec);vec=NULL;

}return vec;

}///////////////////////ARC//////////////////////////////////////void intro_arc(arc* a,int u,int x){

int i,j;for(i=0;i<u;i++){

system("cls"); printf("Virfurile disponibile sunt:"); for (j = 0; j < x; ++j) { printf("[%d] ",j+1); }

printf("\n\nIntrodu datele arcului [%d]\n",i+1);printf("Introdu inceputul: ");scanf("%d",&a[i].inc);printf("Introdu sfirsitul: ");scanf("%d",&a[i].sfr);

if(!(a[i].inc >=1 && a[i].inc <= x && a[i].sfr >=1 && a[i].sfr <= x))

{printf("\a\nAti introdus virfuri care nu exista!\nIncercati din

nou\n\n");free(a);system("pause");intro_arc(a,u,x);

4

} }}

void print_arc(arc* a,int u){

int i;for(i=0;i<u;i++){

printf("Arcu: %d\n",i+1);printf(" [%d] --> [%d]\n\n",a[i].inc,a[i].sfr);

}}

void modif_arc(arc* a,int u,int x,int mod){

printf("Virfurile disponibile sunt:"); for (int j = 0; j < x; ++j) { printf("[%d] ",j+1); }

printf("\nArcul:\n\n");printf(" [%d] --> [%d]\n\n",a[mod-1].inc,a[mod-1].sfr);printf("Introdu inceputul: ");scanf("%d",&a[mod-1].inc);printf("Introdu sfirsitul: ");scanf("%d",&a[mod-1].sfr);if(!(a[mod-1].inc >=1 && a[mod-1].inc <= x && a[mod-1].sfr >=1 && a[mod-

1].sfr <= x)) {

printf("\a\nAti introdus virfuri care nu exista!\nIncercati din nou\n\n");

system("pause");modif_arc(a,u,x,mod);

}}void add_virf(arc* a,int u,int *x,int x1){

int i;*x=*x+x1;

}arc* dell_virf(arc* a,int *u,int *x){

int i,j,t=0; int v; printf("Virfurile disponibile sunt:"); for (j=0;j<*x;j++) { printf("[%d] ",j+1); } printf("\n");

printf("Introduceti virful care doriti sa il stergeti:\n"); scanf("%d",&v);

mn:for(i=0;i<*u-1;i++) { if(a[i].inc==v)

5

{if(i==*u) {t=t+1; break;} else {for(j=i;j<=*u-1;j++) {a[j].inc=a[j+1].inc; a[j].sfr=a[j+1].sfr;}}t=t+1;} if(a[i].sfr==v) {if(i==*u) {t=t+1; break;} else {for(j=i;j<=*u-1;j++) {a[j].inc=a[j+1].sfr; a[j].sfr=a[j+1].sfr;}}t=t+1;} } for(i=0;i<*u; i++){ if(a[i].inc==v || a[i].sfr==v) goto mn; } for(i=0;i<*u;i++) { if(a[i].inc>=v && a[i].sfr>=v ) { a[i].inc=a[i].inc-1; a[i].sfr=a[i].sfr-1; } else if(a[i].inc>=v){ a[i].inc=a[i].inc-1; } else if(a[i].sfr>=v){ a[i].sfr=a[i].sfr-1; } } *u=*u-t; *x=*x-1; a=(arc*)realloc(a,(*u)*sizeof(arc)); return a;}void add_arc(arc* a,int *u,int x,int u2){

int i;for(i=*u;i<*u+u2;i++){

system("cls"); printf("Virfurile disponibile sunt:"); for (int j = 0; j < x; ++j) { printf("[%d] ",j+1); }

printf("\n\nIntrodu datele arcului %d\n",i+1);printf("Introdu inceputul: ");scanf("%d",&a[i].inc);printf("Introdu sfirsitul: ");scanf("%d",&a[i].sfr);

if(!(a[i].inc >=1 && a[i].inc <= x && a[i].sfr >=1 && a[i].sfr <= x))

{printf("\a\nAti introdus virfuri care nu exista!\nIncercati din

nou\n\n");system("pause");add_arc(a,u,x,u2);

} } *u=*u+u2;}

void del_arc(arc* a,int *u,int x,int u3){

int i; *u=*u-1; if(*u>0) { for(i=u3-1;i<*u;i++)

a[i]=a[i+1]; } else {

system("cls");

6

}}//////////////////////////MATRICEA INCIDENTA////////////////////////////////

void matr_inc(arc* a,int** vec,int u,int x){

int i,j;for(i=0;i<u;i++){

for(j=0;j<x;j++){

if(a[i].inc==a[i].sfr && a[i].inc==j+1)vec[i][j]=2;

elseif(a[i].inc==j+1)

vec[i][j]=-1;else

if(a[i].sfr==j+1)vec[i][j]=1;

elsevec[i][j]=0;

}}

}

void print_matr_inc(int** vec,int u,int x){

int i,j;for(i=0;i<x;i++)

{ printf("\tX%d",i+1); } for(i=0;i<u;i++) { for(j=0;j<x;j++) { if(j==0) { printf("\nU%d",i+1); } printf("\t%d",vec[i][j]); } printf("\n"); }}

////////////////////MATRICEA ADIACENTA///////////////////////

void matr_adc(arc* a,int** vec,int u,int x){

int i,j,y,z=0;for(i=0;i<x;i++){

for(j=0;j<x;j++){

for(y=0;y<u;y++){

if(a[y].inc==i+1 && a[y].sfr==j+1){

7

vec[i][j]=1;z++;

}}if(!z)

vec[i][j]=0;z=0;

}}

}

void print_matr_adc(int** vec,int u,int x){

int i,j;for(i=0;i<x;i++)

{ printf("\tX%d",i+1); } printf("\n"); for(i=0;i<u;i++) { for(j=0;j<x;j++) { if(j==0) { printf("X%d",i+1); } printf("\t%d",vec[i][j]); } printf("\n"); }}

/////////////////////LISTA DE ADIACENTA////////////////////////void list_ad(arc* a,int** vec,int u,int x){

int i,j,y,z=1;for(i=0;i<x;i++){

vec[i][0]=i+1;z=1;for(j=1;j<x+u;j++){

for(y=0;y<u;y++){

if(a[y].inc==i+1 && a[y].sfr==j){

vec[i][z]=j;z++;

}}

}vec[i][z]=0;

}}

void print_list_ad(int** vec,int u,int x){

int i,j;

8

for(i=0;i<u;i++) { printf("%d |",vec[i][0]); for(j=1;j<x;j++) { printf(" %d",vec[i][j]); if(vec[i][j]==0) break; } printf("\n\n"); }

Fisierul main.c

#include "functions.c"

int main(){int u=0,x=0;arc* a=NULL;int** tab_matr_inc=NULL;int** tab_matr_adc=NULL;int** tab_li_adc=NULL;int n,m,mod,u2,u3,x1,x2;int op1,op2,op3,op4,i,op5;//switch optionsint l,k,r,s,t;//while options

while(1){

while(l){

l=0;system("cls");printf(" ----------------------------------------------------\n");

printf(" || Pastrarea grafurilor in memoria calculatorului ||\n"); printf(" || A efectuat st.gr SI-141 Cucu Eugeniu ||\n"); printf(" ----------------------------------------------------\n"); printf("\n\n ---------------------------------------------\n"); printf(" || [1] INTRODUCEREA ARCELOR SI VIRFURILOR ||\n"); printf(" || [2] IESIRE ||\n"); printf(" ---------------------------------------------\n"); printf("\n\n Comanda : "); scanf("%d",&op1);

switch(op1){

case 1 :system("cls");printf("Dati numarul de arcuri:\n");scanf("%d",&u);printf("Dati numarul de virfuri:\n");scanf("%d",&x);a=(arc*)malloc(u*sizeof(arc));intro_arc(a,u,x);break;

case 2 :if(a)free(a);exit(1);

default :system("cls");

9

printf("\aAti introdus o comanda gresita!\n");l=1;system("pause");break;

}system("pause");

}

while(k){

k=0;system("cls");printf("\t\t===================\n");

printf("\t\t|| LISTA MENIURI ||\n"); printf("\t\t===================\n"); printf("\n\n\t\t=============\n"); printf("\t\t|| AFISARE ||\n"); printf("\t\t=============\n\n"); printf("\t\t===============================\n"); printf("\t\t|| [1] ARCE ||\n"); printf("\t\t|| [2] MATRICEA DE INCIDENTA ||\n"); printf("\t\t|| [3] MATRICEA DE ADIACENTA ||\n"); printf("\t\t|| [4] LISTA DE ADIACIDENTA ||\n"); printf("\t\t==============================="); printf("\n\n\t\t================\n"); printf("\t\t|| MODIFICARE ||\n"); printf("\t\t================\n\n"); printf("\t\t============================\n"); printf("\t\t|| [5] SCHIMBAREA DATELOR ||\n"); printf("\t\t|| [6] ADAUGARE ||\n"); printf("\t\t|| [7] STERGERE ||\n"); printf("\t\t============================\n\n"); printf("\t\t===============\n"); printf("\t\t|| IESIRE[0] ||\n"); printf("\t\t==============="); printf("\n\n\t\t Comanda : "); scanf("%d",&op2); switch(op2) { case 1 : system("cls"); if(u>0) print_arc(a,u); else printf("Nu mai sunt arce alegeti [6] sau [0]\n"); k=1; system("pause"); break; case 2 : system("cls"); if(u>0) {

printf("Matricea de incidenta:\n\n"); tab_matr_inc=aloc_vec(u,x); matr_inc(a,tab_matr_inc,u,x); print_matr_inc(tab_matr_inc,u,x);

} else printf("Nu mai sunt arce alegeti [6] sau [0]\n");

10

k=1; system("pause"); break; case 3 : system("cls"); if(u>0) {

printf("Matricea de adiacenta:\n\n"); tab_matr_adc=aloc_vec(x,x); matr_adc(a,tab_matr_adc,u,x); print_matr_adc(tab_matr_adc,x,x);

} else printf("Nu mai sunt arce alegeti [6] sau [0]\n"); k=1; system("pause"); break; case 4 : system("cls"); if(u>0) {

printf("Lista de adiacenta:\n\n"); tab_li_adc=aloc_vec(x,x+u); list_ad(a,tab_li_adc,u,x); print_list_ad(tab_li_adc,x,x+u);

}else

printf("Nu mai sunt arce alegeti [6] sau [0]\n"); k=1; system("pause"); break; case 5 : system("cls");

print_arc(a,u); printf("\n\nIntrodu numarul arcului pentru modificare: ");

scanf("%d",&mod);if(!(mod >= 1 && mod <= u)){

system("cls"); printf("\aArcul introdus nu exista! Incercati din

nou.\n"); system("pause"); printf("\n\nIntrodu numarul arcului pentru

modificare: ");scanf("%d",&mod);

}system("cls");modif_arc(a,u,x,mod);k=1;

system("pause"); break;

case 6 :system("cls");printf("Dati numarul de arce pentru adaugare:\n");scanf("%d",&u2);a=(arc*)realloc(a,(u+u2)*sizeof(arc));system("cls");add_arc(a,&u,x,u2);k=1;

11

system("pause"); break; case 15 :

system("cls");printf("Dati numarul de virfuri pentru adaugare:\n");scanf("%d",&x1);a=(arc*)realloc(a,(x+x1)*sizeof(arc));system("cls");add_virf(a,u,&x,x1);k=1;

system("pause"); break; case 16 : system("cls"); dell_virf(a,&u,&x); k=1; system("pause"); break;

case 7 :system("cls");print_arc(a,u);printf("Indicati numarul arcului pentru stergere\n");scanf("%d",&u3);a=(arc*)realloc(a,(u+u3)*sizeof(arc));system("cls");del_arc(a,&u,x,u3);k=1;

system("pause"); break;

case 0 :if(a)free(a);if(tab_matr_inc)

free_vec(tab_matr_inc,u);if(tab_matr_adc)

free_vec(tab_matr_adc,x);if(tab_li_adc)

free_vec(tab_li_adc,x+u);system("cls");exit(1);

default :system("cls");printf("\aAti introdus o comanda gresita!\n");k=1;system("pause");break;

}}

}return 0;}

12

ConcluziaIn urma efectuarii lucrarii date unde am studiat metodele de definire a unui graf: in matrice

adiacenta,matrice de incedinta si lista,am elaborat un procedeu de introducere, afisare si extragere a unei din metodele mentionate mai sus prin programul C.Am observat cu usurinta editarea grafului prin metoda listei de adecianta(incidenta).Prin orice metoda de definire a grafului putem usor sa obitnem metoda grafica a grafului.

Bibliografie1. Conspectul la matematica discreta predat de V.Bagrin2. “Matematica discreta in inginerie” indrumar de laborator Chisinau 1999

13