Page 38 - MATINF Nr. 3

38 I.A. Popescu

Definit , ia 2. Fie G = (X, U) un graf neorientat, X mult , imea nodurilor, iar U mult , imea
muchiilor. G se numes , te graf aproape 2-neconex echilibrat dac˘a exist˘a o mult , ime de muchii
(posibil vid˘a) ce pot fi ad˘augate ˆın G astfel ˆıncˆat noul graf notat cu G new s˘a fie 2-neconex
echilibrat.

Exemplul 2. Fie G = (X, U) cu X = {1, 2, 3, 4, 5, 6, 7, 8}, U = {[1, 3], [4, 6], [2, 6], [1, 5]}. G
nu este 2-neconex echilibrat, pentru c˘a are 4 componente conexe, iar dac˘a ad˘aug˘am muchiile
[5,8], [6,7] se obt , in pentru G new componentele conexe G 1 = (X 1 , U 1 ), X 1 = {1, 3, 5, 8}, U 1 =
{[1, 3], [1, 5], [5, 8]}. G 2 = (X 2 , U 2 ), X 2 = {2, 4, 6, 7}, U 2 = {[2, 6], [4, 6], [6, 7]}. G 1 s , i G 2 sunt
singurele componente conexe pentru G new s , i card(X 1 ) = card(X 2 ) = 4. Astfel G new este 2-
ˆ
neconex echilibrat. Rezult˘a G este aproape 2-neconex echilibrat. In Figura 2 este reprezentat
grafic graful G new .

1 3 2

5 4 4 6

8 7

Fig. 2: Exemplu de graf neorientat aproape 2-neconex echilibrat.

Observat ,ia 1. Din definit , ia grafului aproape 2-neconex echilibrat rezult˘a c˘a orice graf 2-neconex
echilibrat este s , i aproape 2-neconex echilibrat.

Algoritm pentru conditia de graf 2-neconex echilibrat
,

Vom considera un graf neorientat dat prin n - num˘arul de noduri, m - num˘arul de muchii s , i m
perechi de noduri ce reprezint˘a muchiile. Nodurile vor fi etichetate cu numerele 1, 2, . . . , n.

Algoritmul pe care ˆıl prezent˘am ˆın continuare foloses , te urm˘atoarele structuri de date:

1. Liste de adiacent , ˘a L = (L 1 , L 2 , . . . , L n ), L i este lista cu nodurile adiacente cu i, 1 ≤ i ≤ n.
2. Vector de vizitare a nodurilor v = (v 1 , v 2 , . . . , v n ), v i este 0, dac˘a nodul i nu a fost vizitat,
respectiv 1, ˆın caz contrar, 1 ≤ i ≤ n.

Etapele algoritmului sunt urm˘atoarele:

I Citim n, m.
II Dac˘a n este impar, graful nu este 2-neconex echilibrat s , i algoritmul se termin˘a.
III Citim cele m muchii ˆın variabilele i s , i j, dup˘a care introducem j ˆın lista L i , respectiv i ˆın
lista L j .
IV Init , ializ˘am componentele lui v cu 0.
V Parcurgem ˆın l˘at , ime sau adˆancime din nodul 1 graful dat folosind listele de adiacent , ˘a
(detalii ˆın [6] sau [7]).
VI Determin˘am ˆın n 1 num˘arul de noduri vizitate (egal cu suma elementelor lui v).
VII Dac˘a n 1 este diferit de n/2, graful nu este 2-neconex echilibrat s , i algoritmul se termin˘a.