Grafuri Neorientate.doc

MINISTERUL EDUCAȚIEI,CERCETĂRII,TINERETULUI ȘI SPORTULUICOLEGIUL TEHNIC MĂTĂSARI

ATESTAT PROFESIONAL

Prof.Îndrumător:Săceanu Ion

Elev: Balcan OnisimProfil:Matematică-Informatică

Colegiul Tehnic Mătăsari

2015

1

MINISTERUL EDUCAȚIEI,CERCETĂRII,TINERETULUI ȘI SPORTULUICOLEGIUL TEHNIC MĂTĂSARI

GRAFURI NEORIENTATE

Prof.Îndrumător:Săceanu Ion

Elev:Balcan Onisim

Profil:Matematică-InformaticăColegiul Tehnic Mătăsari

20152

Cuprins

ARGUMENT........................................................................................................................................4MEMORAREA GRAFURILOR..........................................................................................................5GRAF PARŢIAL, SUBGRAF............................................................................................................10PARCURGEREA GRAFURILOR NEORIENTATE........................................................................11LANŢURI...........................................................................................................................................17GRAF CONEX...................................................................................................................................21COMPONENTE CONEXE................................................................................................................21CICLURI.............................................................................................................................................24ARBORI..............................................................................................................................................26BIBLIOGRAFIE.................................................................................................................................31

3

Argument

Încă de la apariţia limbajelor de programare s-a încercat ca acestea să descrie cat mai bine realitatea.Am ales graful ca temă pentru realizarea proiectului deoarece consider că grafurile au o importanţă deosebită fiind utilizaţi în domenii precum:cibernetică, matematică, cercetări operaţionale în vederea optimizăriidiferitelor activităţi economice, chimie (pentru descrierea structuriicristalelor), reţelele de transport de toate tipurile (pentru optimizarea traseelor), circuite electrice (pentru simularea funcţionări corecte),inteligenţa artificiala şi nu în ultimul rând în domeniul analizei aplicaţiilor software.

GRAFURI NEORIENTATE

4

Definiţie: Graful neorientat este o pereche ordonată G=(V, E). unde:V= { v1, v2,…,vn} este o mulţime finită şi nevidă. Elementele mulţimii V se numesc noduri (vârfuri);E este o mulţime finită de perechi neordonate de forma (vi, vj), unde i diferit de j, si vi, vj V. Elementele mulţimii se numesc muchii. Semnificaţia unei muchii este aceea că uneşte două noduri.

exemplu de graf neorientat:

Definiţii:

1. În graful g=(V,E), nodurile distincte vi ,vj G sunt adiacente dacă există muchia (vi ,vj ) E. Vom spune că muchia (vi ,vj ) E este incidentă la nodurile vi şi vj . În exemplul nostru nodurile 1 şi 5 sunt adiacente dar nodurile 2 şi 5 nu sunt adiacente. Muchia (4,5) este incidentă la nodurile 4 şi 5.

2. Într-un graf neorientat, prin gradul unui nod v se înţelege numărul muchiilor incidente cu nodul v şi se notează cu d(v). Un nod cu gradul 0 se numeşte nod izolat, iar unul cu gradul 1 se numeşte nod terminal. Exemplul nostru : d(2)=2, d(1)=3, d(6)=0 (nod izolat).

3. O relaţie utilă: d1+d2+,....,+ dn =2*m, adică suma gradelor nodurilor grafului = 2* numărul muchiilor;

MEMORAREA GRAFURILOR

5

3

2

4

5

1 6

Avem:G=(V,E)V= {1,2,3,4,5,6}E= { (1,2), (1,3), (1,5),(2,3), (3,4),(4,5)}

Observaţii:Se notează cu n numarul de nodurin=6, iar cu m numărul muchiilor m=6Muchia (1,2) este aceeaşi cu (2,1) pentru ca avem un graf neorientat.Nu există o muchie care uneşte un nod cu el insuşi.Două noduri pot fi unite prin cel mult o muchie.

Memorarea se face prin mai multe metode care e aleg în funcţie de :algoritmul care prelucrează datele referitoare la graf;memoria internă pe care programul o are la dispoziţie;dacă graful conţine multe muchii sau nu.

