Podręcznik: Podstawowe pojęcia grafów Masona

2. Grafy przepływu sygnałów Masona i ich zastosowania w analizie obwodów

2.1. Podstawowe pojęcia grafów Masona

Graf Masona jest graficznym odzwierciedleniem układu równań liniowych i odpowiada przepływowi sygnałów w obwodzie elektrycznym. Wyróżnić w nim można węzły, odpowiadające zmiennym występującym w równaniu oraz gałęzie opisane wagami, odpowiadające współczynnikom równań. Przykładowo, jeśli dany jest układ równań liniowych

$a_{11}x_1+a_{12}x_2-F_1$

$a_{21}x_1+a_{22}x_2-F_2$

(2.1)

to w pierwszej kolejności należy go przekształcić do postaci

$x_1 = (a_{11}+1)x_1+a_{12}x_2-F_1$

$x_2 = a_{21}x_1+(a_{22}+1)x_2-F_2$

(2.2)

Graf Masona odpowiadający powyższemu układowi równań przedstawiony jest na rys. 2.15

Rys. 2.1. Graf Masona odpowiadający układowi równań liniowych (2.2)

Każdemu węzłowi grafu odpowiada zmienna $x_i$ ( $i = 1, 2$ w przykładzie) lub wymuszenie jednostkowe. Węzły połączone są łukami (gałęziami), którym przyporządkowane są współczynniki przy poszczególnych zmiennych układu równań (2.49). Współczynniki te, zwane wzmocnieniami (transmitancjami) gałęzi stanowią wagi, z jakimi sumowane są zmienne w poszczególnych węzłach. Sygnał węzła (zmienna $x_i$ ) jest równy sumie wagowej sygnałów dopływających do danego węzła. W grafie można wyróżnić pętle składające się z gałęzi jednakowo skierowanych tworzących zamknięty cykl (bez powtórzeń gałęzi i węzłów). W szczególności pętlę może tworzyć jedna gałąź wychodząca i wchodząca do tego samego węzła. Transmitancja pętli jest równa iloczynowi wzmocnień (transmitancji) gałęzi tworzących pętlę.
Jedną z najważniejszych zalet grafów Masona jest prosta reguła topologiczna określająca dowolny sygnał w grafie. Reguła ta dotyczy transmitancji definiowanej jako stosunek sygnału dowolnego węzła grafu uznanego za wyjściowy do sygnału węzła źródłowego, czyli węzła z którego sygnały jedynie odpływają (w przykładzie takim węzłem jest węzeł o sygnale równym jeden). Oznaczmy tę transmitancję przez $T=\frac{x_{wy}}{x_{we}}$ . Zgodnie z regułą Masona transmitancję tę określa wzór

$T=\frac{\sum\limits _{k} T_{k} \Delta _{k}}{\Delta }$

(2.3)

W powyższym wyrażeniu Δ oznacza wyznacznik główny grafu określany zgodnie ze wzorem

$\Delta =1-\sum _{i} G_{i} +\sum _{i,\ j} G_{i} G_{j} -\sum _{i,\ j,\ k} G_{i} G_{j} G_{k} +...$

(2.4)

We wzorze tym pierwsza suma oznacza sumowanie po wszystkich transmitancjach pętli $G_i$ istniejących w grafie. Suma druga dotyczy iloczynów transmitancji pętli rozłącznych branych po dwie naraz. Suma trzecia dotyczy iloczynów transmitancji pętli rozłącznych branych po trzy. Rozwinięcie wyznacznika prowadzi się aż do wyczerpania wszystkich możliwych kombinacji wielokrotnych pętli rozłącznych, biorąc sumy na przemian ze znakiem plus i minus, jak to pokazano we wzorze (2.51).
Wyrażenie $\sum\limits _{k} T_{k} \Delta _{k}$ w liczniku transmitancji dotyczy sumowania po wszystkich drogach prowadzących od węzła źródłowego (wejściowego) do węzła wyjściowego, przy czym $T_k$ oznacza iloczyn wzmocnień gałęzi prowadzących od źródła do węzła wyjściowego a $Δ_k$ jest wyznacznikiem $Δ$ określonym dla tej części grafu (podgrafu), która jest rozłączna z k-tą drogą $T_k$ (przy braku pętli w podgrafie wyznacznik Δ jest tożsamościowo równy 1).
Z rozwiązania grafu z rys. 2.15 przy pomocy reguły Masona otrzymuje się następujące transmitancje (węzeł źródłowy jest skojarzony z sygnałem jednostkowym):

$T_1=x_1=\frac{F_1a_{22}-F_2a_{12}}{1-\left[\left(a_{11}+1\right)+\left(a_{22}+1\right)+a_{12}a_{21}\right]+\left(a_{11}+1\right)\left(a_{22}+1\right)}$

$T_2=x_2=\frac{-F_1a_{21}+F_2a_{11}}{1-\left[\left(a_{11}+1\right)+\left(a_{22}+1\right)+a_{12}a_{21}\right]+\left(a_{11}+1\right)\left(a_{22}+1\right)}$

Rozwiązania na wartości zmiennych $x_1$ i $x_2$ układu równań (2.48) uzyskano bezpośrednio na podstawie reguły topologicznej Masona zastosowanej względem grafu z rys. 2.15. W identyczny sposób można wyznaczyć rozwiązanie dowolnie złożonego systemu opisanego poprzez graf Masona.

Jako następny przykład rozpatrzmy graf przepływu sygnałów przedstawiony na rys. 2.2, o wzmocnieniach gałęzi opisanych literami $a, b, c, … l$ .

Rys. 2.2. Graf przepływu sygnałów do przykładu

Stosując regułę Masona wyznaczymy transmitancję $T=\frac{x_{5}}{x_{we}}$ . Bezpośrednio na podstawie analizy struktury grafu otrzymuje się

$T=\frac{aej( 1-l) +bgk( 1-h) +adgk( 1-h) +adfj( 1-l) +bcej( 1-l) +bfj( 1-l)}{1-( cd+h+l) +( cdh+cdl+hl) -cdhl}$

W transmitancji tej wyrażenie mianownika (wyznacznik główny Δ) zawiera trzy składniki związane z pętlami (suma wzmocnień wszystkich pętli, iloczynów wzmocnień pętli rozłącznych branych po dwa i pętli rozłącznych branych po trzy).