Grafuri - Algoritmul Malgrange

I. Noţiuni preliminare:

Fie M o matrice binară, finită, de dimensiune m×n, cu mulţimea de linii L={l1,l2,…,lm} şi mulţimea de coloane C={c1,c2,…,cm}. Vom nota ƒ=(A,B) matricea formată din elementele de la intersecţia liniilor AI şi a coloanelor BJ.

Fie acum ƒ1 şi ƒ2 două submatrice ale matricei M, determinate de perechile de mulţimi de linii şi coloane (Ai,Bi) i=1,2 (ƒ1=(A1,B1) şi ƒ2=(A2,B2)).

Dacă A1A2 , B1B2 (ƒ1ƒ2), matricea ƒ1 se numeşte submatrice a matricei ƒ2 .

Dacă toate elementele din ƒ sunt egale cu 1, submatricea ƒ a matricei M se numeşte completă.

Dacă submatricea ƒ este completă şi în M nu există o altă submatrice completă ƒ́́’ astfel încît ƒƒ’, se numeşte principală.

Dacă orice element egal cu 1 din M aparţine cel puţin unei submatrici din familia C={ƒ1,ƒ2,…,ƒp}, această familie C se numeşte acoperire a matricei C.

Cardinalul mulţimii stabile interior maxime a grafului G se notează prin α0(G) şi se numeşte număr de stabilitate internă.

II. Descrierea algoritmului

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

a b c d e f

a 0 1 0 1 1 1

b 1 0 1 1 1 1

c 0 1 0 1 0 0

d 1 1 1 0 1 1

e 1 1 0 1 0 1

f 1 1 0 1 1 0

iar Ā este matricea complementară a acesteia (elementele āij ale matricei Ā se calculează în baza elementelor aij ale matricei A dupa formula āij=1- aij):

a b c d e f

a 1 0 1 0 0 0

b 0 0 0 0 0 0

c 1 0 1 0 1 1

d 0 0 0 1 0 0

e 0 0 1 0 1 0

f 0 0 1 0 0 1

1

Scopul lucrării: De a construi toate submatricile principale pătratice ale lui Ā, în baza cărora se pot determina toate mulţimile maximale stabile interior ale ale grafului G, prin utilizarea algoritmului Malgrange.

Pasul 1. Construim o acoperire arbitrară C0 a matricei Ā. În calitate de acoperirea C0 se ia familia tuturor submatricelor complete din Ā de forma ƒi=(Ai,Bi), unde |A|=1, iar Bi este formată din coloanele matricei Ā, ce conţin unitatea în linia Ai.

Acoperirea iniţială C0 a matricei Ā 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, încît ƒj ƒi } – familia tuturor submatricelor complete din Cp, care care se conţin în alte submatrice ale lui Cp.

În acest caz X0= 

Pasul 3. Construim familia de submatrice Γ(CpXp), care se obţine prin aplicarea operaţiilor

⋂ şi ⋃ asupra tuturor perechilor posibile de matrice ƒi, ƒj din CpXp, cu condiţia ca aceste elemente noi să nu le conţină pe submatricele din CpXp.