Structuri de memorare a grafurilor:

1. Memorare grafului prin matricea de adiacenţă a. Este o matrice An,n – o matrice pătratică, unde elementele ei, ai,j au

semnificaţia: 1, pentru (i,j) E

i. Ai,j = 1. 0, pentru (i,j) E

Pentru exemplul de graf dat, matricea de adiacenţă este:

0 1 1 0 1 0 1 0 1 0 0 0 A6,6= 1 1 0 1 0 0

0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0Observaţii:

Elementele de pe diagonala principală sunt 0 ( pentru că am definit un graf la care nu există muchii de la un nod la el insuşi)

Matricea de adiacenţă este simetrică ai,j = aj,i i,j { 1,2,..,n} Suma elementelor de pe linia i reprezintă gradul nodului i, adică

d(i) Suma tuturor elementelor matricei de adiacenţă = suma gradelor

tuturor nodurilor, adică dublul numărului de muchii (2m)b) Crearea matricei prin citirea muchiilor grafului: Datele se citesc dintr-un fişier care are pe primul rând numărul de noduri, iar pe fiecare din următoarele câte o muchie. Se foloseşte funcţia următoare:

void CitireN (char nume_fiş[20], int a[50][ 50], int &n) { int i,j; fstream f(nume_fiş,ios :: in); f>>n; while (f>>i>>j) a[i][j]=a[j][i]=1; f.close();

6

Fişierul ptr graful nostru:

61 21 31 52 33 44 5

}

Programul următor citeşte muchiile grafului şi afişează matricea de adiacenţă.# include <iostream.h># include<conio.h>int a[50][50], n;void CitireN (char nume_fiş[20], int a[50][ 50], int &n) { int i,j; fstream f(nume_fiş,ios :: in); f>>n; while (f>>i>>j)

a[i][j]=a[j][i]=1; f.close();

}

void main( ){

CitireN (“graf.txt”,a,n); For (int i=1; i<=n;i++) { for (int j=1; j<=n;j++) cout<<a[i][j]<<” ”; cout<<endl; }getch(); }

2. Memorarea grafului prin liste de adiacenţă

a. Listele de adiacenţă reprezintă o altă formă de memorare a grafului, în care pentru fiecare nod se indică lista nodurilor adiacente cu el.

b. Pentru exemplul nostru, vom avea listele:

7

c. Se utilizeaza un vector cu n componente, pe care il vom numi Start şi o matrice T cu 2 linii si 2m coloane. Semnificaţiile sunt;

i. Start – pentru fiecare nod i, start[i] specifica coloana din T unde incepe lista nodurilor adiacente cu i. Daca reţine 0, inseamnă că nodul i nu are noduri adiacente.

ii. T (0,i)- reprezintă indicele coloanei din T unde se gaseşte următorul element din listă. Dacă reţine 0, atunci acesta este ultimul element din lista succesorilor;

1 2 3 4 5 6

Start

1 2 3 4 5 6 7 8 9 10 11 12

T[0] T[1]

Exemplu de utilizare: Vrem sa vedem nodurile adiacente ptr nodul 3.Ne uităm in StartStart[3]=9 in t[0]la coloana 9nodul 4 următorul se află la coloana 8- avem nodul 2 următorul il gasim in coloana 4 nodul 1- rezultă ultimul nod pentru că la T[1] urmează 0Rezultă ca nodurile adiacente ale lui 3 sunt 4, 2, 1

Subprogramul care construieşte listele de adiacenţă:

8

5 97 01211

2 1 3 1 5 1 3 2 4 3 45

0 0 1 0 3 0 2 4 8 0 610

Stop am dat de 0

Nodul 6 nu are noduri adiacente ptr ca Start [6]= 0

1 2,3,52 1,331,2,44 3,551,46

Void Citire_LA(char Nume_fis[20], int T[2][50], int Start[50], int& n) { int i, j, k=0 ; fstream f(Nume_fis,ios ::in) ; f>>n; while (f>>i>>j) { k++ ; T[0][k]=j; T[1][k]=Start[i]; Start[i]=k;

K++; T[0][k]=I; T[1][k]=Start[j]; Start[j]=k; }

f.close();}

