0000078

Siec Maeona reprezentuje ukłaa równań liniowych

A *X ■ B

w naetępujecy eposób:

Układ równań możemy przepiaec naetypujico

(A_u ♦ I) X'- X'    <⁹-⁵>

gdzie X" [^xj«^x2.....^xn* ^xn^l ]    ¹ xn*i * ^ł *

wtedy dla każdej zmiennej *_k otrzymujemy równanie

(*kk ^{4 ł}> ^xk ' ^bk ^xn»l ⁴ £ *kj ^XJ " ^Xk    ^(9>6)

jak

Sieć Maeona reprozentuj|C| ten układ równań tworzyay nnotępujoco

s.M_u) ■ s_c(A_u ♦ I) • <c_t.H. l*)>

C_B •< x" u. P>

«^dzi0    I,    ,    1

*    • l^xl.....V^Xn*l)

Oeżeli zalenne x_fc, reprezentowane przez wierzchołki grafu eiecl Maeono, zinterpretujemy jako eygnały, to z (9.6) wynika, że każ-Oy oygnał x_v jeet produktem wezyetklch eygnałów tranealtowanych przez łukl i pytle grafu C_ff oo wierzchołka x_k. Ty fizyczni Interpretację lluotruje rye.9.7.

Ryo.9.7

Olotego toż tioć Masona jost nazywano grafom sygnałowym (signal fIow graph).

TWIEROZENIE 9.3

Nloch G_m(A) bę ozls grafom oioci Masona, atowerzyozo-nej z eociorzę kwodrotowę A^ł,[^,ij]n*n*

Wtedy

d.t A.    - zz (-1)^V *(C_UV)1

^L u,v    ^J

v>0

gdzie C_yv Jest u-tya podgrafao częściowym grafu Gjh , tworzonym przez v różnych wierzchołków 1 gałęzi drogi prostej cyklicznej w grafie G^.

Oowód twierdzenia zamleezczony jest w [iO].

TWIERDZENIE 9.4

Niech G₀(A) będzie grafem elecl Masona, stowarzyszonej z (nadarzę kwadratów# A- [•jJ _nxn ¹ n * ²*

Wtady

\l ■ I-¹)"*¹ i¹    "^C'uv>]

v>0

(-1)

n-1

U

> U ♦

*.t

tX>

dla i / j, gdzie    jaat dopełnianiem algebraiczny#

elementu a^ macierzy A; c'_uv Jest u-tya podgrefem częściowym tworzonym przez v różnych wierzchołków i gałęzi drogi prootaj cyklicznej w 0_n(    P_tj

Jest k-t# dróg# prost# z wierzchołka 1 do wierzchołka j w GJA) i C)J_t jest s-tym podgrefem częścio-wyo tworzonym przez t wierzchołków cyklicznej drogi prostej rozł#cznej z drogę P^; netomloet A_ij jest podaacierz# macierzy A , powstał# przez wykreślenie i-tego wiersze i j-tej kolumny.

155