Definiie Se numete graf neorientat o pereche ordonat de mulimi (V,U), V fiind o mulime finit i nevid de elemente numite noduri sau vfuri, iar U o mulime de perechi neordonate (submulimi de dou elemente) din V numite muchii.

Definiie Numim muchii adiacente dou muchii cu o extremitate comun. Pentru exemplul de mai sus, muchiile [1,5] i [5,4] sunt muchii adiacente pentru c au ca extremitate comun nodul 5.

Definiie Un graf parial al grafului G=(V,U) este un graf G1=(V,U1) astfel nct U1este inclus in U, adic G1 are aceeai mulime de vrfuri ca G, iar muimea de muchii U1 este chiar U sau o submulime a acesteia (un graf parial al unui graf se obine pstrnd aceeai mulime de noduri i eliminnd o parte din muchii).

Definiie Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel nct V1 este inclus in V iar U1 conine toate muchiile din U care au ambele extremiti n V1 (un subgraf se obine eliminnd vrfuri din V i muchiile incidente acestor vrfuri). Vom spune c subgraful H este indus sau generat de mulimea de vrfuri V1.

Definiie Gradul unui vrf x este numrul muchiile incidente cu x. Gradul vrfului x se noteaz d(x).

Definiie Un vrf care are gradul 0 se numete vrf izolat.

Definiie Un vrf care are gradul 1 se numete vrf terminal.

Propoziie Dac un graf G(V,U) are m muchii i n vrfuri, iar V={x1,x2,...,xn} atunci d(x1)+d(x2)+...+d(xn)=2*m.

Corolar n orice graf G exist un numr par de vrfuri cu grad impar.

Definiie Se numete graf complet cu n vrfuri un graf care are proprietatea c orice dou noduri diferite sunt adiacente.

Propoziie Un graf complet Kn are n(n-1)/2 muchii.

Definiie Un graf G=(V,U) se numete bipartit dac exist dou mulimi nevide A, B astfel nct V=A U B, AB = i orice muchie a lui G are o extremitate n A iar cealalt n B.

Definiie Un graf bipartit se numete complet dac pentru orice x din A i y din B, exist muchia (x,y).

Fie G=(V,U) un graf neorientat, V={x1,x2,..,xn}.

Definiie Se numete lan n G succesiunea de vrfuri L=[xi1,xi2,...,xik] cu proprietate c orice dou noduri consecutive din lant sunt adiacente, adic [xi1,xi2], [xi2,xi3], ..., [xik-1,xik]

Definiie Dac vrfurile xi1, xi2, ..., xik sunt diferite dou cte dou atunci lanul se numete lan elementar. n caz contrar, lanul este lan neelemntar. Cu alte cuvinte, un lan elementar este un lan care nu trece de dou ori prin acelai vrf.

Definiie Se numete ciclu n G un lan L pentru care xi1=xik i toate muchiile adiacente [xi1, xi2], [xi2, xi3], ..., [xik-1, xik] sunt diferite.

Definiie Se numete ciclu elementar un ciclu care are proprietate c oricare dou vrfuri ale sale, cu excepia primului i ultimului, sunt diferite dou cte dou. n caz contrar, ciclul este un ciclu neelementar.

Pentru exemplul anterior un ciclu elementar este [3,5,6,3].

Definiie Un graf G se numete conex dac pentru orice dou vrfuri x i y diferite ale sale exist un lan ce le leag.

Definiie Se numete component conex a grafului G=(V,U) un subgraf G1=(V1,U1), conex, al lui G care are proprietatea c nu exist nici un lan care s lege un vrf din V1 cu un vrf din V-V1. Cu alte cuvinte, se numeste componenta conexa a unui graf neorientat, G = (V,U), un subgraf al lui G, G1=(V1,U1), conex si maximal.

n exemplul din anterioara avem dou componente conexe : 1 : [2] 2 : [1,3,4,5,6]

Definiie Numarul Mu(G) = m-n+p se numeste numar ciclomatic al grafului G=(V,U); am notat cu m=numarul de elemente din U, n=numarul de elemente din V , p - numarul componentelor conexe ale grafului.

Definiie Numarul Lm(G) = n-p se numeste numar cociclomaticPunerea n eviden a vectorului de muchii. De exemplu pentru figura de mai jos. V={1,2,3,4,5,6} U={[1,5],[1,6],[3,6],[3,5],[3,4],[6,5]}

2. Lista de adiacen: pentru fiecare nod punem n eviden mulimea nodurilor cu are formeaz muchii. Pentru exemplul din figura de mai sus, lista de adiacen corespunztoare grafului este:

3. Matricea de adiacen: un graf poate fi memorat printr-o matrice ptratic boolean, de dimensiune egal cu numrul de noduri, n care o poziie a[i,j] va fi 1 dac exist arcul (xi,xj) i 0 n caz contrar, numit matricea adiacenelor directe.

Observaii: 1.Numrul de elemente din lista de adiacen corespunztoare unui nod i este aceli cu gradul vrfului 2.Matricea de adiacen este o matrice simetric fa de diagonala principal 3.Suma elementelor dintr-o matrice de adiacen este 2m. 4.Pe linia i i pe coloana i avem un numr de elemente 1 egal cu d(i). 5.Pe diagonala principal a unei matrice de adiacen corespunztoare unui graf neorientat sunt numai elemente 0