Referat Bazele Informaticii

Mai jos puteti citi fragmente din Referat Bazele Informaticii si de asemenea puteti face Download Referat Bazele informaticii

Citeste fragmente din Referat Bazele Informaticii

Bazele informaticii Grafuri orientate Def: Se numeste graf orientat o pereche ordonata de multimi G=(X,U) unde X este o multime finita si nevida numita multimea varfurilor (nodurilor) iar U este multimea formata din perechi ordonate de elemente distincte din X numita multimea arcelor. Def2: Se numeste graf orientat o pereche ordonata G=(X,U) unde X este o multime finita si nevida numita multimea varfurilor ; U este o familie de perechi ordonate de varfuri din X, numita familia de arce. Numim grad exterior al unui varf x, notat d+ (x), numarul arcelor de forma (x,y) apartinand lui U. Numim grad interior al unui varf x, notat d- (x), numarul arcelor de forma (y,x) apartinand lui U. Se numeste graf partial al unui graf orientat G=(U,V) un graf orientat G1 =(X,V) cu V inclus in U (deci este g insusi sau se obtine prin suprimarea unor arce). Se numeste subgraf al unui graf orientat G=(X,U) un graf H=(Y,V) unde Y inclus in X iar arcele din V sunt toate arcele din U care au ambele extremitati in multimea Y (deci este G insusi sau se obtine din G prin suprimarea a anumitor varfuri si a arcelor incidente cu acestea). Se spune ca H este indus sau generat de multimea de varfuri Y. Un graf orientat este complet daca oricare doua varfuri distincte sunt adiacente. Un graf orientat G=(X,U) se numeste conex daca pentru oricare doua varfuri distincte x,y apartin lui X exista in G un lant de extremitati x,y. Se numeste componenta conexa a unui graf orientat G un subgraf conex al sau maximal in raport cu aceasta proprietate (oricare ar fi un nod din subgraf nu exista lant intre acel nod si varfurile care nu fac parte din subraf). Grafuri neorientate Def: Se numeste graf neorientat o pereche ordonata de multimi (X,U), X fiind o multime finita si nevida de elemente numite noduri sau varfuri, iar U o multime de perechi neordonate (submultimi cu doua elemente) din X, numite muchii. Gradul unui varf x este dat de numarul muchiilor incidente cu x. Se noteaza cu d(x) (‘d’ reprezinta prima litera din cuvantul degre din limba franceza si care inseamna grad). Un graf partial al grafului G=(X,U) este un graf G 1 =(X.V) daca G1 are aceeasi multime de varfuri ca G iar multimea de muchii V este chiar U sau o submultime a acesteia. Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel incat Y este inclus in X iar V contine toate muchiile din U care au ambele extremitati in Y. Vom spune ca subgraful H este indus sau degenerat de multimea de varfuri Y. Se numeste graf complet cu n varfuri un graf care are proprietatea ca orice doua noduri diferite sunt adiacente. Tare conexitate Un graf G=(X,U) este tare conex daca lxl=1 sau pentru oricare doua varfuri x,y apartin lui X exista un drum de la x la y si un drum de la y la x. O componenta tare conexa a unui graf G=(X,U) este un subgraf G1=(X1,Y1) al lui G care este tare conex si care este maximal in raport cu aceasta proprietate, adica oricare ar fi x apartine XX1 subgraful lui G generat de X1 reunit cu{x} nu mai este tare conex. Drum critic Numim drum critic al unui graf de activitati un drum de lungime maxima care leaga nodul initial de nodul final. Un graf de activitati este asociat unei lucrari complexe a carei realizare presupune desfasurarea mai multor actiuni (procese, activitati). 쥁@