Grafuri Neorientate

Grafuri neorientate

Definiţie. Se numeşte graf neorientat o pereche ordonată de mulţimi (X, U), X fiind o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U o mulţime de perechi neordonate ( submulţimi cu două elemente) din X, numite muchii.

Ex.

Fig.1

Pentru graful de mai sus avem:

X={1, 2, 3, 4, 5, 6, 7, 8}

U={[1,2], [1,4], [1,5], [2,3], [2,5], [3,4], [6,7]}

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 a muchiei);

Dacă u1 şi u2 sunt două muchii care au o extremitate comună ele se vor numi adiacente

Definiţie. Un graf parţial al grafului G=(X,U) este un graf G1=(X,V) astfel încât VU, adică G1 are aceeaşi mulţime de vârfuri ca G iar mulţimea de muchii V este chiar U sau o submulţime a acesteia.

Ex. Mai jos avem un graf parţial al grafului de mai sus (Fig.1)

Fig.2

Cu alte cuvinte, un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de vârfuri şi eliminând o parte din muchii.

Definiţie. Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel încât Y X iar V conţine toate muchiile din U care au ambele extremităţi în Y. Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri Y.

Ex. Mai jos avem un subgraf al grafului din Fig.1 obţinut prin eliminarea nodului 3

Definitie:

Gradul unui varf x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).

Exemplu: d(1)=3, d(2)=2, d(4)=0, d(5)=1.

- Un varf care are gradul 0 se numeste varf izolat(de exemplu varful 4).

- Un varf care are gradul 1 se numeste varf terminal(de exemplu varful 5).

Propozitie:

Fie G=(X,U) un graf neorientat cu n noduri si m muchii, suma gradelor tuturor nodurilor este egala cu 2m.

Intr-un graf neorientat numarul nodurilor de grad impar este un numar par.

- Se numeste graf partial al grafului G=(X,U) un graf neorientat G’=(X,V), unde VÍX. Altfel spus, un graf G’ a lui G, este chiar G sau se obtine din G pastrand toate varfurile si suprimand niste muchii.

- Se numeste subgraf al grafului G=(X,U) ungraf neorientat H=(Y,V), unde YÍX iar V contine toate muchiile din U care au ambele extremitati in multimea Y.

Reprezentarea grafurilor neorientate

Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt: matricea de adiacenta, listele vecinilor si vectorul muchiilor.