Scopul proiectului

Am realizat un program in limbajul TURBO PASCAL intitulat graf_neorientat pentru tratarea problemelor de drumuri minime si studiul grafurilor neorientate.

Acesta are un meniu simplu alcatuit din sase optiuni pe care le voi

prezenta succint:

0.Exit - pentru a iesi din program

1.Introducere graf - pentru introducerea grafului asupra caruia se va face analiza si calculul din urmatoarele etape.

2.Afiseaza matricea de adiacenta - se afiseaza matricea de adiacenta pentru graful introdus de la tastatura in optiunea 1.

3.Afiseaza gradul nodurilor - se afiseaza gradul tuturor nodurilor introduse.

4.Calculeaza drumul minimal - pentru afisarea drumului cu cel mai mic cost.

5.Afiseaza grafurile conexe - afiseaza nodurile ce formeaza un graf conex..

Detalii teoretice si algoritmi

Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri si amuzamente matematice.

Data nasterii teoriei grafurilor este anul 1736, iar termenul de graf este derivat din termenul notatiei "grafica" din chimie.

GRAF NEORIENTAT - pereche neordonata de multimi (X,U).

X - fiind o multime finita si nevida de elemente numite NODURI sau VARFURI.

U - multime de perechi neordonate (submultimi cu doua elemente) din X, numite MUCHII.

Fie G=(X,U) un graf neorientat. Multimea X se numeste multimea nodurilor sau varfurilor grafului G, iar U multimea muchiilor.

O muchie uIU, este deci o submultime de varfuri distincte din X si se noteaza u=[x.y], unde x si y sunt extremitatile muchiei u.

Daca u1 si u2 sunt doua muchii care au o extremitate comuna atunci aceste muchii se numesc incidente.

Un graf poate fi reprezentat cu ajutorul unei figuri plane in care fiecarui varf i se asociaza un punct si fiecarei muchii [x,y], o linie curba care uneste in plan punctele ce corespund varfurilor x si y.

Matricea de adicenta asociata unui graf neorientat se defineste ca o matrice patratica de ordinul "n", cu elementele :

A[i,j]= un graf neorientat, X=.

Se numeste lant in G succesiunea de varfuri L=[xi1, xi2, , xik] cu proprietatea ca orice doua varfuri consecutive din L sunt adiacente, adica [xi1, xi2], [xi2, xi3], ., [xi(k-1), xik]IU.

Se numeste ciclul in G un lant L pentru care xi1=xik si toate muchiile [xi1, xi2], [xi2, xi3],, [xi(k-1), xik] sunt diferute doua cate doua.

Un graf G=(X,U) se numeste conex daca pentru orice doua varfuri x si y diferite ale sale, exista un lant care le leaga.

Se numeste componenta conexa a grafului G=(X,U) un subgraf C=(X ,Y ), conex, al lui G care are proprietatea ca nu exista nici un lant in G care sa lege un varf din X cu un varf din X - X

ALGORITM care verifica daca un graf este conex:

PAS 1. Se alege un varf x. Se initializeaza numarul "nc" de componente convexe cu 0

(nc:=0).

PAS 2. Se mareste "nc" cu o unitate (nc:=nc+1).

Se determina si se afiseaza multimea varfurilor legate de x prin lanturi utilizand parcurgerea BF, luand varf de plecare pe "x". Aceasta reprezinta multimea de varfuri ale componentei conexe "nc". Daca toate varfurile au fost vizitate, se trece la pasul 3. Daca nu, se alege un varf x, inca nevizitat, si se reia pasul 2.

PAS 3. Se testeaza "nc". Daca nc =1, rezulta ca graful este conex. Daca nu, precizeaza numarul total de componente conexe.

Parcurgerea grafurilor neorientate

