Grafuri neorientate

Pentru reprezentarea grafică a unui graf neorientat, se iau în considerare următoarele:

• nodurile se reprezintă prin puncte, sau cercuri numerotate;
• muchiile se reprezintă prin linii și unesc nodurile între ele.

Există câteva definiții și termeni de bază pentru grafurile neorientate.

Nod (vârf)

Nodurile sunt punctele unui graf, ce alcătuiesc mulțimea nodurilor.

Ele se numerotează fie cu cifre, fie cu litere, pentru a putea fi deosebite. Mulțimea se notează în general cu $X$ și conține toate nodurile grafului.

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\}$.

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ă $\emptyset$, întrucât este un graf nul;
• mulțimea muchiilor grafului $2$ este $U=\{[a,b],[a,d],[c,d]\}$.

Adiacență

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

Exemple: (graful 2)

• $a$ este nod adiacent cu nodurile $d$ și $b$;
• nodul $e$ nu este adiacent cu niciun nod;
• nodul $b$ este adiacent cu nodul $a$.

Incidență

Numim muchii incidente două muchii care au o extremitate comună (un nod comun).

Exemple: (graful 2)

• $[a,d]$ este muchie incidentă cu muchia $[c,d] <=> d$ este vârf comun;
• $[a,b]$ nu este muchie incidentă cu muchia $[c,d]$, deoarece nu au niciun nod în comun.

Un nod 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.

Gradul nodurilor

Se numește gradul nodului $x$ numărul de noduri adiacente cu $x$ (numărul de muchii incidente cu $x$).

Notăm gradul nodului într-un graf neorientat cu $d(x)$ și ia valori în intervalul întreg $[0,n)$.

Exemple:

• în graful $1$, gradele nodurilor 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ă” 2 muchii din fiecare).

Nod izolat

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

Exemple:

• toate nodurile grafului $1$ sunt noduri izolate;
• în graful $2$, nodul $e$ este singurul nod izolat (are gradul $0$).

Câteva formule comune pentru grafurile neorientate. Majoritatea formulează proprietăți pentru grafuri neorientate.

• numărul maxim de muchii dintr-un graf neorientat cu $n$ noduri este $C_{n}^{2} = \frac{n*(n-1)}{2}$;
• suma gradelor într-un graf neorientat este egală cu dublul numărului de muchii, adică $2*m$;
• numărul de grafuri neorientate care se pot forma cu $n$ noduri este egal cu $2^{C_{n}^{2}} = 2^{n*(n-1)/2}$. Formula calculează practic toate combinațiile posibile între muchii;
• numărul minim de muchii necesar astfel încât un graf neorientat să nu conțină noduri izolate este $[\frac{n+1}{2}]$ (parte întreagă);
• numărul de muchii necesar pentru ca un graf neorientat să nu poată conține noduri izolate este $C_{n+1}^{2}+1$. Se înțelege un subgraf complet cu $n-1$ noduri, la care se adaugă o muchie ce va uni nodul izolat de „restul nodurilor”.