Programul următor citeşte nr de varfuri şi muchiile unui graf şi afişează, pentru fiecare nod, lista nodurilor adiacente.

# include <iostream.h># include<conio.h>

int t[2][50], start[50], n, i, man;

void citire_muchii(char Nume_fis[20], int t[2][50], int start[50], int& n) { int i, j, k=0 ; fstream f(nume_fis,ios ::in) ; f>>n; while (f>>i>>j) { k++ ; t[0][k]=j; t[1][k]=start[i]; start[i]=k; k++; t[0][k]=i; t[1][k]=start[j]; start[j]=k; }

f.close();}

void main( )

9

Date de intraregraf1.txt61 21 31 52 33 44 5

Date de iesire

1 2,3,52 1,331,2,44 3,551,46 -

{ citire_muchii( “graf1.txt”, t, start,n); for ( i=1;i<=n;i++) { cout<<”noduri adiacente cu “<<i<<endl;

man=start[i]; while ( man) {

cout<<t[0] [man] <<” “; man=t[1][man];

} cout<<endl; }getch();}

3. Memorarea grafurilor prin lista muchiilor

Se utilizează un vector cu m componente, unde m este numărul muchiilor. Fiecare componentă va reţine cele două noduri la care muchia respectivă este incidentă şi , în anumite cazuri alte informaţii referitoare la muchia respectivă.

Struct muchie { int x,y; } ; muchie v[50];

GRAF COMPLET

Definiţie: Un graf complet este un graf neorientat în care oricare două noduri sunt adiacente. El se notează cu Kn, unde n este numărul de noduri ale grafului.

RELAŢII UTILE1. Într-un graf complet gradul oricărui nod este n-1.2. Într-un graf complet avem relaţia m= n(n-1) / 2 , unde m este numarul de

muchii, iar n numarul de noduri.3. Avem 2n(n-1)/2 grafuri neorientate cu n noduri.

10

GRAF PARŢIAL, SUBGRAF

Definiţie:Un graf parţial al unui graf neorientat dat G=(V,E) este un graf G1= (V, E1), unde E1 E.Un graf parţial al unui graf dat, este el însuşi sau se obţine din G prin eliminarea unor muchii.

G=(V,E) G1= (V, E1),

Definiţie: Un subgraf al un ui graf neorientat G(V,E) este un graf G1=(V1, E1), unde V1 V. E1 E iar muchiile din E2 sunt toate muchiile din E care sunt incidente numai cu nodurile din mulţimea V1.

Un subgraf al unui graf este el însuşi sau se obţine din G prin suprimarea anumitor noduri şi a tuturor muchiilor incidente cu acestea.

11

3

2

4

5

1

3

2

4

5

1

3

2

4

5

1

34

5

1

G=(V,E) G1= (V1, E1),

PARCURGEREA GRAFURILOR NEORIENTATE

Parcurgerea grafurilor este o vizitare a nodurilor. Este importanta parcurgerea eficienta. Există două modalităţi de parcurgere:

Parcurgerea în lăţime BF- Breadth First Parcurgerea în adâncime DF

Parcurgerea în lăţime BF- Breadth First - se face incepând de la un nod i, pe care il considerăm vizitat.- Vizităm apoi toate nodurile adiacentecu el- fie ele j1, j2, ..., jk

- Vizităm toate nodurile adiacentecu j1 apoi j2, ..., jk

- Parcurgerea continuă în acest mod până cand au fost vizitate toate nodurile accesibile

Algoritmul este următorul:- parcurgerea se realizează prin utilizarea structurii coadă, având grijă ca fiecare

nod să fie vizitat o singură dată.- Nodul de pornire este introdus în coadă şi este marcat cu vizitat

o Cât timp coada este nevidă Pentru nodul aflat la inceputul cozii:

Se trec în coadă toate nodurile adiacente cu el, care nu au fost vizitate şi se marchează ca vizitate

Se afişează Se extrage din coadă

- Se folosesc notaţiile:o i_c indicele primei componente a coziio s_c indicele ultimei componente a coziio coada vectorul care memorează coada propriu-zisă

0, dacă nodul i a fost vizitato s vector ce reţine nodurile vizitate: s[i]=

1, dacă nodul i a fost vizitat

12

