Page 40 - MATINF Nr. 3

40 I.A. Popescu

VI Folosind metoda program˘arii dinamice se determin˘a dac˘a exist˘a componente ˆın vectorul
x care au suma n/2 (ca la problema rucsacului - poate fi consultat˘a ˆın [1], [2], [3], [4]).
Fie M[i, g] = valoarea maxim˘a a unei sume cel mult egal˘a cu g format˘a cu elemente din
x 1 , . . . , x i , 0 ≤ i < n, 0 ≤ g ≤ n/2. Avem M[i, g] = 0 pentru i = 0 sau g = 0 s , i

M[i, g] = max {M[i − 1, g], x i + M[i − 1, g − x i ]} , dac˘a x i ≤ g,

M[i, g] = M[i − 1, g], dac˘a x i > g,

pentru 1 ≤ i < n, 1 ≤ g ≤ n/2 (pentru implementare se poate utiliza un vector).
VII Dac˘a r˘aspunsul la pasul VI este afirmativ, adic˘a dac˘a exist˘a i ∈ {1, 2, . . . , n − 1} astfel
ˆıncˆat M[i, n/2] = n/2, atunci graful este aproape 2-neconex echilibrat. Altfel graful nu
este aproape 2-neconex echilibrat.
2
Observat ,ia 3. Algoritmul are timpul de execut , ie de ordinul O(n ).

Exemplu
Pentru graful neorientat din Exemplul 2 (Figura 2) variabilele din algoritm, dup˘a fiecare
etap˘a, au urm˘atoarele valori:

I n = 8, m = 3.
II n este par.
III L 1 = {3, 5}, L 2 = {6}, L 3 = {1}, L 4 = {6}, L 5 = {1}, L 6 = {2, 4}, L 7 = {O}, L 8 = {O}.
IV v 1 = 0, v 2 = 0, v 3 = 0, v 4 = 0, v 5 = 0, v 6 = 0, v 7 = 0, v 8 = 0, k = 0.
V k = 4, x 1 = 3, x 2 = 3, x 3 = 1, x 4 = 1.
VI n/2 = 4, 4 = x 1 + x 4 .
VII Graful este aproape 2-neconex echilibrat.

Observat ,ia 4. Algoritmul anterior poate fi completat astfel ˆıncˆat s˘a determine s , i un s , ir de noi
muchii ce trebuie ad˘augate pentru a obt , ine G new din definit , ia grafului aproape 2-neconex echilibrat.
Mai precis, trebuie memorat pentru fiecare component˘a conex˘a s , i cˆate un nod y 1 , y 2 , . . . , y k .

Dac˘a n/2 = x w[1] + x w[2] + . . . + x w[p] , atunci muchiile necesare pentru a obt , ine graful G new
] - pentru o component˘a conex˘a, respectiv, dac˘a
sunt [y w[1] , y w[2] ], [y w[2] , y [w[3 ]], . . . , [y [w p−1 ] , y w [p]
au r˘amas componentele conexe cu numerele de noduri x [w p+1 ] , x [w p+2 ] , . . . , x [w k ] , se adaug˘a s , i
muchiile [y [w p+1 ] , y [w p+2 ] ], . . . , [y [w k−1 ] , y [w k ] ] - pentru cealalt˘a component˘a conex˘a.

Bibliografie

[1] Arhiva educat , ional˘a .campion, http://campion.edu.ro/arhiva/

[2] Arhiva educat , ional˘a infoarena, https://www.infoarena.ro/

[3] Site de preg˘atire pentru programare varena, http://varena.ro/

[4] D. Lica, M. Pas , oi, Fundamentele program˘arii, Ed. L&S InfoMat, clasa a XI-a, 2018.

[5] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, MIT Press, 2001.

[6] C. B˘alc˘au, Combinatoric˘a s , i teoria grafurilor, Ed. Universit˘at , ii din Pites , ti, 2007.

[7] C. B˘alc˘au, Algoritmica grafurilor - Note de curs, 2019.