Definitia grafurilor neorientate.

Definiţie Se numeşte ciclu în G un lanţ L pentru care xi1=xik şi toate muchiile adiacente [xi1, xi2], [xi2, xi3], ..., [xik-1, xik] sunt diferite.

Definiţie Se numeşte ciclu elementar un ciclu care are proprietate că oricare două vârfuri ale sale, cu excepţia primului şi ultimului, sunt diferite două câte două. În caz contrar, ciclul este un ciclu neelementar.

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

Definiţie Un graf G se numeşte conex dacă pentru orice două vârfuri x şi y diferite ale sale există un lanţ ce le leagă.

Definiţie Se numeşte 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 vârf din V1 cu un vârf 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]

Definiţie 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.

Definiţie Numarul Lm(G) = n-p se numeste numar cociclomatic