CONEXITATE

 

 

Def! Un graf se numeste conex daca intre oricare doua varfuri exista un lant.

      OBS! Pentru a verifica daca un graf este conex sau nu se realizeaza o parcurgere pornind din varful 1 si daca numarul de varfuri vizitate este n atunci graful este conex.

OBS! Daca graful nu este conex,atunci acesta este format din componente conexe.

Def!O componenta conexa este un subgraf conex maximal cu aceasta proprietate.

Def!  O componenta conexa a unui graf G=(X,U) este un subgraf S=(Y,Z) cu proprietatea ca nu exista un lant care sa uneasca un varf din Y cu un varf din X-Y.

OBS! Fiecare varf izolat constituie o componenta conexa.

ncc-numarul de componente conexe;

var a:array[1..20,1..20]of 0..1;

cc:array[1..20]of byte;

n,vi,ncc,i,j:byte;

 

procedure df(v:byte);

var i:byte;

begin

cc[v]:=ncc;

for i:=1 to n do

if (a[v,i]=1) and (cc[i]=0) then df(i);

end;

begin

{citire graf si vf initial}

ncc:=0;

for i:=1 to n do cc[i]:=0;

for i:=1 to n do

if (cc[i]=0) then begin

ncc:=ncc+1;

df(i);

end;

for i:=1 to ncc do  begin

write(‘componenta ‘,i);

for j:=1 to n do

if cc[j]=i then write(j,’ ‘);

writeln;

end;

readln;

end.