Grafuri

Proiect la informatica

Grafuri

Un graf este o pereche ordonata de multimi (X,U) , unde X este multimea finite si nevida de elemente numita varfuri(noduri), iar U este multimea de perechi din X(submultimi cu 2 elemente) numite arce(muchii)

Notatie : G=(X,U)

G=graful

X=multimea nodurilor(A,B,C,D) C e

U=multimea arcelor(c,g,e,b,f,a) c

g f

B

b a

D

Grafuri neorientate

Nod(varf)

Muchie(arc)

Nod izolat

Daca multimea U are proprietatea de simetrie, G (X,U) este neorientat altfel este orientat.

Varfurile alaturate sunt adiacente, in extremitatile arcelor aflandu=se nodurile.

Un varf este incident cu o muchie daca reprezinta o extremitate a acestuia.

Gradul unui varf X este dat de numarul muchiilor adiacente cu acel varf.

Reprezentarea grafurilor.Memorare

Matricea de adiacenta:

0 1 1 0 0

1 0 1 0 0

1 1 0 1 0

0 0 1 0 0

0 0 0 0 0

Pentru ca elementele matricii sunt doar 0 si 1 matricea se mai numeste si booleana.

Constructia liste de adiacenta:

Varful(k) Varfuri adiacente cu varful (k)

2,3,4

1,3

3 2,4

4 3

5 0

Lista varfurilor adiacente:

2,3,4

1,3

2,4

3

0

Lista de adiacenta:

Tipuri de grafuri:

Graful nul:

-nu are muchii

-nodurile sunt isolate

Graful complet:

-fiecare nod are muchii spre toate celelalte noduri

-graful complet neorientat are x(x-1) / 2 noduri

Graful partial :

Graf originar :

Graf partial:

-graful partial se obtine suprimand din graful originar anumite muchii dar pastrand toate varfurile

Graful - Subgraf al unui graf

Graf ordinar :

Subgraf:

Graful complementar:

Graf originar:

Graf complement :

-Un graf este complementar altui graf daca varfurile adiacente in primul graf nu sunt adiacente in al doilea graf.

-multimea varfurilor este egala

-prin reuniunea muchiilor din cele 2 grafuri se obtine multimea muchiilor unui graf ccomplet.

Elemente :

Lant:

-elementar: L=[1,4,3,6]

-neelementar: L=[1,2,3,6,3,4]

-lungimea lantului o determina numarul de muchii

Ciclul:

-elementar : L=[1,4,3,2,1]

-neelementar: L=[1,2,3,6,3,4,1]

Graf conex:

-un graf este conex daca dintr-un oricare nod putem ajunge in orice alt nod

Graf Hamiltonean:

Graf hamiltonean se poate numi un ciclu care cuprinde toate nodurile si trece doar o data prin fiecare.

Teorema: Daca un graf are minim 3 noduri , iar gradul fiecarui nod este mai mare sau egal decat jumate din numarul nodurilor este hamiltonean.

Graf Eulerian:

Un lant eulerian contine toate muchiile doar o data, iar daca varful initial coincide cu cel final atunci se numeste ciclu eulerian .

Teorema: Daca graful este conex si gradul fiecare nod este par atunci graful se numeste eulerian.

Parcurgerea grafurilor:

In latime(BF):

1,2,4,3,6

In adancime (DF):

6,3,2,1,4

Grafuri orientate(digraf)

Elemente :nod, arc, adiacenta, incidenta, incidenta exterior,I ncidenta spre interior, successor, predecessor, bucla, p-graf, f-graf, gradul exterior, gradul interior, graf partial, subgraf, lant, drum, circuit, reprezentare grafica orient, graf complet, graf tare complet, graf turneu, graf tare conex, componenta tare conexa, formule.

-noduri:1,2,3,4

-arc:[2,1] , [1.4] , [2,3] , [3,2] , [4,3] ;

-adiacenta:daca intre 2 noduri exista arc atunci nodurile se numesc adiacente:

1 adiacent cu 4 ; 4 adiacent cu 3;

-incidenta: un nod este incident cu un arc daca este o extremitate a arcului :

1 incident cu [2,1] ; 4 incident cu [1,4];

