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

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 


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