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