Grafuri neorientate - Algoritmul Malgrange

Fie M o matrice binara, finita, de dimensiune m- n, cu multimea de linii L={l1,l2, ,lm} si multimea de coloane C={c1,c2, ,cm}. Vom nota - =(A,B) matricea formata din elementele de la intersectia liniilor A- I si a coloanelor B- J.

Fie acum - 1 si - 2 doua submatrice ale matricei M, determinate de perechile de multimi de linii si coloane (Ai,Bi) i=1,2 (- 1=(A1,B1) si - 2=(A2,B2)).

Daca A1a2 , B1- B2 (- 1- - 2), matricea - 1 se numeste submatrice a matricei - 2

Daca toate elementele din - sunt egale cu 1, submatricea - a matricei M se numeste completa.

Daca submatricea - este completa si in M nu exista o alta submatrice completa - - - ' astfel incit - - - ', se numeste principala.

Daca orice element egal cu 1 din M apartine cel putin unei submatrici din familia C={- 1,- 2, ,- p}, aceasta familie C se numeste acoperire a matricei C.

Cardinalul multimii stabile interior maxime a grafului G se noteaza prin - 0(G) si se numeste numar de stabilitate interna.

II. Descrierea algoritmului

Fie A matricea de adiacenta a unui graf neorientat G=(X;U):

a b c d e f

a

b

c

d

e

f

iar A este matricea complementara a acesteia (elementele aij ale matricei A se calculeaza in baza elementelor aij ale matricei A dupa formula aij=1- aij):

a b c d e f

a

b

c

d

e

f

1

Scopul lucrarii: De a construi toate submatricile principale patratice ale lui A, in baza carora se pot determina toate multimile maximale stabile interior ale ale grafului G, prin utilizarea algoritmului Malgrange.

Pasul 1. Construim o acoperire arbitrara C0 a matricei A. In calitate de acoperirea C0 se ia familia tuturor submatricelor complete din A de forma - i=(Ai,Bi), unde a- =1, iar Bi este formata din coloanele matricei A, ce contin unitatea in linia Ai.

Acoperirea initiala C0 a matricei A este:

C0 = { (a,ac), (b,b), (c,acef), (d,d), (e,ce), (f,cf) }.

Pasul 2. Pentru p=0, construim familia Xp={- i- Cp, - j- - i astfel, incit - j- - - i } - familia tuturor submatricelor complete din Cp, care care se contin in alte submatrice ale lui Cp.

In acest caz X0= - -

Pasul 3. Construim familia de submatrice - (Cp- Xp), care se obtine prin aplicarea operatiilor

- si - asupra tuturor perechilor posibile de matrice - i, - j din Cp- Xp, cu conditia ca aceste elemente noi sa nu le contina pe submatricele din Cp- Xp.

C0- X0= C0- - - - (C0- X0) = - (C0):

(a, ac) - (c,acef) = (a - c, ac - acef) = (ac,ac)

(a, ac) - (e,ce) = (a - e, ac - ce) = (ae,c)

(a, ac) - (f,cf) = (a - f, ac - cf) = (af,c)

(c, acef) - (e,ce) = (c - e, acef - ce) = (ce,ce)

(c, acef) - (f,cf) = (c - f, acef - cf) = (cf,cf)

(e,ce) - (f,cf) = (e - f, ce - cf) = (ef,c)

- (C0- X0) ={ (ac,ac), (ae,c), (af,c), (ce,ce), (cf,cf), (ef,c) }.

Pasul 4. Formam acoperirea de matrice: Cp+1- - Cp- Xp) - (- (Cp- Xp))

C1- - C0- X0) - (- (C0- X0)) = { (a,ac), (b,b), (c,acef), (d,d), (e,ce), (f,cf), (ac,ac), (ae,c), (af,c), (ce,ce), (cf,cf), (ef,c) }.

Pasul 5. Daca Cp+1 - Cp, atunci consideram p=p+1 si ne reintoarcem la Pasul 2.

C1 - - - 0 - -

Pasul 2. Construim familia Xp+1=X1:

2

(a,ac)- - (ac,ac)

(e,ce)- - (ce,ce)

(f,cf)- - (cf,cf)

X1 ={ (a,ac), (e,ce), (f,cf) }.

Pasul 3. Construim familia - (Cp+1- Xp+1) = - (C1- X1):

C1- X1= { (b,b), (c,acef), (d,d), (f,cf), (ac,ac), (ae,c), (af,c), (ce,ce), (ef,c) }.

(c,acef) - (f,cf) = (c - f, acef - cf) = (cf,cf)

(c,acef) - (ac,ac) = (c - ac, acef - ac) = (ac,ac)