|
|
Bulove matrice-matrica grafa
Definicija 1 : Matricu A=[aij], i=1,...,m ; j=1,...,n ,gde su aij Bulovi izrazi, je Bulova matrica formata mxn.Ako su aij E(pripada) {0,1}, matrica A je konstantna Bulova matrica.
Definicija 2 : Dve Bulove matrice istog formata mxn su jednake, u oznaci A=B, ako i samo ako su aij=bij, i=1,...,m;j=1,...,n Bulovi identiteti za svaki i,j.
Definicija 3 : neka su Bulove matrice A iB istog formata mxn. Zbir A+B=[aijVbij] Proizvod A • B=[aij • bij] Negacija A =[ a ij], i=1,...,m;j=1,...,n gde su V, • ,_ operacije Bulove algebre(L2,V, • ,_) Definija 4 : Matrični proizvod Bulove matrice A formata mxp i Bulove matrice formata pxn, je Bulova matrica A ๏ B=[k=1 V p (aik bkj)]
Definicija 5: Neka je ⊕ O(sa krstom u sebi) operacija sabiranja po mod2 na L2 i A,B Bulove matrice istog formata mxn, tada je alternativni ybir matrica A ⊕ O(sa krstom u sebi) B=[aik ⊕ O(sa krstom u sebi) bkj], i)1,...,m;j=1,...,n. Ako je A formata mxp, a B formata pxn, onda je alternativni proizvod bulove matrice A i Bulove matrice B Bulova matrica AoB=[k=1 ∑ ⊕ O(sa krstom u sebi) p (aik • bkj)] Neka je E=[eij] kvadratn matrica , gde je eij={1 za i=j ; 0 za i =/(nejednako) j tada važi AoE=EoA=A
Definicija 6 : Neka su A i B Bulove matrice istog formata mxn. A <_ (manje i jednako) B< =/(nejednako) >aij <_ (manje i jednako) bij, za svako i,j
Definicija 7 : Inverzna matrica kvadratne matrice A je matrica A^(-1), takva da važi AoA^(-1)=A^(-1)oA=E
Poseban značaj Bulove matrice imaju u teoriji grafova . Neka je skup S={x1,x2,...,xn} i ρ C(podskup) S^2 relacija tog skupa. Uredjen par(S,ρ) zovemo graf reda n. Geometrijska predstava grafa (S,ρ) odredjuje se na sledeći način. Svakom elementu xi skupa S pridružujemo jednu tačku - čvor grafa. Ako je (xi,xj) E(pripada) ρ, i =/(nejednako) j tada čvorove xi i xj vezujemo strelicom. Ako je (xi,xi) E(pripada) ρ tada u čvoru xi imamo petlju. Svakom grafu reda n pridružujemo kvadratnu Bulovu matricu Mρ=[mij], i,j=1,...,n , gde je mij={1,ako (xi,xj) E(pripada) ρ ; 0,ako (xi,xj) E/(ne pripada) ρ Mρ zovemo matricom grafa (S,ρ).