Parcurgerea unui graf neorientat indica posibilitatea de a ajunge o singura data in fiecare varf al grafului, pornind de la un varf dat "x_k" si parcurgand muchii adiacente. Aceasta operatiune poarta numele de vizitare sau traversare a varfurilor grafului si este efectuata cu scopul prelucrarii informatiei asociata varfurilor.

Deoarece graful este o structura neliniara de organizare a datelor, prin parcurgerea sa in mod systematic se realizeaza si o aranjare liniaraq a varfurilor sale, deci informatiile stocate in varfuri se pot regasi si prelucra mai usor.

Pentru a facilita scrierea, convenim ca in loc de sa se scrie , fara ca valabilitatea rezultatelor sa fie diminuata. Astfel, prin similitudine, se poate folosi drept relatie de ordine intre varfurile grafului, relatia de ordine din numerele naturale (notata cu "<").

Metoda de parcurgere BF

Numele provine din limba engleza (Breadth First-"in latime") si principiul este: se viziteaza intai varful initial, apoi vecinii acestuia, apoi vecinii nevizitati ai acestora, si asa mai departe.

Vizitarea unui varf inseamna de fapt o anumita prelucrare specificata asupra varfului respectiv.

Derularea algoritmului presupune alegerea, la un moment dat, dintre toti vecinii unui varf, pe acela ce nu a fost inca vizitat. Acest lucru este posibil prin folosirea unui vector VIZITAT de dimensiune n, ale carui componente se definesc astfel: pentru kI

VIZITAT[k] 1, daca varful k a fost vizitat

0, in caz contrar

Se foloseste o structura de tip coada (simulata in alocare statica printr-un vector V) in care prelucrarea unui varf k aflat la un capat al cozii (varful cozii), consta in introducerea in celalat capat al ei (coada cozii), a tuturor varfurilor j vecine cu k, nevizitate inca. Pentru inceput, k este egal cu varful indicat initial i si toate componentele lui VIZITAT sunt zero.

Algoritmul consta in urmatorii pasi:

se prelucreaza varful initial k;

se adauga varful k in coada;

varful k se considera vizitat;

cat timp coada este nevida se executa:

pentru toti vecinii j nevizitati inca ai varfului k, executa:

se adauga varful j in coada;

varful j se considera vizita;

varful j devine varful k;

3) se afiseaza continutul cozii;

Ex 1:

-pentru acest graf, pornind din nodul 1, continutul cozii va fi: 1,2,6,3,4,5.

Ex 2:

- pentru acest graf, pornind din nodul 4, continutul cozii va fi: 4,1,2,3,6,5,7

Program parcurgere_BF;

uses crt;

var vizitat:array[1..20] of 0..1;

A:array[1..20,1..20] of integer;

V:array[1..20] of integer;

f:text;

nume:string;

n,m,p,u,i,j,k,x1,x2:integer;

procedure init;

begin

for i:=1 to n do

begin

vizitat[i]:=0;

for j:=1 to n do

a[i,j]:=0;

end;

end;

procedure complet;

begin

for i:=1 to m do

begin

readln(f,x1,x2);

a[x1,x2]:=1;

a[x2,x1]:=1;

end;

end;

procedure prim_vf;

begin

v[1]:=i;

p:=1;u:=1;

vizitat[i]:=1;

end;

procedure prelucrare;

begin

k:=v[p];

for j:=1 to n do

if (a[k,j]=1) and (vizitat[j]=0) then

begin

inc(u);

v[u]:=j;

vizitat[j]:=1;

end;

inc(p);

end;

procedure scrie;

begin

writeln(' Plecand din varful ',i,', ');

writeln('parcurgand graful prin metoda BF,');

writeln('succesiunea varfurilor, este :');

write(' ',i,' ');

for j:=2 to u do

write(v[j],' ');

writeln;

end;

begin

clrscr;

assign(f,'date.txt');

reset(f);

write('Dati numarul de varfuri n: ');

readln(n);

write('Dati numarul de muchii m: ');

readln(m);

