stresz142

V.N.Sachkov i V.E. Tarakanov w monografii "Combinatorics of Nonnegative Matrices" wydanej w 2002 roku przez American Mathematical Society w serii Mathematical Monographs Volume 213 jeden z rozdzia $\l$ ów poswiecili zwiazkom nieujemnych macierzy z digrafami.

Niech $A=(a_{ij})$ , $i,j=1,...,n\$ bedzie macierza o nieujemnych elementach. Na zbiorze $N_n=\{1,...,n\}$ definiujemy wielowartosciowe przekszta $\l$ cenie $\Gamma \colon N_n\rightarrow N_n$ w nastepujacy sposób:

$\begin{displaymath}\Gamma(i)=\{j\colon a_{ij}>0\},\ \ i\in N_n.\end{displaymath}$

To przekszta $\l$ cenie definiuje digraf, którego wierzcho $\l$ ki sa indeksowane elementami zbioru

Wierzcho $\l$ ki oraz sa po $\l$ aczone $\l$ ukiem , jesli $\Gamma(i)=j$ , czyli jesli $a_{ij}>0$ . Tak zdefiniowany digraf oznaczamy symbolem $\Gamma (A)$ .

Jesli wierzcho $\l$ ki oraz sa po $\l$ aczone w $\l$ ancuchem $i,i_1,...,i_{l-1},j$ d $\l$ ugosci , to mówimy, ze jest osiagalne z w krokach, co zapisujemy: $i\rightarrow j$ .

Wierzcho $\l$ ek digrafu $\Gamma (A)$ nazywamy istotnym, jesli istnieje co najmniej jeden wierzcho $\l$ ek taki, ze $i\rightarrow j$ oraz dla dowolnego takiego, ze $i\rightarrow j$ zachodzi $j\rightarrow i$ .

Jedna z prostych w $\l$ asnosci wiazacych macierze z digrafami jest nastepujacy wynik:

Jesli nieujemna macierz A stopnia n nie ma wierszy zerowych, to digraf $\Gamma (A)$ zawiera co najmniej jedna klase wierzcho $\l$ ków istotnych.

W referacie przedstawione zostana inne ciekawe w $\l$ asnosci digrafów $\Gamma (A)$ , równiez te, które scisle zwiazane sa z wnioskami z twierdzenia Frobeniusa dla równan diofantycznych w Z.