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 X X1 subgraful lui G generat de X1 reunit cu{x} nu mai este tare conex.