init;

complet;

write('Varful de plecare: ');

readln(i);

prim_vf;

while p<=u do

prelucrare;

scrie;

readkey;

end.

Programul PASCAL pentru varianta recursive este asemanator cu programul pentru varianta nerecursiva. Deoarece procedura BF_R se autoapeleaza, se inlocuieste while p<=u do PRELUCRARE cu BF_R(1), unde procedura BF_R este:

procedure BF_R(p:integer);

begin

k:=v[p]

for j:=1 to n do

if(a[k,j]=1)and(vizitat[j]=0)then

begin

inc(u);

v[u]:=j;

vizitat[j]:=1;

end;

if p<=u then

BF_R(p+1);

end

Aplicatie:

Enunt: Pentru alimentarea cu apa a unui cartier exista o statie de pompare a apei la care sunt conectate cateva blocuri (nu toate) . Stiind ca mai sunt conectate si unele

blocuri intre ele determinati daca pentru o configuratie data de conectare a blocurilor si a statiei de pompare exista posibilitatea de alimentare cu apa a intregului cartier.

Fisierul de intrare are urmatoarea forma:

IN.txt

N-numarul de blocuri;

Ns-nodul de start;nr blocului unde este statia de pompare

x y

exista conexitate intre blocul x si blocul y

Rezolvare:

Cu datele problemei se construieste un graf in care nodurile grafului reprezinta conexiunile dintre blocuri.Se parcurge graful in latime avand drept nod de start blocul in care se afla statia de pompare .Daca in urma parcurgerii s-au vizitat toate nodurile , inseamna ca se poate realiza alimentarea cu apa a intregului cartier.

De exemplu , pentru configuratia din fisierul urmator:

EX:1

6 4

Se obtine graful:

9 2

ns

Si programul afiseaza :

"Nu se poate alimenta cu apa intreg cartierul";

EX:2

Se obtine graful :

ns

3

8 4

5

Si programul afiseaza :

" Se poate alimenta cu apa intreg cartierul";

Program alimentarea_cartierului_cu_apa;

uses crt;

type coada=array[1..100] of integer;

vector=array[1,,100] of integer;

matrice=array[1..20,1..20] of integer;

var c:coada;v:vector;a:matrice;nr,ns,n:byte;

procedure citire;

var f:text; x,y:byte;

begin

assign(f,'in.txt');

reset(f);

readln(f,n);

readln(f,ns);

while not eof(f) do

begin

readln(f,x,y);

a[x,y]:=1;

a[y,x]:=1;

end;

close(f);

end;

function prim_nevizitat:byte;

var i:byte;

begin

i:=1;

while (v[i]<>0) and (i<=n) do

inc(i);

if i<=n then

prim_nevizitat:=i

else

prim_nevizitat:=n+1;

end;

procedure parcurgere;

var i,lc,x:byte;

begin

nr:=0;

while ns<=n do

begin

nr:=nr+1;

c[1]:=ns;

write(ns);

v[ns]:=1;

lc:=1;

while lc<>0 do

begin

x:=c[1];

for i:=1 to n do

if (a[x,i]=1) and (v[i]=0) then

begin

inc(lc);

c[lc]:=i;

write(i);

v[i]:=1;

end;

for i:=1 to lc-1 do

c[i]:=c[i+1];

lc:=lc-1;

end;

ns:=prim_nevizitat;

end;

end;

begin

clrscr;

citire;

parcurgere;

if nr=1 then

writeln('Se poate alimenta cu apa intreg cartierul')

else

writeln('Nu se poate alimenta cu apa intreg cartierul');

readkey;

end.

Metoda de parcurgere DF

Algoritmul DF (depth first) se caracterizeaza prin faptul ca merge "in adancime" ori de cate ori acest lucru este posibil.

