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.

Laborator in limbajul BorlandC la obiectul Grafuri

Algoritmul Malgrange