Reprezentarea grafurilor neorientate

1.Cu ajutorul matricei de adiacenta(matricei adiacente).

 A є M(m,n),n-nr de varfuri,m-nr de muchii.,unde A(i,j)=1,daca exista muchia (i,j)

                                                                                      0,daca nu exista

OBS! Matricea de adiacenta este simetrica fata de diagonala principala: A(i,j)=A(j,i).

OBS! Gradul unui varf x se poate determina calculand suma pe linia x.

·  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.

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).