Grafuri neorientate

Se numește graf neorientat perechea ordonată de mulțimi G=(X,U), unde X este o mulțime finită și nevidă numită mulțimea nodurilor (vârfurilor), iar U este o mulțime de perechi neordonate de forma [x,y], cu x,y∈X, numită mulțimea muchiilor grafului.
  • numărul nodurilor (vârfurilor) se notează cu n
  • numărul muchiilor (legăturilor) se notează cu m

Reprezentarea grafică a unui graf

  • Nodurile se reprezintă prin puncte sau cercuri numerotate;
  • Muchiile se reprezintă prin linii care vor uni nodurile corespunzătoare
grafuri neorientate

Terminologie

1. Nod (vârf)

Nodurile sunt punctele unui graf și alcătuiesc mulțimea nodurilor.
  Ele se numerotează fie cu cifre, fie cu litere, pentru a putea fi diferențiate. Mulțimea nodurilor se notează cu X și conține toate nodurile unui graf.

Exemple: Mulțimea nodurilor grafului 1 este formată din 5 elemente, și anume nodurile: {1,2,3,4,5}. Pentru graful 2, X={a,b,c,d,e}.

2. Muchie

Muchiile sunt legături ce unesc între ele nodurile corespunzătoare perechilor.

  Pentru a ne referi la muchia dintre nodurile x și y, le vom scrie „ca într-un interval închis”: [x,y] == [y,x]. Deoarece ne referim la un graf neorientat, sensul muchiei nu contează, astfel că putem pune nodurile în ce ordine dorim.

  Mulțimea muchiilor se notează cu U și conține toate muchiile grafului.

Exemple: Mulțimea muchiilor grafului 1 este mulțimea vidă, întrucât este un graf nul. Mulțimea muchiilor grafului 2 este U={[a,b],[a,d],[c,d]}.

3. Adiacență

Două noduri x și y se numesc adiacente dacă formează o muchie în plan.

    Exemple (graful 2):
  • nodul a este adiacent cu nodurile d și b;
  • nodul e nu este adiacent cu niciun nod;
  • nodul b este adiacent cu nodul a.

4. Incidență

Două muchii se numesc incidente dacă au o extremitate comună.

    Exemple (graful 2):
  • muchia [a,d] este incidentă cu muchia [c,d] <=> d este vârf comun;
  • muchia [a,b] nu este incidentă cu muchia [c,d], deoarece nu au niciun nod în comun.

Un vârf este incident cu o muchie dacă este extremitate a acesteia.

    Exemple (graful 2):
  • nodul a este incident cu muchia [a,d] și muchia [a,b];
  • nodul a nu este incident cu muchia [c,d], deoarece nu este extremitate a acesteia.

5. Gradul nodurilor

Se numește gradul unui vârf x, numărul de vârfuri adiacente cu x (numărul de muchii incidente cu x).

Se notează cu d(x) și ia valori din intervalul [0,n).

    Exemple:
  • gradele nodurilor din graful 1 sunt 0 (graful nu are nicio muchie);
  • în graful 2, nodurile a și d au cel mai mare grad, 2, deoarece au câte 2 muchii incidente („pleacă” câte 2 muchii din fiecare).

6. Nod izolat

Se numește nod izolat nodul care are gradul 0 (nu are nicio muchie incidentă).

    Exemple:
  • toate nodurile grafului 1 sunt izolate;
  • în graful 2, nodul e este singurul care are gradul 0, deci singurul nod izolat.

Proprietăți ale grafurilor neorientate

  • numărul maxim de muchii dintr-un graf neorientat cu n noduri este C2n    , sau n*(n-1)/2 ;
  • suma gradelor nodurilor unui graf neorientat este egală cu dublul numărului de muchii;
  • numărul de grafuri neorientate cu n vârfuri este egal cu 2C2n    , sau 2n*(n-1)/2 ;
  • numărul minim de muchii astfel încât un graf să nu conțină vârfuri izolate este [(n+1)/2] (parte întreagă);
  • numărul maxim de muchii astfel încât un graf să nu conțină vârfuri izolate este C2n-1    +1.