Extras din laborator
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 AI şi a coloanelor BJ.
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ă A1A2 , B1B2 (ƒ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={ƒiCp, ƒ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.
Preview document
Conținut arhivă zip
- Grafuri - Algoritmul Malgrange.doc