Grafuri
Notiuni teoretice introductive
Definiţie Se numeşte graf neorientat o pereche ordonată de mulţimi (V,U), V fiind o mulţime finită şi nevidă de elemente numite noduri sau vâfuri, iar U o mulţime de perechi neordonate (submulţimi de două elemente) din V numite muchii.
Definiţie 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.
Definiţie Un graf parţial al grafului G=(V,U) este un graf G1=(V,U1) astfel încât U1este inclus in U, adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii U1 este chiar U sau o submulţime a acesteia (un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de noduri şi eliminând o parte din muchii).
Definiţie Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel încât V1 este inclus in V iar U1 conţine toate muchiile din U care au ambele extremităţi în V1 (un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri). Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri V1.
Definiţie Gradul unui vârf x este numărul muchiile incidente cu x. Gradul vârfului x se notează d(x).
Definiţie Un vârf care are gradul 0 se numeşte vârf izolat.
Definiţie Un vârf care are gradul 1 se numeşte vârf terminal.
Propoziţie Dacă un graf G(V,U) are m muchii şi n vârfuri, iar V={x1,x2,...,xn} atunci d(x1)+d(x2)+...+d(xn)=2*m.
Corolar În orice graf G există un număr par de vârfuri cu grad impar.
Definiţie Se numeşte graf complet cu n vârfuri un graf care are proprietatea că orice două noduri diferite sunt adiacente.
Propoziţie Un graf complet Kn are n(n-1)/2 muchii.
Definiţie Un graf G=(V,U) se numeşte bipartit dacă există două mulţimi nevide A, B astfel încât V=A U B, A∩B = şi orice muchie a lui G are o extremitate în A iar cealaltă în B.
Definiţie Un graf bipartit se numeşte 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}.
Definiţie Se numeşte lanţ în G succesiunea de vârfuri L=[xi1,xi2,...,xik] cu proprietate că orice două noduri consecutive din lant sunt adiacente, adică [xi1,xi2], [xi2,xi3], ..., [xik-1,xik]
Definiţie Dacă vârfurile xi1, xi2, ..., xik sunt diferite două câte două atunci lanţul se numeşte lanţ elementar. În caz contrar, lanţul este lanţ neelemntar. Cu alte cuvinte, un lanţ elementar este un lanţ care nu trece de două ori prin acelaşi vârf.
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
