Grafuri neorientate

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.
Ex! X={1,2,3,4,5};
U={(1,3),(2,3),(2,5),(3,5)};

Def:Doua varfuri legate printr-o muchie se numesc adiacente.
Def:Muchia [x,y] este incidenta cu varful x si varful y.

Def:Se numeste gradul unui varf x si se noteaza d(x) numarul varfurilor adiacente cu varful x.

OBS!Varfurile cu grad zero se numesc izolate,iar varfurile cu grad 1 se numesc terminale.

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 ad