Parcurgerea incepe cu un varf initial dat "i" si continua cu primul dintre vecinii sai nevizitati; fie acesta "j". In continuare se procedeaza in mod similar cu varful "j", trecandu-se la primul dintre vecinii lui "j", nevizati inca.

Algoritmul in pseudocod este urmatorul :

PAS 1. pentru j:=1, n executa viz[j]:=0;

urm[j]:=0;

PAS 2. S[1]:=i;

ps:=1;

PAS 3. atat timp cat ps:=1 executa j:=S[ps];

determina primul dintre vecinii k ai lui j, nevizati inca

urm[j]:=k;

daca nu exista un asemenea k atunci ps:=ps-1;

astfel scrie k;

viz[k]:=1;

ps:=ps+1;

Program parcurgere _DF;

var viz : array[1..20] of 0..1;

a : array[1..20,1..20] of integer;

n,m,k,i,j,x,y,ps : integer;

s,urm : array[1..20] of integer;

begin

write ('n,m='); readln(n,m);

for i:=1 to n do

for j:=1 to n do A[i,j]:=0;

for i:=1 to m do begin

write('muchia',i,'=');

readln(x,y); A[x,y]:=1; A[y,x]:=1;

end;

write('varful de plecare:'); readln(i);

for j:=1 to n do begin

viz[j]:=0;

urm[j]:=0;

end;

S[1]:=i; ps:=1;

viz[i]:=1; write ('ordinea in DF :',i,' ');

while ps 1 do begin

j:=S[ps]; k:=urm[j]+1;

while(k n) and ((a[j,k]=0) or (a[j,k]=1) and (viz[k]=1)) do k:=k+1;

urm[j]:=k;

if k:=n+1 then ps:=ps - 1

else begin

write(k,' '); viz[k]:=1; ps:=ps+1; S[ps]:=k;

end;

end;

Program graf_neorientat

Fie G=(X,U) astfel in  X=

U=

.Introducere graf: n=8

m=9

muchia1= 1 2 muchia7=5 7

cost= 5 cost=2

muchia2= 1 3 muchia8=6 7

cost= 5 cost=3

muchia3= 1 4 muchia9=6 8

cost= 5 cost=1

muchia4= 2 5  

cost=3

muchia5=3 5

cost=2

muchia6=4 6

cost=5

Matricea de adiacenta

0 1 1 1 0 0 0 0

1 0 0 0 1 0 0 0

1 0 0 0 1 0 0 0

A = 1 0 0 0 0 1 0 0

0 0 0 1 0 0 1 1

0 0 0 0 1 1 0 0

0 0 0 0 0 1 0 0

.Gradul nodurilor

d(1)=3 d(5)=3

d(2)=2 d(6)=3

d(3)=2 d(7)=2

d(4)=2 d(8)=1

.Drumul minimal

Cel mai ieftin drum are cost=21 si este:

[5,7]

[3,5]

[6,7]

[2,5]

[4,6]

[1,4]

.Singurul graf conex este [1,2,3,4,5,6,7,8,]

Program graf neorientat(Pascal)

In cadrul programului softul folosit este Turbo Pascal 6.0, iar hardul: Calculatoare compatibile PC. Sistem de operare MS-DOS 6.20. Mai jos este dat programul care rezolva problema enuntata mai sus.

program graf_neorientat;

uses crt;

var n,m:1..20;

a:array[1..20,1..20] of byte;

v:array[1..100,1..2] of byte;

arb:array[1..100,1..2] of byte;

cost:array[1..20] of byte;

x,component:array[1..20] of byte;

d,nr,mcount,m_ini,cost_total,l_cost:byte;

grad,numar,c,cost_final:array[1..20] of byte;

l,select:array[1..10,1..10] of byte;

sel:array[1..20] of boolean;

procedure meniu;

begin

clrscr;

writeln;

writeln;

writeln(' Program grafuri neorientate');

writeln;

writeln;

writeln;

writeln;

writeln(' 0.Exit');

