Grafuri

Def: Se numeste graf neorientat o pereche ordonata g= (X, U) , unde X este o multime finita si nevida cu elemente numite noduri sau varfuri, iar U este o multime de perechi neordonate din X numite muchii.

Teorema: In orice graf (X, U) suma gradelor varfurilor este de doua ori numarul de muchii, adica ?d (x) =d (x1) +d (x2) + +d (xn) =2*m, x ? X, m-nr de muchii, n-nr de varfuri.

Dem: Fiecare muchie (x, y) contribuie cu o unitate la gradul lui x si cu o unitate la gradul lui y=>contribuie cu 2 unitati la suma gradelor, si atunci fiind m muchii inseamna ca suma gradelor este de 2 ori nr de muchii.

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.

Citirea unui graf memorat cu ajutorul matricei de adiacenta!

Varianta 1: Citirea numarului de varfuri, citirea regiunii de deasupra diagonalei principale urmata de simetrizare.

var a: array[1. 120, 1. 120] of 0. 1; x, d, i, j, n: byte; begin write (nr de varfuri: =); readln (n); for i: =1 to n-1 do for j: =i+1 to n do begin write (a[, i, , , j,]: =); readln (a[i, j]); a[j, i]: =a[i, j]; end; end.

Varianta 2: Se citesc n-nr de varfuri, m-nr de muchii; -initializarea matricei de adiacenta cu zero; -citirea extremitatii fiecarei muchii; -completarea matricei de adiacenta.

var a: array[1. 120, 1. 120] of 0. 1; x, d, i, j, n: byte; begin write (n: =); readln (n); write (m: =); readln (m); for i: =1 to n do for j: =1 to n do a[i, j]: =0; for i: =1 to m do begin writeln (Muchia, i, este: ); readln (x, y); a[x, y]: =1; a[y, x]: =1; end; end.

Cate grafuri neorientate cu n varfuri exista?

R: 2 la C din n luate cate 2. 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: -AnB=multime vida, A+B=X. (+ este reunit); -toate muchiile grafului au o extremitate in A si cealalta in B.

Definitie! Se ...