referat, referate , referat romana, referat istorie, referat geografie, referat fizica, referat engleza, referat chimie, referat franceza, referat biologie
 
Informatica Educatie Fizica Mecanica Spaniola
Arte Plastice Romana Religie Psihologie
Medicina Matematica Marketing Istorie
Astronomie Germana Geografie Franceza
Fizica Filozofie Engleza Economie
Drept Diverse Chimie Biologie
 

Arbori

Categoria: Referat Informatica

Descriere:

Se observa ca oricare ar fimuchia arborelui pe care am suprima – o se obtine un graf neconex care are doua componente conex . De asemenea oricare ar fi perechea de varfuri neadiacente ale unui arbore pe care le – am unii printr-o muchie se creaza un ciclu unic. De exemplu, daca adaugam muchia [ 3 , 4 ] apare ciclul [ 2 , 3 , 4 , 2 ], daca adaugam muchia [ 5 , 7 ] apare ciclul [ 5 , 1 , 10 , 7 , 5 ] etc. Aceste proprietati au loc pentru orice arbore...
Varianta Printabila 
Free Download Referat Word
Dimensiune: 77KB
Free Download Referat PDF
Dimensiune: 8.075KB

Arbori

            Un graf conex si fara cicluri se nmeste arbore . In urmatorul desen vom avea un arbore cu 10 vârfuri .

Se observa ca oricare ar fimuchia arborelui pe care am suprima – o se obtine un graf neconex care are doua componente conex . De asemenea oricare ar fi perechea de varfuri neadiacente ale unui arbore pe care le – am unii printr-o muchie se creaza un ciclu unic De exemplu , daca adaugam muchia [ 3 , 4 ] apare ciclul [ 2 , 3 , 4 , 2 ] , daca adaugam muchia [ 5 , 7 ] apare ciclul [ 5 , 1 , 10 , 7 , 5 ] etc . Aceste proprietati au loc pentru orice arbore , asa cum rezulta din teorema : urmatoarele afirmatii sunt echivalente pentru un graf G :
  • G este un arbore .
  • G este un graf conex minimal , adica G este conex si daca ii suprimam o muchie oarecare [x ,y ]. Graful obtinut devine neconex.
  • G este un graf fara cicluri maximal , adica G nu contine cicluri si daca x si y sunt doua varfuri neadiacente ale lui G atunci graful obtinut din G prin adaugarea muchiei [x , y ] contine un ciclul.
    • Proprietati ale arborilorCorolar un graf G contine un arbore partial daca si numai daca G este conex .
    Orice arbore cu n >= 2 varfuri contine cel putin 2 varfuri terminale ( de gradul 1 ) .
    Orice arbore cu n varfuri are n – 1 muchii .                                   Arbori binari si aplicatii              Un arbore binar se defineste in modul urmator : un arbore care are un varf numit radacina , al carui grad este 0 , unu sau doi . Daca gradul radacinii este 0 , arborele binar este format numai din radacina . In caz contrar , radacina se leaga printr – o muchie sau prin doua muchii de unul sau de doua alte noi varfuri care se deseneaza sub radacina care se numesc fiii varfului radacina . Modul in care varfurile fiu se deseneaza sub radacina , la stanga sau la dreapta , are importanta . Aeste noduri fiu au fiecare 0 , 1 , 2 noduri fiu , la stanga sau la dreapta s.a.m.d. Vom spune ca radacina arborelui are nivelul 0 , fii radacinii nivelului 1 , fii acestora nivelul 2 , descendentii de ordin k ai radacinii nivelul k si ii vom desena la aceeasi inaltime fata de marginea de jos a unei pagini.
    Referat oferit de www.ReferateOk.ro
    Home : Despre Noi : Contact : Parteneri  
    Horoscop
    Copyright(c) 2008 - 2012 Referate Ok
    referate, referat, referate romana, referate istorie, referate franceza, referat romana, referate engleza, fizica