Programul de parcurgere BF (lăţime) a unui graf memorat prin liste de adiacenţă

#include <conio.h>#include<iostream.h>

int n, coada[50], s[50], i_c=1, sf_c=1, t[2][50], start[50], p;void citire_muchii (char nume_fis[20], int t[2][50], int start[50], int& n) { int i, j, k=0 ; fstream f(nume_fis,ios ::in) ; f>>n; while (f>>i>>j) { k++ ; t[0][k]=j; t[1][k]=start[i]; start[i]=k; k++; t[0][k]=i; t[1][k]=start[j]; start[j]=k; }

f.close();}

void bf(int nod){ coada[i_c]=nod; s[nod]=1; while (i_c<=sf_c) { p=start [coada[i_c]]; while (p) { if ( s [ t[0] [p] ]= =0) { sf_c++; coada [sf_c]=t[0][p]; s [ t[0] [p] ]=1;

13

} p=t[1][p]; } cout<<coada[i_c] <<endl ; }}

void main( ){ citire_muchii(“graf.txt”, t, start, n); bf(6); getch( );}

Programul de parcurgere BF (lăţime) a unui graf memorat prin matricea de adiacenţă

#include <conio.h>#include<iostream.h>int n, coada[50], s[50], i_c=1, sf_c=1, A[50][50], i;


}

void bf (int nod){ coada[i_c]=nod; s[nod]=1; while (i_c<=sf_c) { i=1; while (i<=n) { if (A[coada[i_c]][i]= =1 && s[i]= =0 ) { sf_c++;

14

coada[sf_c]=i; s[i]=1; } i++; } cout<<coada[i_c]<<endl; i_c++; }}void main( ){ CitireN( “graf.txt”, A, n); Bf(1); getch();}

Parcurgerea în adâncime DF- Depth First

- Parcurgerea în adâncime se face de la un nod i care se consideră vizitat.- După vizitarea unui nod, se vizitează primul dintre nodurile adiacente, nevizitate

încă, apoi următorul nod adiacent, până când au fost vizitate toate nodurile adiacente cu el.

- ………- Parcurgerea continuă în acest mod până când au fost vizitate toate nodurile

accesibile.

Programul de parcurgere DF (adâncime) a unui graf memorat prin liste de adiacenţă


int s[50], n, T[2][50], Start[50] ;Void Citire_LA (char Nume_fis[20], int T[2][50], int Start[50], int& n) { int i, j, k=0 ; fstream f(Nume_fis,ios ::in) ; f>>n; while (f>>i>>j) { k++ ; T[0][k]=j;

15

T[1][k]=Start[i]; Start[i]=k; K++; T[0][k]=i; T[1][k]=Start[j]; Start[j]=k; }

f.close();}

void df (int nod){ int p; cout<< nod <<” “; p=Start [nod]; s [nod]=1; while (p) { if ( s [ T[0] [p] ]= =0) df (T [0][p] ); p= T[1] [p]; }}

void main( ){ Citire_LA(“graf.txt”, T, Start, n); df(1); getch( );}

Programul de parcurgere DF (adâncime) a unui graf memorat prin matricea de adiacenţă


int s[50], n, A[50][50] ; void CitireN (char nume_fiş[20], int a[50][ 50], int &n)

{ int i,j;

16

fstream f(nume_fiş,ios :: in); f>>n; while (f>>i>>j) a[i][j]=a[j][i]=1; f.close();

}

void df_r (int nod){ int k; cout<< nod <<” “; s [nod]=1; for (k=1; k<=n; k++) if ( A[nod] [k] = =1 && s[k]= = 0) df_r(k); }

void main( ){ CitireN (“graf.txt”, A, n); df_r(1); getch( );}

Estimarea timpului necesar parcurgerii grafurilor

- Parcurgerea BF sau DF a grafurilor pornind de la matricea de adiacenţă, se face în O(n2). Pornind de la un nod i , se caută pe linia i a matricei toate nodurile adiacente cu el.- Parcurgerea BF sau DF a grafurilor pornind de la listele de adiacenţă se face în O( m). Pornind de la un nod i , se caută toate nodurile adiacente cu el. Dar acestea se găsesc deja grupate în lista asociată nodului respectiv şi numărul lor corespunde numărului de muchii incidente acestuia.

