vineri, 28 martie 2014

Grafuri neorientate : Tipuri de graf

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

Exemple graful din fig 5 este graf regulat 
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.



Niciun comentariu:

Trimiteți un comentariu