Arbori

Notiunea de arbore:

Se numeste arbore un graf neorientat care este conex si nu contine cicluri.

Problema: Se citeste un graf. Sa se scrie un program care verifica daca este arbore.

1. Mai iintai, trebuie vazut daca graful este conex. in cazul grafurilor orientate aceasta problema se rezolva printr-o simpla parcurgere in adancime. Dar in cazul grafurilor neorientate apare o problema. De la nodul i la nodul j exista doua arce, de la i la j si de la j la i. Aceasta conduce la semnalarea unui ciclu fals. Pentru rezolvare, dupa alegerea unei muchii, de exemplu de la i la j se elimina muchia de la j la i. in final daca au fost atinse toate nodurile (adica daca orice componenta a vectorului S retine numai 1) inseamna ca graful este conex.

2. Trebuie analizat daca graful nu are cicluri. Aceasta problema se rezolva tot cu ajutorul parcurgerii in adancime. Parcurgerea asigura selectia unei muchii o singura data. Daca graful are cel putin un ciclu, atunci un nod este atins de doua ori. Cum ne putem da seama daca aceasta are loc? Simplu, daca a fost atins un nod i, pentru care s = 1.

in aceste conditii, nu se face decat o simpla parcurgere in adancime. Iata programul:

program arbore;

type mat_ad = array [1 10, 1 10] of integer;

vector = array [1 50] of byte;

var S: vector

A: mat_ad;

suma, n, i, k: integer;

gasit: boolean;

procedure citireN (nume- fis; string; var a: mat_ad; n: integer);

var i, j : byte;

begin

assign (f, nume-fis);

reset (f)

readln (f, n);

while (not eof (f)) do

begin

readln (f, i, j); A[i, j]:=1;

A[j, i]:=1;

end;

close (f);

end;

procedure parcurgere (nod: byte);

var k: byte;

begin

S[nod]:=1;

for k:=1 to n do

if (A[nod, k]=1)

then

begin

A[k, nod]:=0;

if S[k]=0 then parcurgere(k)

else gasit:=true;

end;

end;

begin

clrscr;

1. TUDOR SORIN - ,,INFORMATCA, VARIANTA PASCAL" -

MANUAL PENTRU CLASA A XI-A,

EDITURA L&S INFOMAT 2001,BUCURESTI

2. MATEESCU (CERCHEZ) E, MAXIM - ,,ARBORI", EDITURA

TARA FAGILOR, SUCEAVA, 1997 3. NICULESCU ST. CERCHEZ E.SERBAN M, LICA D.,ONEA E.MANZ.

D.POPESCU, D.VOICU A. ,,BACALAUREAT SI

ATESTAT" EDITURA L&S INFOMAT, 1999

4. PATRUT B, MILOSESCU M- ,,INFORMATICA" EDITURA

TEORA, 1999