Teorie "Grafuri si arbori"

       Se numeste graf neorientat o pereche de forma (X,E) unde x este egal cu multimea nodurilor sau a varfurilor, E= {(xi,xj), xi,xj ∈ X}
       Doua varfuri se numesc adiacente daca exista o muchie care le leaga. 
       O muchie e incidenta la un varf daca unul dintre capetele muchiei este varful respectiv.
       Gradul unui varf reprezinta numarul de muchii incidente lui.
       Suma gradelor intr-un graf neorientat este de 2 ori numarul de muchii.
       Matricea de adiacenta este o matrice patratica unde n reprezinta numarul de varfuri cu proprietatea ca a(i,j)= 1, daca exista muchia (i,j) si 0 daca nu exista muchia (i,j)
       Se numeste lant o succesiune de muchii.
       Se numeste ciclu un lant in care extremitatea intiala este egala cu cea finala.
       Un graf se numeste conex daca oricare ar fi 2 varfuri din acel graf exista cel putin un lant care leaga.
       Un arbore este un graf conex fara ciclu.
     

Niciun comentariu:

Trimiteți un comentariu