LANŢURI

17

Definiţie: Pentru graful neorintat G=( V,E), un lanţ L= [v1,v2,....,vp] este o succesiune de noduri cu proprie-tatea a oricare două noduri vecine sunt adiacente, adică (v1,v2) E, (v2,v3) E, ....(vp-i,vp) E. Un lanţ poate fi definit ca o succesiune de muchii (v1,v2) E, (v2,v3) E, ....(vp-i,vp) E.

Vârfurile v1 , vp se numesc extremităţile lanţuluiNumărul p-1 se numeşte lungimea lanţului. Acesta este dat de numărul de muchii ce unesc nodurile lanţului.

Definiţie: Se numeşte lanţ elementar un lanţ care conţine numai noduri distincte.

APLICAŢIEFiind dat un graf şi două noduri ale sale a şi b, să se scrie un program care decide dacă între ele există un lanţ sau nu, iar în caz că acest lanţ există, se cere să se afişeze lanţul.

Notă: intre a si b există lanţ doar dacă putem parcurge lanţul din a şi ajungem în b. Ne vom folosi de un vector T care are forma

j, dacă i este descendent al lui j T[j]=

0, dacă i nu a fost selectat

Programul afişează drumul, pornind de la matricea de adiacenţă a grafului.


int s[50], A [50] [50], n, T[50] , a, b ; void CitireN (char nume_fiş[20], int a[50][ 50], int &n)

18

3

2

4

5

1

Lanţ elementar- [ 1,2,3,4] cu lungimea 3

Lanţ neelementar [1,2,3,1,5] cu lungimea 4

{ int i,j; fstream f(nume_fiş,ios :: in); f>>n; while (f>>i>>j) a[i][j]=a[j][i]=1; f.close();

}

void refac( int nod){ if (nod!=0) { refac (T[nod]); cout<<nod<<’ “; }}

void df_r (int nod){ int k; s [nod]=1; for (k=1; k<=n; k++) if ( A[nod] [k] = =1 && s[k]= = 0) { T[k]=nod; df_r(k); }}

void main( ){ CitireN (“graf.txt”, A, n); cout<<”a=”; cin>>a; cout<<”b=”; cin>>b; df_r(a); if (T[b] != 0) refac (b); getch( );}

19

Programul afişează lanţul de lungime minimă aflat între nodurile a şi b ( parcurgere în lăţime DF )


int n, coada[50] , s[50], i_c=1, sf_c=1, A[50][50], I, T[50], a, b ;


}

void refac( int nod){ if (nod!=0) { refac (T[nod]); cout<<nod<<’ “; }}

void bf (int nod){ coada[i_c]=nod; s[nod]=1; while (i_c<=sf_c) { i=1; while (i<=n) { if (A[coada[i_c][i]= =1 && s[i]= =0 ) { sf_c++; coada[sf_c]=i; s[i]=1;

20

Fişierul text ptr graful nostru:

61 21 31 52 33 44 5

T[i]=coada[i_c]; } i++; } i_c++; }}

void main( ){ CitireN (“graf.txt”, A, n); cout<<”a=”; cin>>a; cout<<”b=”; cin>>b; df_r(a); if (T[b] != 0) refac (b); getch( );}

GRAF CONEX

Definiţie:

Un graf neorientat G=(V, E) este conex, dacă pentru orice pereche de noduri x, y V, există un lanţ în care extremitatea iniţială este x şi extremitatea finală este y.Un graf cu un singur nod este conex.

21

3

2

4

5

1

3

2

4

5

1 6

Graf CONEX Graful nu este CONEX ( nu există lanţ între nodul 1 şi 5)

COMPONENTE CONEXE

Definiţie:Fir G=(V, E) un graf neorientat şi G1= ( V1,E1) un subgraf al său. Atunci G1= ( V1,E1) este o componentă conexă a grafului G=(V, E) dacă sunt îndeplinte condiţiile:

Oricare ar fi x, y V1, există un lanţ de la x la y;Nu există un alt subgraf al lui G, G2= ( V2,E2) cu V1 V2 care îndeplineşte condiţia a).

