Grafuri și Arbori

Grafuri neorientate

Un graf neorientat este o pereche ordonata

G = (X,U),

unde X este o multime finita si nevida de elemente numite noduri (vârfuri),

iar U este o multime de perechi (neordonate) de elemente distincte ale lui X, numite muchii.

O muchie având vârfurile i si j (numite extremitatile sale) este notata prin [i, j] sau [j, i].

nod/vârf = poate fi reprezentat în plan printr-un punct (cerc etc.), eventual numerotat

vom considera ca sunt n noduri intr-un graf

muchie = pereche neordonată de noduri; poate fi reprezentată în plan printr- un segment de dreaptă.

vom considera ca sunt m muchii intr-un graf

Exemplu 1. Graful neorientat

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

U = {[1,2], [1,5], [2,3], [2,4],[2,6], [3,6], [4,5], [7,8]}) poate fi reprezentat grafic ca în figura 1.

Noduri

Un vârf (nod) care este extremitatea unei singure muchii se numeste vârf (nod) terminal. (7 sau 8)

Doua vârfuri unite printr-o muchie se numesc vârfuri adiacente. (7 si 8, 1 si 2, 4 si 5)

dacă [x,y]- U, spunem că muchia este incidentă cu nodurile x și y

gradul nodului x = numărul de muchii incidente cu nodul x, notat d(x)

nod izolat = nod cu gradul 0; d(x) = 0

nod terminal = nod cu gradul 1; d(x) = 1

Propoziție

În orice graf neorientat cu n noduri și m muchii, are loc egalitatea

2*m = d(x1) + d(x2) + ... + d(xn)

Suma gradelor varfurilor este dublul numarului de muchii.

Consecinta: In orice graf G exista un numar par de varfuri de grad impar.

Subgraf

Un subgraf al unui graf G = (X,U) este un graf

H = (Y, V),

unde Y  X, iar V este formata din toate muchiile lui U care unesc vârfuri din Y.

Astfel H = ({1,2,3,4}, {[1,2], [2,3], [2,4]}) este un subgraf al grafului din figura 1.

Graf partial

Un graf partial al unui graf G = (X,U) este un graf

H = (X, V) cu V  U.

Astfel

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

{[1,2], [2,3], [2,6] [3,6], [4,5], [7,8]})

este un subgraf al grafului din figura 1.

graf parțial = graf care se obține din graful inițial prin eliminarea unor muchii, nu și a nodurilor