ARBORI

 Din punct de vedere structural arborii sunt cele mai simple grafuri.

Pentru varfurile unui arbore vom folosi notiunea de nod

Def: Un graf conex si fara cicluri se numeste arbore.

Def:  Un arbore A este fie vid, fie format dintr-un nod radacina ( R ), caruia ii este atasat un numar finit de arbori. Acestia sunt subarbori a lui A.

Intre doua noduri pot fi relatiile (“tata”, “fiu”, “Frate”), descendent sau urmas – fiul fiului; ascendent sau stramos – tatal tatalui.

Avem noduri terminale si frunze.

Numarul de descendenti directi reprezinta ordinul nodului.

Def:  Daca fiecare din nodurile unui arbore are cel mult doi descendenti directi (fii) atunci arborele se numeste arbore binar.

Def:  Fie G = (X, U) cu n > 1 noduri si m muchii si p componente conexe.

                n (G) = m – n + p se numeste numarul ciclomatic al grafului G

Def: Fie G un graf. Un subgraf partial al sau care este arbore se numeste arbore partial.

Prop: Un graf cu n noduri este arbore daca si numai daca are n-1 muchii si nu contine cicluri.

Parcurgerea arborilor – in latime si adancime – la fel ca la grafuri

Teorema:  Fie H = (X, U) cu n > 1 noduri si m muchii si p componente conexe atunci următoarele afirmaţii sunt echivalente:

      1. G conex si fără cicluri           

      2. G fără cicluri si m=n-1    

      3. G conex si m=n-1

      4. G fără cicluri, maximal (prin adăugarea unei muchii rezultă un ciclu si numai unul)

      5. G graf conex minimal (dacă se elimină o muchie nu mai este conex)

      6. Oricare pereche de noduri este legată de un lanț si numai unul 

Demonstraţie :

1)Þ 2). Afirmația fără cicluri este prezentă atât la ipoteză cât și la concluzie. Din   n (G) = m – n + p avem p=1 și n (G) = 0 deci  0 = m - n + 1  adică  m = n - 1.

2)Þ3).  Afirmația m=n-1 este prezentă atât la ipoteză cât și la concluzie.  Din  n  (G) = m – n + p avem m=n-1 și n (G) = 0 deci  0 = (n-1) - n  + p  adică  p = 1, adică G conex.

3)Þ4).  Avem  n (G) = m – n + p știm că p=1 și m = n - 1. Presupunem că mai adăugăm o muchie. Deci vom avea n muchii. Atunci   n (G) = n - n + 1 = 1 deci s-a format un ciclu.

4)Þ5).  Presupunem că nu este conex minimal, înseamnă că prin eliminarea unei muchii se va obține tot un graf conex, ceea ce înseamnă că inițial am avut un ciclu, ceea ce intră în contradicție cu ipoteza.

5)Þ6).  Dacă graful este conex rezultă că între oricare două noduri există un lanț. Mai trebuie să demonstrăm că este unic. Dar dacă între două noduri ar exista două lanțuri atunci rezultă că se formează un ciclu. Atunci s-ar putea elimina o muchie și s-ar obține tot un graf conex, ceea ce intră în contradicție cu ipoteza.

6)Þ1). Oricare pereche de noduri este legată de un lanț rezultă că graful este conex. Presupunem că graful are cicluri ceea ce implică existența a două noduri între care există două lanturi distince ceea ce contrazice ipoteza.