Un graf cu n noduri poate avea un nr. de componente conexe cuprins între 1 şi n.Exemple:

Graful are 2 componente conexe Graful are 3 componente conexe (1,2,3), (5,6) (1,2,3,4),5, 6

APLICAŢIE:

Fiind dat un graf neorientat, se cere să se afişeze nodurile fiecărei componente conexe.

22

3

2

4

51

3

2

4

5

1 6

NOTĂ: parcurgem graful…de câte ori il parcurgem atâtea componente conexe avem.


int s[50], A [50] [50], n, i; void CitireN (char nume_fiş[20], int a[50][ 50], int &n)


}

void df_r (int nod){ int k; cout<<nod<<endl; s [nod]=1; for (k=1; k<=n; k++) if ( A[nod] [k] = =1 && s[k]= = 0) df_r(k); }

void main( ){ CitireN (“graf.txt”, A, n); for ( i=1; i<=n; i++) if (s[i]= =0) { cout<<”componeneta conexa “<<endl; df_r(i); cout<<endl; } getch( );}

23


61 21 31 52 33 44 5

CICLURI

Definiţie;

Un lanţ L care conţine numai muchii distincte şi pentru care nodul iniţial coincide cu nodul final se numeşte ciclu. Dacă cu excepţia ultimului nod, care coincide cu primul, lanţul este elementar, atunci ciclul este elementar ( adică, cu excepţia ultimului nod, care coincide cu primul, conţine noduri distincte.

APLICAŢIE: Fiind dat un graf conex, G=(V,E), să se scrie un program care decide dacă graful conţine cel puţin un ciclu.

NOTĂ: Graful conţine cel puţin un ciclu dacă, în timpul parcurgerii DF, algoritmul va ajunge în situaţia de a vizita un nod de două ori.


24

32

4

5

1 [1,2,3,1] ciclu elementar[1,2,1,] nu este ciclu pentru ca (1,2) şi (2,1) reprezintă aceaşi muchie, deci nu conţine muchii distincte

int s[50], A [50] [50], n, gasit; void CitireN (char nume_fiş[20], int a[50][ 50], int &n)


}

void df (int nod){ int k; s [nod]=1; for (k=1; k<=n; k++) if ( A[nod] [k] = =1 ) { A [k][nod]=0; if (s[k]= = 0) df (k); else gasit=1; } }

void main( ){ CitireN (“graf.txt”, A, n); df (1); if (gasit) cout<<” da”; else cout<<” NU”; getch( );}

Pentru a verifica matematic dacă există cel puţin un ciclu se face verificarea, m>n-1. Dacă este verificată înseamnă ca există cel puţin un ciclu.Dacă m=n-1 nu există cicluri

25


61 21 31 52 33 44 5

Dacă m<n-1 graful nu este conex, ceea ce ar contrazice cerinţa.

ARBORI

Definiţie: Se numeşte arbore un graf neorientat care este conex şi nu conţine cicluri.Exemplu un arbore cu 5 noduri.

Ex.: este conex pentru ca exista un lant intre orice doua varfuri x si y din V si nu are cicluri.

TEOREMĂ 1: Fie G un graf neorientat cu n noduri. G este arbore dacă şi numai dacă are n-1

muchii şi nu conţine cicluri.

Obs 1 : Orice arbore cu n varfuri are n-1 muchii.

Obs 2 : Orice arbore cu n>=2 varfuri contine cel putin 2 varfuri terminale.TEOREMA2 : Fie G=(V,M) un graf neorientat . Următoarele afirmaţii sunt adevărate:-G este arbore-G este un graf conex ,minimal in raport cu aceasta proprietate(daca se elimina o muchie oarecare din G se obtine un graf neconex)-G este fara cicluri ,maximal in raport cu aceasta proprietate (daca se adauga o muchie ,se va obtine cel putin un ciclu in graf)

26

3

4

5

21

Obs. In cazul arborilor in loc de varfuri si muchii se folosesc cu precadere termenii de noduri si arce.

APLICAŢIE: Se citeşte un graf. Să se scrie un program care verifică dacă este arbore.

#include <conio.h>#include<iostream.h>int s[50], A [50] [50], n, gasit, i, suma;


}