writeln(' 1.Introducere graf');

writeln(' 2.Afiseaza matricea adiacenta);

writeln(' 3.Afiseaza gradul nodurilor);

writeln(' 4.Calculeaza drum minimal');

writeln(' 5.Afiseaza grafurile conexe');

writeln;

writeln;

write(' Introduceti optiunea dumneavoastra : ');

readln(d);

end

procedure introducere;

var i:byte;

fm,fc:text;

begin

clrscr;

write('introduceti numarul de noduri n='); readln(n);

write('introduceti numarul de muchii m='); readln(m);

for i:=1 to m do begin

write('muchia ');read(v[i,1],v[i,2]);

write(' cost=');readln(cost[i]);

end;

assign(fm,'graf.dat');

rewrite(fm);

writeln(fm.n); writeln(fm,m);

assign(fc,'cost.dat');

rewrite(fc);

for i:=1 to m do begin

writeln(fm,v[i,1],' ',v[i,2]);

writeln(fc,cost[i]);

end;

close(fm);

close(fc);

end; 

procedure initializare;

var i,j:byte;

f:text;

begin

assign(f,'graf.dat');reset(f);

readln(f,n);readln(f,m);

for i:=1 to m do begin

for j:=1 to 2 do read(f,v[i,j]);

readln(f);

end;

close(f);

end;

procedure adicenta;

var i:byte;

begin

for i:=1 to m do begin

a[v[i,1],v[i,2]]:=1;

a[v[i,2],v[i,1]]:=1;

end;

end;

procedure afis_adiacenta;

var i,j:byte;

begin

for i:=1 to n do begin

for j:=1 to n do write(a[i,j],' ');

writeln;

end;end;

procedure roy;

var i,j,k:byte;

begin

for i:=1 to n do

for j:=1 to n do l[i,j]:=a[i,j];

for i:=1 to n do

for j:=1 to n do

if l[i,j]=1 then for k:=1 to n do

if l[i,k]<l[j,k] then l[i,k]:=1;

end;

procedure citeste_cost;

var i:byte;

f:text;

begin

assign(f,'cost.dat');

reset(f);

for i:=1 to m do readln(f,cost[i]);

close(f);

end;

procedure sortare_muchii;

var i,j,k:byte;

begin

for i:=1 to m-1 do

for j:=i+1 to m do

if cost[i]>cost[j] then begin

t:=cost[j];

cost[j]= cost[i];

cost[i]:=t;

t:=v[j,1];

v[j,1]:=v[i,1];

v[i,1]:=t;

t:= v[j,2];

v[j,2]:=v[i,2];

v[i,2]:=t;

end;

end;

procedure arbore_min;

var i,j,t:byte;

costmin:integer;

begin

initializare;

citeste_cost;

sortare muchii;

writeln;

for i:=1 to n do component[i]:=i;

component[v[1,2]]:=component[v[1,1]];

arb[1,1]:=v[1,1];arb[1,2]:=v[1,2];

costmin:=cost[1];

for i:=1 to m do

if component[v[i,1]]<>component[v[i,2]] then begin

t:=component[v[i,2]];

for j:=1 to n do

if component[j]=t then

component[j]:=component[v[i,1]];

arb[i,1]:=v[i,1];

arb[i,2]:=v[i,2];

inc(costmin,cost[i]);

end;

writeln('Cel mai ieftin drum are cost=',costmin,' si este :');

for i:=1 to m do if arb[i,1]<>0 then writeln('[',arb[i,1],',',arb[i,2],']');

end;

procedure componente_conexe;

var i,j:byte;

begin

nr:=0;

for i:=1 to n do component[i]:=0;

for i:=1 to n do

if component[i]=0 then begin

nr:=nr+1;

component[i]:=nr;

for j:=1 to n do

if l[i,j]=1 then component[j]:=nr;

end;

end;

procedure tip_conex;

var i,j:byte;

begin

for i:=1 to nr do begin

write('[');

for j:=1 to n do if component[j]=i then write(j,',');

writeln(#8']');

end;

end;

procedure det_grad_vf;

var i,j:integer;

begin

for i:=1 to n do

for j:=1 to n do

if a[i,j]=1 then inc(grad[i]);

end;

procedure afis_grad;

var i:byte;

begin

for i:=1 to n do

writeln('grad [',i,']=',grad[i]);

end;

procedure costm(k:byte);

var i,j,l,ii,cosymin:byte;

begin

sel[k]:=true;

c[mcount]:=k;

costmin:=255;

ii:=0;

repeat

for i:=1 to n do

if not sel[i] and (k<>1) then begin

for l:=1 to m do

if ((v[l,1]=k) and (v[l,2]=i)) or

((v[l,2]=k) and (v[l,1]=i)) then exit;

if cost[l]<costmin then begin

costmin:=cost[l];

ii:=i;

end;

end;

if ii=0 thensel[m_ini]:=false;

until ii<>0;

sel[ii]:=true;

inc(cost_total, costmin);

c[mcount+1]:=ii;

end;

procedure lant_h_cost_min;

var i:byte;

begin

l_cost:=255;

for m_ini:=1 to n do begin

for i:=1 to n do sel[i]:=false;

mcount:=1; c[1]:=m_ini; sel[m_ini]:=true;cost total:=0;

for i:=1 to n do begin

costm(c[mcount]);

mcount:=mcount+1;

end;

if cost_total<l_cost then begin

cost_final:=c;

l_cost:=cost_total;

end;

end;

write('Cel mai ieftin ciclu hamiltonian este: [');

for i:=1 to n+1 do write(cost_final[i],',');writeln(#8'[');

writeln('Cost : ',l_cost);

end;

begin

initializare;

roy

citeste_cost;

repeat

meniu;

case d of

1 :introducere;

2 :begin

clrscr;

initializare;

adiacenta;

afis_adiacenta;

readln;

end;

3 :begin

clrscr;

det_grad_vf;

afis_grad;

readln

end;

4 :begin

clrscr;

arbore_min;

readln;

end;

5 :begin

clrscr;

initializare;

adiacenta;

roy;

citeste_cost;

sortare_muchii;

componente_conexe;

tip_conex;

readln;

end;

end;

until d=0;

end.

Bibliografie

Ghid de utilizare "TURBO PASCAL 6.0" - Editura Microinformatica CLUJ - NAPOCA

. Manual "Bazele informaticii" - Editura Petrion Bucuresti.

Atanasiu, Adrian- Concursuri de informatica Editura Petrion, 1995

Cormen, Thomas; Leiserson, Charles; Rivest, Ronald- Introduction to Algorithms. The Massachusetts Institute of Technology, 1990

Ionescu, Clara; Zsako Ioan- Structuri arborescente cu aplicatiile lor. Editura Tehnica, 1990

7. Ivasc, Cornelia; Pruna Mona-Bazele Informaticii. Editura Petrion, 1995

Manber, Udi- Introduction to Algorithms, 1989

Mitrana, Victor- Provocarea algoritmilor. Editura Agni, 1994

. Nedita, V.; Niculescu, St.; Zidaroiu, C.- Matematica aplicata in tehnica de calcul. 11. Editura Didactica si Pedagogica

Popescu Anastasiu, Doru- Puncte de articulatie si punti in grafuri. Gazeta de Informatica nr. 5/1993

Tomescu, Ioan- Probleme de combinatorica si teoria grafurilor. Editura Didactica si Pedagogica

Tomescu, Ioan; Leu, Adrian- Matematica aplicata in tehnica de calcul. Editura Didactica si Pedagogica

Vlada, Marin- Grafuri neorientate si aplicatii. Gazeta de Informatica

*** -Gazeta de Informatica Editura Libris, 1991-1996