Grafuri - Definitii, tipuri

Grafuri

Definitii, tipuri

Notiunile de algoritm si schema logica pot fi definite, explicate si mai ales foarte des utilizate in legatura cu elemente de teoria grafurilor.

Se umeste graf neorientat o pereche ordonata G = ( X, U ), unde X este o multime finita si nevida de elemente numite noduri ( varfuri ), iar U este o multime de perechi neordonate de elemente distincte ale lui X, numite muchii.

Se numeste lant intr-un graf G = ( X, U ) o succesiune de muchii de forma [i₁,i₂], [i₂,i₃],,[in_-1,in], notata prescurtat prin [i₁,i₂,in]

Un lant in care muchiile sunt diferite doua cate doua se numeste ciclu.

Un varf care este extre,otatea imeo somgire ,icjoo se mi,este varf terminal.

Doua varfuri unite printr-o muchie se numesc varfuri adiacente.

Un graf orientat este o pereche ordonata G = ( X, U ), deosebirea fata de graful neorientat constand in faptul ca elementele lui U sunt perechi ordonate de varfuri numite arce. In cazul grafurilor orientate, notiunile de lant si ciclu isi au corespondent in notiunile de drum si circuit.

Arbori

Se numeste arbore un graf neorientat, conex,

OBSERVATIE: Intr-un arbore cu nvarfuri, exista cel putin doua varfuri terminale.

Se poate demonstra, cu privire la grafuri, teorema:

Fie G un graf neorientat, cu n1 varfuri. Urmatoarele afirmatii sunt echivalente:

1. G este un arbore;

2. G are n-1 muchii si nu contine cicluri;

3. G are n-1 muchii si este conex;

4. Orice doua varfuri din G sunt unite printr-un unic lant.

Se numeste arbore binar un arbore orientat, in care fiecare varf are cel mult doi descendenti, facandu-se insa distinctia intre descendetul stang si cel drept al fiecarui varf.

Se numeste arbore de sortare un arbore binar cu proprietatile:

INF(i) INF(j) pentru orice varf j din subarborele stang al lui i;

INF(i) INF(j) pentru orice varf j din subarborele drept al lui i.