Grafuri

GRAFURI NEORIENTATE

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

GRAFURI ORIENTATE

Definitie Se numește graf orientat notat cu G o pereche ordonată de mulțimi {X,U} G= {X,U} unde X este mulțimea vârfurilor si U este multimea arcelor.

X={1,2,3,4,5}

U={(1,2);(1,3);(2,5);(4,2);(4,5)}

MATRICEA DE ADIACENTA.

Matricea de adiacenta asociata unui graf orientat este patratica si nesimetrica:

a[i][j]= 1 daca nodul i este adiacent cu nodul j;

0 daca nodul i nu este adiacent cu nodul j.

pentru graful orientat de mai sus avem urmatoarea matrice de adiacenta:

A= 0 1 1 0 0

0 0 0 0 1

0 0 0 0 0

0 1 0 0 1

0 0 0 0 0

GRAFUL UNUI NOD.

-grad extern este egal cu numarul arcelor care au extremitate initiala( numarul arcelor care ies din X)

-grad intern este egal cu numarul arcelor care au extremitate finala( numarul arcelor care intra in X).

TERMINOLOGIE.

Elementele mutimii U se numesc arce,iar multimea U se mai numeste si multimea arcelor.

Varfurile adiacente sunt orice pereche de varfuri care formeaza un arc.

Pentru arcul (x,y) spunem ca x este extremitate initiala iar y este extremitate finala.

Se numesc arce incidente doua arce care au o extremitate comuna.

Se numeste succesor al varfului X orice varf in care ajunge un arc care pleaca din varful X.

Se numeste predecesor al varfului X orice varf in care intra un arc care pleaca din varful X.

Nod sursa al grafului este nodul care are multimea succesorilor formata din toate celelalte noduri mai putin el iar multimea predecesorilo sai este vida. Nod destinatie al grafului este nodul care are multimea predecesorilor formata din toate celelalte noduri mai putin el iar multimea succesorilor sai este vida.

Se numeste nod terminal un nod care are suma gradelor egala cu 1.

Se numeste nod izolat un nod care are suma gradelor egala cu 0.

TEOREME.

1.Numarul total de grafuri orientate care se pot forma cu n noduri este

2.Intr-un graf orientat cu n varfuri suma gradelor interne ale tuturor nodurilor este egala cu suma gradelor exterioare ale tuturor nodurilor si cu numarul de arce.

3.Numarul de grafuri orientate complete care se pot construi cu n noduri este egal cu

4.Un graf cu mai mult de 2 noduri este hamiltonian daca gradul fiecarui nod este >=n/2.

5. Un graf ce nu contine grafuri izolate este eulerian daca si numai daca este conex si gradele tuturor nodurilor sunt pare.

6. Numarul de cicluri hamiltoniene dintr-un graf complet cu n noduri este

7. Orice graf turneu contine un drum elementar care trece prin toate nodurile grafului.

8. Pentru orice graf turneu, exista un nod x, astfel incat toate nodurile y!=x sunt accesibile din x pe un drum care contine un arc sau doua arce.

GRAFURI SPECIALE.

Graful G se numeste graf bipartit daca exista 2 multimi nevide de noduri A si B care au urmatoarele proprietati: AuB=X si AnB= multimea vida si orice muchie(arc) din multimea U are o extremitate in multimea de noduri A si o alta extremitate in multimea de noduri B.

Graful bipartit se numeste graf bipartit complet daca pentru orice nod xi care apartine lui A si orice nod xj care apartine lui B exista o muchie ( un arc ) formata din cele 2 noduri care apatin multumii U( [ xi, xj ]e U).

Graful GT1 este graf bipartit.

A={1,3,5}

B={2,4,6,7}

GT1

Graful GT2 este bipartit complet.

A={ 1,2}

B={3,6,7}

GT2

Numim lant hamiltonian un lant elementar ce contine toate nodurile grafului.

Lantul elementar este lantul care contine numai noduri distincte.

Numim ciclu hamiltonian un ciclu elementar ce contine toate nodurile grafului.

Un graf ce contine un ciclu hamiltonian se numeste graf hamiltonian.

Numim ciclu eulerian un ciclu ce contine toate muchiile grafului.

Un graf ce contine un ciclu eulerian se numeste graf eulerian.

Un garf orientat in care , intre oricare 2 noduri exista un singur arc si numai unul se numeste graf turneu.

Parcurgerea in latime

// inițializări
pentru fiecare nod u din V
{
    culoare[u] = alb
    d[u] = infinit
    p[u] = null
}
culoare[sursa] = gri
d[sursa] = 0
enqueue(Q,sursa) // punem nodul sursă în coada Q
 
// algoritmul propriu-zis
cât timp coada Q nu este vidă
{
    v = dequeue(Q) // extragem nodul v din coadă
    pentru fiecare u dintre vecinii lui v
        dacă culoare[u] == alb
        {
            culoare[u] = gri
            p[u] = v
            d[u] = d[v] +1
            enqueue(Q,u) // adăugăm nodul u în coadă
        }
    culoare[v] = negru // am terminat de explorat toți vecinii lui v
}

Parcurgerea in adancime 

//inițializări
pentru fiecare nod u din V
{
    culoare[u] = alb
    p[u] = NULL
    tDesc[u] = 0
    tFin[u] = 0
}
contor_timp = 0
 
//aplicarea algoritmului pentru toate componentele conexe 
pentru fiecare nod u din V
{
    daca culoare[u] == alb
        DFS(u)
}
 
//algoritmul propriu-zis
DFS(u)
{
    vizitare(u) // efectuarea de operațiuni asupra nodului curent
    contor_timp = contor_timp + 1
    tDesc[u] = contor_timp
    culoare[u] = gri
 
    pentru toate nodurile v adiacente lui u
        daca culoare[v] == alb
        {
            p[v] = u
            DFS(v)
        }
 
    contor_timp = contor_timp + 1
    tFin[u] = contor_timp
    culoare[u] = negru
}