Teoria grafurilor

TEORIA GRAFURILOR
Exist? dou? tipuri de grafuri:
Grafuri neorientate
Grafuri orientate

GRAFURI NEORIENTATE
Defini?ie. Se nume?te graf neorientat o pereche ordonat? de mul?imi (X, U), X fiind o mul?ime finit? ?i nevid? de elemente numite noduri sau v?rfuri, iar U o mul?ime de perechi neordonate ( submul?imi cu dou? elemente) din X, numite muchii.
Ex.




Pentru graful de mai sus avem:
X={1, 2, 3, 4, 5, 6, 7, 8}
U={[1,2], [1,4], [1,5], [2,3], [2,5], [3,4], [6,7]}
Dac? u1 ?i u2 sunt dou? muchii care au o extremitate comun? ele se vor numi adiacente.





Cu alte cuvinte, un graf par?ial al unui graf se ob?ine p?str?nd aceea?i mul?ime de v?rfuri ?i elimin?nd o parte din muchii.
Defini?ie. Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel ?nc?t Y( X iar V con?ine toate muchiile din U care au ambele extremit??i ?n Y. Vom spune c? subgraful H este indus sau generat de mul?imea de v?rfuri Y.
Ex. Mai jos avem un subgraf al grafului de mai sus ob?inu...