Matrici inversabile, Grafuri orientate si matrici

Matrici inversabile

Def. Fie A o matrice de tipul m x n. Inversa la stanga a lui A este o matrice B de tipul n x m, astfel incat BA=I_n, (I_n este matricea unitate de ordin n). Inversa la dreapta a lui A este o matrice C de tipul n x m, astfel incat AC=I_m.

Observatie. Pot exista mai multe inverse la dreapta (nu la stanga). Pentru matricele patratice, inversa la dreapta coincide cu inversa la stanga, daca acestea exista. (Prop. 1.7).

Def. Daca o matrice patratica A este inversabila la dreapta si la stanga, atunci ea se numeste inversabila. O matrice inversabila se numeste nesingulara, in caz contrar, se numeste singulara.

Inversa lui A, daca exista se noteaza A^-1. Aceasta notiune o utilizam pentru rezolvarea ecuatiilor de tipul: AX=B sau XC=D.

Daca exista A^-1, respectiv C^-1, atunci ecuatia are solutie unica:X=A^-1B, (respectiv X=DC^-1).

Prop 1.8 Daca A este inversabila, atunci A^-1 este inversabila si

(A^-1)^-1=A.

Observatie Matricile nulpotente nu sunt inversabile.

Prop. 1.9 Daca A si B sunt doua matrici inversabile de acelasi ordin, atunci produsul AB este inversabil si (AB)^-1=B^-1A^-1.

Dem (B^-1A^-1)(AB)=B^-1A^-1AB=B^-1IB=I

Corolar Daca A₁, A₂.,A_n este inversabila si (A₁A₂.A_n)^-1=

Grafuri orientate si matrici

Def. Un graf orientat, G=(X, U), este format dintr-o multime finita nevida de varfuri, X, si o multuime de sageti (curbe orientate), U X x X. Ordinul grafic este prin definitie, numarul de elemente din X, notat cu x (coordonatul lui X). Daca u=(x,y)IU, spunem ca u=(x, x), spunem ca u este o bucla in x.

Un graf orientat este deci format dintr-o multime X si o relatie binara U pe X. Spunem ca G este un graf reflexiv (a) simetric (b) sau tranzitiv (c), daca verifica una din relatiile:

a)     x I X (x, x) I U;

b)     (x, y) I U (y, x) I U;

c)     (x, y) IU si (y,z) I U T (x, z) I U.

Def. Fie G=(X, U), un graf orientat. Un drum din G de lungime n (n o) este un sir finit, e=(x₀, x₁,.,x₁) de varfuri X astfel incat pentru orice i, 1 i n, sa avem (x_i-1, x_i) I U. Spunem ca este un drum de la x₀ la x_n. un drum este circuit daca x₀=x_n. In particular, pentru orice x I X, admitem ca drumul (x) este un circuit (lungimea lui este 0).

Def. Fie G=(X, U), un graf orientat. G este tare conex daca, daca pentru orice x, y I X, exista un drum de la x la y.

Def. Daca x I X este un varf al graficului orienat G=(X, U) putem defini:

d⁺(x)= = gradul de iesire a lui x (numarul sagetilor care pleaca din x)

si

d^- (x)= = gradul de intrare a lui x (numarul sagetilor ce vin la x).

Prop. 1.10 (Lema loviturilor de picior).

Pentru orice graf orientat G=(X, U) avem

.

Def. Un graf orientat G=(X, U) este un graf simplu daca este simetric si fara bucle. In acest caz, o pereche pentru care (x, y) I U si (y, x) I U se numeste muchie a grafului simplu.

Putem, in reprezentarea grafului simplu sa inlocuim sagetile cu segmente.

Intr-un graf simplu, pentru orice varf x, gradul de iesire este egal cu gradul de intrare si se numeste gradul lui x:

d(x)=d⁺(x)=d^-(x).

Prop. 1.11. (Lema strangerilor de mana)

Intr+un graf simplu G=(X, A), unde a reprezinta multimea muchiilor, avem:

Dem. Este suficient sa observam ca:

U =2 A

Def. Fie G=(X, U), un graf orientat cu X= . Matricea adiacenta lui G este matricea patratica de ordin n, M(G) definita prin:

Prop. 1.12. Fie G=(X, U), un graf orientat, M(G)= m_ij , matricea adiacenta. Atunci:

1.     Pentru orice i

d⁺(x_i)= suma elementelor de pe linia i;

d^-(x_i)=suma elementelor de pe coloana i.

2.    

3.     G este simetric daca si numai daca M(G) este o matrice simetrica.

4.     Numarul buclelor din G este egal M(G).

5.     M(G^-1)=M(G)^T unde G^-1=(X, U^-1)este graful opus sau dual lui G:

U^-1=

6.     M( )=E-M(G) unde E= e_ij cu e_e 1 pentru orice i si j, si =(X, 5) este graful complementar lui G:

5