Grafuri neorientate

           

Tipuri de grafuri

 

 

Grafuri Hamiltoniene

Def!Se numeste ciclu hamiltonian un ciclu elementar care contine toate varfurile grafului.

      Def!Un graf se numeste hamiltonian daca are cel putin un ciclu hamiltonian.

TEOREMA!Fie G=(X,U) un graf.Daca gradul fiecarui varf este >=n/2 atunci graful este hamiltonian.

OBS!Conditia din teorema este necesara,dar nu si suficienta.

Aplic!Ciclurile hamiltoniene sunt legate de problema comis-voiajorului care pleaca dintr-un oras si trebuie sa treaca o singura data prin celelalte orase si sa se intoarca de unde a plecat

Grafuri euleriene

Def!Un ciclu se numeste eulerian daca trece o singura data prin toate muchiile.

OBS!Un graf se numeste eulerian daca are un ciclu eulerian.

TEOREMA!Un graf fara varfuri izolate se numeste eulerian daca si numai daca este conex si gradul fiecarui varf este par.

OBS!Dintre grafurile complete sunt euleriene cele cu numar impar de varfururi.

Graf partial si subgraf

Def!Fie graful  G=(X,U).Un graf partial al lui G,este un graf G1=(X,V) ,cu V≤U(inclus).Altfel spus ,un graf partial se obtine pastrand toate varfurile si eliminand niste muchii.

      Def!Fie graful G=(X,U).Un subgraf al lui G,este un graf S=(Y,T),unde Y≤X si T≤V,iar T va contine numai acele muchii care au ambele extremitati in Y.Altfel spus,un subgraf S al lui G se obtine din G eliminand niste varfuri si odata cu acestea acele muchii care au cel putin o extremitate in submultimea eliminata.

 

     Graf complet si graf bipartit

   Se numeste graf complet cu n varfuri,notat K indice n (Kn),un graf G=(X,U) cu proprietatea ca oricare doua varfuri sunt adiacente,adica oricare cuplu x,y є X,esista muchia [x,y] є U.

Teorema!Un graf complet  cu n varfuri are n(n-1)/2 muchii.

Definitie!Se numeste graf bipartit ,un graf G=(X,U) cu proprietatea ca exista doua multimi distincte A si B incluse in X,astefel incat:

-A∩B=multime vida,A+B=X.(+ este reunit);

-toate muchiile grafului au o extremitate in A si cealalta in B.

Definitie!Se numeste graf bipartit complet ,un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B , exista muchia [x,y].(A+B=X).