Adiacenta. Incidenta. Grad. -P.D

   Reamintim faptul ca un graf neorientat pune in evidenta o relatie simetrica, cum ar fi, de exemplu, cea care exista intre componentele unei retele de calculatoare.
   Varfurile unui astfel de graf (calculatoarele din retea) sunt conectate intre ele prin legaturi de comunicatie directa (muchiile grafului). Intr-o astfel de retea este necesar ca orice calculator sa poata comunica cu toate celelalte calculatoare prezente in retea. De aceea, graful respectiv trebuie sa aiba unele particularitati.
Fie G = (V,U) un graf neorientat in care V={x1,x2,…,xn}.

Definitie Se numeste graf neorientat o pereche ordonată de multimi (V,U), V fiind o multime finita si nevida de elemente numite noduri sau varfuri, iar U o multime de perechi neordonate (submultimi de două elemente) din V numite muchii.

 Definitie Numim muchii adiacente două muchii cu o extremitate comuna. Pentru exemplul de mai sus, muchii [1,5] şi [5,4] sunt muchii adiacente pentru ca au ca extremitate comuna nodul 5. 

 

! Matricea de adiacenta asociata unui graf neorientat este o matrice simetrica.

Adiacenta: Intr-un graf neorientat existenta muchiei (v,w) presupune ca w este adiacent cu v şi v adiacent cu w.

In exemplul din figura, varful 1 este adiacent cu 4 dar 1 şi 3 nu reprezinta o pereche de varfuri adiacente.

Incidenta: o muchie este incidenta cu un nod daca il are pe acesta ca extremitate. Muchia (v,w) este incidenta in nodul v respectiv w.

Grad: Gradul unui nod v, dintr-un graf neorientat, este un numar natural ce reprezinta numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

In graful de mai jos avem:

1. Nodurile 2 si 3 se numesc adiacente.
2. Nodul 4 este un nod terminal.
3. Pentru nodul 2 putem spune ca 3 reprezinta gradul sau.
4. Muchia (2,5) si nodul 2 se numesc incidente