Grafuri

Definitii

- Se numeste graf sau graf neorientat o structura G=(V,E), unde V este o multime nevida iar E este o submultime posibil vida a multimii perechilor neordonate cu componente distincte din V.

GRAF ORIENTAT

- Fie G=(V,E) un graf. Elementul vIV se numeste virf izolat daca, pentru orice e I E, v nu este incident cu e.

- Graful G=(V,E) este graf finit, daca V este o multime finita.

- Fie Gi =(V i,Ei), i=1,2 grafuri. G2 este un subgraf al grafului G1 daca V2 e inclus in V1 si E2 e inclus in E1. G2 este este un graf partial al lui G1 daca V2=V1 si G2 este subgraf al lui G1.

- Un digraf este o structura D=(V,E), unde V este o multime nevida de virfuri, iar E este o multime posibil vida de perechi ordonate cu componente elemente distincte din V. Elementele multimii E sint numite arce sau muchii ordonate. Un graf directionat este o structura D=(V,E), unde V este o multime nevida de virfuri, iar E este o multime posibil vida de perechi ordonate cu componente elemente din V, nu neaparat distincte. Evident, orice digraf este un graf directionat.

- Se numeste graf ponderat o structura (V,E,W), unde G=(V,E) este graf si W este o functie numita pondere care asociaza fiecarei muchii a grafului un cost/cistig al parcurgerii ei.

- Fie G=(V,E) un graf, u,vIV. Secventa de virfuri u0, u1, , un este un u-v drum daca u0=u, un=v, uiui+1IE pentru toti i.

- Doua grafuri sunt izomorfe daca au acelasi numar de noduri si de muchii si daca exista o numerotare a nodurilor din cele doua grafuri astfel incat doua noduri sunt unite (printr-o muchie) pe primul graf daca si numai daca nodurile corespunzatoare sunt unite si pe al doilea graf. In grafuri izomorfe, nodurile corespunzatoare au ordine egala.

- Numim graf orientat pereche ordonata de multimi, notata G=(X,U), unde X este o multime finita si nevida de elemente numite noduri sau varfuri, iar U este o multime de perechi ordonate de elemente din X numite arce.

GRAF ORIENTAT

Pentru o muchie UK=(x,y), vom spune ca :

- varfurile x si y sunt adiacente si se numesc extremitatile muchiei UK;

- muchia UK si varful x sunt incidente in graf (la fel, muchia UK si varful b);

- muchia (x,y) este totuna cu (y,x) (nu exista o orientare