Tipuri de graf.G.L

Definitie:Un graf  se zice regulat daca toate vf sale au acelasi grad.

Exemple graful din fig 5 este graf regulat 

 

     Proprietate Daca un graf G=(X,U) are n varfuri  si m muchii ,iar X={X1,X2,....,Xn} atunci   ∑ d(xi)=2m,1=m,...n.(suma gradelor varfurilor uni graf este 2*m).

     Corolar .in orice graf exista un nr par de varfuri cu grad impar.

Aplicatie :fiind dat un sir s:d1,d2,….,dn format din n numere intregi nenegative ,se pune prolema stabilirii unor conditii necesare  si suficiente astfel incat sa existe un graf ale carui varfuri sa ca gradele numerele date .Daca exista un astfel de graf ,sirul s se numeste sir grafic. Conditiile necesare sunt ;

(1)            di≤ n-1

(2)          d1+d2+....+dn sa fie nr par

Definitii

Ordinul unui graf este nr nodurilor sale.

Un graf se zice planar daca se poate reprezenta intr-un plan astfel incat oricare doua muchii distincte ale sale se intersecteaza numai in noduri .

Fiecarei muchii a unui graf neorientat i se poate asocia un o valoare pozitiva reala care reprezinta costul acelei muchii.

Un graf neorientat in care fiecarei muchii i s-a asociat o valoare se numeste graf valoric sau ponderat .

Exemplu: figura 9 graf ponderat(valoric)

          Un graf G=(X,U) si o functie L:U→R,care asociaza fiecarei muchii uєU costul sau L(u). Costul unui graf reprezinta suma costurilor muchiilor sale .

Un graf G=(X,U) se numeste nul  daca U=Ø(reprezentarea lui in plan consta doar in varfuri izolate )

Graf complementar

Fie graful G=(X,U) .se numeste graf complementar al garfului G grafuil G’=(U’,X’),cu proprietatea ca doua varfuri adiacente in G’ daca nu sunt adiacente in G

Exemplu: Graful    G’      complementar grafului     G .

 

         Graf conex

Un graf este conex daca pentru oricare 2 varfuri x si y exista un lant care le leaga .

                          Exp:fig 8

         Se numeste componenta conexa a grafului  G=(X,U) un subgraf G’=(U’,X’) conex cu proprietatea ca nu exista nici un lant in G care sa lege un  varf din X’ cu un varf din X.

Exemplu: graful alaturat are 2 componenete  conexe fig 12.

           

     Fie G=(V,E)  un graf neorientat conex.Un varf i se numeste punct de articulatie daca prin indepartarea sa si a muchiilor adiacente graful nu mai ramane conex.

Un graf  G=(V,E)  se numeste biconvex daca un are puncte de articulatie .Daca G nu este biconvex se pune problema determinarii componentelor sale biconvexe ,unde prin componenta biconvexa se intelege un subgraf biconvex maximal.

Graf hamiltonian

Se numeste graf hamiltonian un graf care contine un ciclu hamiltonian(care contine toate varfurile grafului).

Exp:fig 14 graf hamiltonian  

 Conditie suficienta ca un graf sa fie hamiltonian :Daca G=(X,U) este un graf cu n≥3 varfuri astfel incat gradul fiecarui varf satisface conditia d(x)≥n/2 atunci este hamiltonian.

Graf eulerian

Se numeste graf eulerian un graf care contine un ciclu eulerian (ciclu care contine toate muchiile grafului)

Exp:graful din  figura alaturata   este eulerian. 

        Un graf G=(X,U) fara varfuri izolate este eulerian  daca si numai daca este conex si gradele tuturor varfurilor sunt numere pare .

OBS: O metoda pentru a arata ca un graf este eulerian :se arata ca graful este conex ,si toate varfurile au grade pare.