-incidenta spre exterior:

2 incident spre ext cu [2,1];

-incidenta spre interior:

4 incident spre interior cu [4,2]

-succesor: succesorul lui 4 este 3

-predecesor : predecesorul lui 4 este 1

-bucla: [2,2]

-p-graf:daca nr arcelor este mai mic sau egal decat "p" atunci graful:

daca p=3 nu e p-graf

daca p=7 e p-graf

-graf exterior:nr arcelor care ies din acel nod

d+(4)=2

-graf interior: nr arcelor care intra in acel nod

d-(4)=1

-lant:o succesiune de noduri intre care exista arce

1,2,3:elementar, lungime 2

2,3,4,2,1 : neelementar, lungime 4

-drum:4,2,3

-circuit:succesiuea de noduri intre care exista arce si ultimul nod se repeta(se tine cont de orientare): 4,2,1,4 :elementar

4,2,3,2,1,4: neelementar

-graf complet:daca intre oricare 2 noduri I si j exista un arc ori de la I la j ori de la j la i

-graf tare complet:cand exista arc de la I la j si de la j la i

-graf conex:intre oricare noduri I si j exsita un lant

-graf tare conex : cand intre oricare 2 noduri exista drum

-graf turneu:intre oricare 2 noduri I si j daca exista un arc de la I la j nu poate sa existe arc de la j la i

-formule :

Reprezentarea grafurilor orientate

Matricea de adiacenta

- 0 daca nu exista arc intre i si j

a[i,j] - 1 daca exista arc

-numarul 1 de pe linia I ne da graful exterior al nodul I

-numarul 1 de pe coloana I ne da gradul interior al nodul i

0 0 0 1

1 0 1 0

0 1 0 0

0 1 1 0

Matricea varfuri arce:

-0 daca nu exita arc intre I si j

A[I,j] -1 daca nodul este exterior

-1 daca nodul este interior

-are dimensiunea m(nr de noduri) X n(nr de arce)

	n1	n2	n3	n4	n5	n6
				n1
				n2
						N5
			n3
				N4
				N6

Listele vecinilor

L+ L-

1 4 2

2 1,3 3,4

3 2 2

4 2,3 1

Vectorul de muchii:

n1

n2

n3

n6

n4

n5

n1

n2

n3

n4

n5

n6

Matricea drumurilor:

- 0 daca nu exista drum intre I si j

A[i,j] - 1 daca exista drum

-dimensiunea n*n

-nu e simetrica

1 2 3 4

1 1 1 1 1

2 1 1 1 1

3 1 1 1 1

4 1 1 1 1

Arbori

Definitia:Arbor se poate numi un graf conex , aciclic(fara ciclu).

In loc de varfuri si muchii se folosesc termenii noduri si arce.

Exista un nod in care nu intra nici un arc numit radacina arborelui

Cu exceptia radacinii fiecare nod are proprietatea ca in el intra un singur arc.

-acesta leaga nodul respective de un alt nod numit predecessor sau parinte.

Dintru-un nod pot iesi unul sau mai multe arce.Acestea se numesc successor sau fiu al nodului.

Nodurile sunt organizate pe nivele, primul nivel fiind ocupat de nodul radacina.Nodurile de pe ultimul nivel au proprietatea ca din ele nu mai iese nici un arc si se numesc noduri terminale sau frunze.

Nodurile pot contine o " informatie utila " care poate fi de orice tip (cheia arborelui).

Def : Un arbore cu proprietate ca fiecare nod cu exceptia frunzelor are cel mult 2 descendenti(succesori) se numeste arbore binary.Cei 2 succesori ai unui nod se numesc succesor stang si succesor drept.

Un arbore cu proprietatea ca fiecare nod cu exceptia frunzelor are exact 2 descendeti se numeste arbore binar complet.

Reprezentarea si parcurgerea arborilor binari:

Radacina stanga dreapta:

RSD:1 2 3 4 5 6

Stanga radacina dreapta:

SRD:3 2 5 4 1 6

Stanga dreapta radacina:

SDR:3 5 4 2 6 1

Bibliografie:

Cursul de informatica :prof. Osztian Erika, Vera Radovici