void df (int nod){ int k; s [nod]=1; for (k=1; k<=n; k++) if ( A[nod] [k] = =1 ) { A [k][nod]=0; if (s[k]= = 0) df (k); else gasit=1; }

}

void main(){ CitireN (“graf.txt”, A, n); df (1); suma=0; for (i=1;i<=n; i++) suma+=s[i]; if (suma !=n) cout<<” nu este conex”;

27


61 21 31 52 33 44 5

else if (gasit) cout<<”are ciclu ”; else cout<< “arbore “; getch( );}

Noțiuni caracteristice arborilor:

1)Nodul în care nu intra nici un arc sau nodul iniţial reprezintă rădăcina arborelui2) Cu excepţia nodului rădăcina , fiecare nod are proprietatea că în el intră un singur arc . Acest arc leagă nodul respectiv de un alt nod numit nod predecesor său părinte.3)Dintr-un nod pot ieşi mai multe arce.Fiecare astfel de arc leagă nodul respectiv de un alt nod numit succesor său fiu al nodului sau descendent.4)Nodurile sunt organizate pe nivele, primul nivel este ocupat de nodul rădăcină .Nodurile de pe ultimul nivel se carcterizeaza prin faptul că din ele nu mai iese nici un arc ,ele sn noduri terminale sau frunze.5)Înălţimea unui arbore este dată de nr nivelurilor sale -1 sau lungimea celui mai lung lanţ elementar

Ex N1 1- rădăcina arborelui Frunze : 3 4 5 7 8 Descendenții direcți ai lui 2 : 5 si 6

N2 Descendenți lui 2: 5 6 7 8 H=3

N3

N4

Reprezentarea arborilor :

Arborii fiind cazuri particulare de garfuri ,au aceleaşi metode de reprezentare ca şi grafurile.Există însă o formă de reprezentare specifică arborilor prin vectorul „taţilor” astfel:

28

1

2 3 4

5 6

7 8

Se alcătuieşte un tabel cu două linii şi coloane în număr egal cu număr de noduri respectând următoarele reguli:-pe prima linie se trec modurile -pe a doua linie ,pt fiecare nod se trece tatăl nodului respectiv

Mai clar :Pentru graf neorientat cu n vârfuri avem:T=(t[1],t[2],…t[n]) unde t[i] i 1..n reprezintă tatăl nodului i

Ex . Fiind dat vectorul de taţi al unui arbore(6,0,2,2,3,3,2,7,7,9) să se determine:- nodul rădăcină- frunzele grafului- reprezentarea grafică.

Def. Se numeşte arbore parţial al unui graf neorientat G=(V,M) un graf parţial al său care în plus este şi arbore.

Ex Dacă eliminăm [1,3] şi [2,4] se obţine un

arbore parţial

Def . Se numeşte arbore binar ,o mulţime finită de noduri care este:-fie vida- fie un arbore ordonat în care fiecare nod are cel mult doi descendenţi direcţi

Noţiuni : succesor stâng ,drept Subarbore stâng ,drept

ARBORE PARŢIAL:

Se obţine dintr-un graf prin eliminarea unui număr de muchii, păstrându-se un număr minim de muchii astfel incât graful rămas să fie conex şi fără cicluri.Exemplu:

29

2

4 5

3

1

2

4 5

3

1

1

2

3

4

Graf conex G=(V, E) Arbore parţial

Program pentru determinarea unui arbore parţial pornind de la un graf conex G =(V, E).

#include <conio.h>#include<iostream.h>int s[50], A [50] [50], n ;


}

void df_r (int nod){ int k; s [nod]=1; for (k=1; k<=n; k++) if ( A[nod] [k] = =1 && s[k]= = 0 ) { cout<<nod<<” “<< k<< endl; df_r(k); }

} void main( )

{ CitireN (“graf.txt”, A, n); df_r (1); getch();

30

Graf.txt61 21 31 52 33 44 5

}

BIBLIOGRAFIE

https://www.scribd.com/doc/225055268/Grafuri-neorientate

https://grafurineorientate.wordpress.com/

http://infoscience.3x.ro/c++/Grafuri%20neorientate.htm

31

Grafuri Neorientate.doc

Documents

Transcript of Grafuri Neorientate.doc