Page 39 - MATINF Nr. 3

Grafuri neorientate 2-neconexe echilibrate 39

VIII Determin˘am un nod i cu v i = 0.
IX Parcurgem ˆın l˘at , ime sau adˆancime din nodul i graful dat folosind listele de adiacent , ˘a.
X Calcul˘am ˆın n 2 suma elementelor lui v (adic˘a num˘arul de noduri vizitate dup˘a cele dou˘a
parcurgeri).
XI Dac˘a n 2 = n atunci graful este 2-neconex echilibrat, altfel graful nu este 2-neconex
echilibrat.

Observat ,ia 2. Algoritmul are timpul de execut , ie de ordinul O(m + n).

Exemplu

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

I n = 6, m = 4.
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}.
IV v 1 = 0, v 2 = 0, v 3 = 0, v 4 = 0, v 5 = 0, v 6 = 0.
V v 1 = 1, v 2 = 0, v 3 = 1, v 4 = 0, v 5 = 1, v 6 = 0.
VI n 1 = 3.
VII n 1 este egal cu n/2 (n/2 = 6/2 = 3).
VIII i = 2 (4 sau 5).
IX v 1 = 1, v 2 = 1, v 3 = 1, v 4 = 1, v 5 = 1, v 6 = 1.
X n 2 = 6.
XI n 2 = n este echivalent˘a cu 6 = 6, adev˘arat, deci graful este 2-neconex echilibrat.

Algoritm pentru conditia de graf aproape 2-neconex echilibrat
,

Vom considera din nou un graf neorientat dat prin n - num˘arul 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:

I Liste de adiacent , ˘a L = (L 1 , L 2 , . . . , L n ), L i este lista cu nodurile adiacente cu i, 1 ≤ i ≤ n.
II 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.
III Vectorul x = (x 1 , x 2 , . . . , x k ), cu k = num˘arul de componente conexe s , i x i = num˘arul de
noduri a celei de-a i-a component˘a conex˘a, 1 ≤ i ≤ k.

Etapele algoritmului sunt urm˘atoarele:

I Citim n, m.
II Dac˘a n este impar, graful nu este aproape 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 s , i k cu 0.
V Pentru fiecare nod i din mult , imea {1, 2, . . . , n}, dac˘a v i = 0 atunci k = k + 1 s , i parcurgem
ˆın l˘at , ime sau adˆancime din nodul i graful dat folosind listele de adiacent , ˘a s , i determin˘am
ˆın x k num˘arul de noduri vizitate (num˘arul de noduri din componenta conex˘a ce cont , ine
nodul i).