R1 Nume:

Teza pe semestrul al II-lea la

Informatica

Subiectul I 6 0p

1. Se consideră graful neorientat definit prin mulțimea nodurilor {1,2,3,4,5,6} şi mulțimea muchiilor {[1,2],[2,3],[3,4],[3,5],[4,5],[1,3],[2,6],[2,4],[4,6]}.

a. Câte muchii trebuie adăugate ca graful G sa devină complet. Defineşte graful complet.b. Care este numărul minim de muchii ce trebuie eliminate astfel incat graful sa nu mai fie conex.

Defineşte noțiunea de conexitate.c. Parcurge graful in adâncime şi în lățime de la nodul 2,. Explică raționamentul parcurgerii cu BF.d. După eliminarea nodului 2, Scrie gradele nodurilor. Ce tip de graf se obține?e. Scrie un lanț elementar, un ciclu elementar.f. Scrie rândul al 5-lea din matricea de adiacență, elimina toate muchiile care au extremitati

numere pare. Cate componente conexe avem, si cate noduri terminale?

a. Reprezintă grafic. Si scrie gradele exterioare varfurilor pare si gradele interioare varfurilor impare.

b. Reprezintă graful prin vectori de arce. Scrie declarația in C++ a unui vector de arce,

c. Parcurge in adancime si in latime graful plecand de la vârful 5.Cate arce trebuie sa adăugăm ca graful sa devina conex.

d. Scrie un drum elementar de lungime maxima şi un circuit elementar de lungime maxima.e. Scrie al 2-lea, al 3-lea, al 5-lea rând din matricea vârfuri arce.f. Reprezintă graful prin matricea de costuri, adăugând costuri la alegere.

Subiectul II 30p

Scrie ultimele 5 soluții.

2. Fie G=(X, U) un graf orientat. Scrie un program care citeşte de la tastatură matricea de adiacență ataşată grafului, şi afişează numărul de arce, lista arcelor, şi gradul exterior al vârfurilor.Ex.

A=(0 1 01 0 10 0 0) se afisează numarul de arce=3 Arcele sunt (1,2); (2,1);(2,3) gradul exterior

varfurilor este 1,2,0.

R1 Nume: