Grafuri neorientate

Se numeste graf neorientat, o pereche ordonata de multimi notata G= (X, U), unde X={x1, x2,... xn} este o multime finite si nevida de elemnte numite noduri sau varfuri, iar U={u1, u2,... un} este o multime de perechi neordonate de elemente din X numite muchii.

Asadar un neorientat poate fi reprezentat sub forma unei figure geometrice alcatuite din puncte (noduri, varfuri) si linii drepte sau curbe care unesc aceste puncte (muchii, arce). Doua muchii care au o extremitate comuna se numesc incidente. 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.

Matricea de adiacenta Este o matrice patratica cu n linii si n coloane, in care elementele a[i, j] se definesc astfel: a[i, j]=1 daca exista (i, j) in U, cu x diferit de y si 0 daca nu exista (i, j) in U.

Pentru graful G= (X, U) din figura de mai jos, matricea de adiacenta este: 0 1 1 1 1 1 0 1 0 2 A= 1 1 0 1 3 coloana 1 2 3 4 a[i, j]=a[j, i] oricare ar fi i, j ({1, 2, .... n} Proprietatile matricei de adiacenta: Este o matrice simetrica; Pe diagonala principala are toate elemntele egale cu 0; Suma elementelor pe linia sau coloana i este egala cu gradul nodului i; Daca elementele pe linia/coloana i sunt toate egale cu 0 atunci nodul este izolat; Daca toate elementele din matrice, mai putin cele de pe diagonala principala, sunt 1 inseamna ca graful este complet.

Listele vecinilor Pentru fiecare nod al grafului se retin nodurile adiacente cu el.

Pentru reprezentarea listei de adiacenta se poate folosi alocare dinamica.

Exemplu pentru matricea de adiacenta de mai sus: 2, 3, 4 1, 3 1, 2, 4 1, 3 Vectorul muchiilor Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem defini tipul de date tmuchie, astfel: type tmuchie=record nod1, nod2: integer; end; Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de ...