Wykres przepływu (matematyka)

Graf blokowy to forma digrafu powiązana z zestawem liniowych równań algebraicznych lub różniczkowych:

„Wykres przepływu sygnału to sieć węzłów (lub punktów) połączonych ze sobą skierowanymi gałęziami, reprezentującymi zestaw liniowych równań algebraicznych. Węzły na wykresie przepływu służą do reprezentowania zmiennych lub parametrów, a łączące gałęzie reprezentują współczynniki powiązanie tych zmiennych ze sobą. Graf blokowy jest powiązany z szeregiem prostych reguł, które umożliwiają uzyskanie każdego możliwego rozwiązania [związanego z równaniami].

Chociaż w tej definicji zamiennie używa się terminów „wykres przepływu sygnału” i „wykres przepływu”, termin „wykres przepływu sygnału” jest najczęściej używany do określenia wykresu przepływu sygnału Masona, przy czym Mason jest twórcą tej terminologii w swojej pracy w sieciach elektrycznych. Podobnie, niektórzy autorzy używają terminu „wykres przepływu”, aby odnieść się ściśle do wykresu przepływu Coatesa . Według Henleya i Williamsa:

„Nomenklatura jest daleka od standaryzacji i… nie można oczekiwać żadnej standaryzacji w dającej się przewidzieć przyszłości”.

Oznaczenie „wykres przepływu”, które obejmuje zarówno wykres Masona, jak i wykres Coatesa oraz różne inne formy takich wykresów, wydaje się przydatne i zgadza się z podejściem Abrahamsa i Coverleya oraz Henleya i Williamsa.

Sieć skierowana – znana również jako sieć przepływowa – jest szczególnym typem wykresu przepływu. Sieć z jego krawędzi, a jeśli graf jest dwuznakiem, wynikiem jest sieć skierowana . Graf przepływu jest bardziej ogólny niż sieć skierowana, ponieważ krawędzie mogą być powiązane ze wzmocnieniami, wzmocnieniami gałęzi lub transmitancjami , a nawet funkcjami operatorów Laplace'a , w którym to przypadku nazywane są funkcjami przenoszenia .

Istnieje ścisły związek między grafami a macierzami oraz między digrafami a macierzami. „Algebraiczną teorię macierzy można wykorzystać w teorii grafów, aby elegancko uzyskać wyniki” i odwrotnie, podejścia oparte na teorii grafów oparte na grafach przepływu są używane do rozwiązywania liniowych równań algebraicznych.

Wyprowadzanie wykresu przepływu z równań

Przykład wykresu przepływu sygnału

Wykres przepływu dla trzech równoczesnych równań. Krawędzie występujące w każdym węźle są pokolorowane inaczej, tylko dla podkreślenia.

Przedstawiono przykład wykresu przepływu połączonego z niektórymi równaniami wyjściowymi.

Układ równań powinien być spójny i liniowo niezależny. Przykładem takiego zestawu jest:

{\ Displaystyle {\ rozpocząć {bmatrix} 1 i 2 i 0 \\ 0 i 1 i 1 \\ 5 i -1 i -1 \ koniec {bmatrix}} {\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}5\\5\\0\end{bmatrix}}}

Spójność i niezależność równań w zbiorze jest ustalona, ponieważ wyznacznik współczynników jest niezerowy, więc rozwiązanie można znaleźć korzystając z reguły Cramera .

Wykorzystując przykłady z podrozdziału Elementy grafów przepływu sygnałów konstruujemy wykres Na rysunku, w tym przypadku wykres przepływu sygnałów. Aby sprawdzić, czy wykres przedstawia podane równania, przejdź do węzła x ₁ . Spójrz na strzałki przychodzące do tego węzła (kolor zielony dla podkreślenia) i dołączone do nich ciężarki. Równanie dla x ₁ jest spełnione przez przyrównanie go do sumy węzłów dołączonych do nadlatujących strzałek pomnożonej przez wagi dołączone do tych strzałek. Podobnie czerwone strzałki i ich wagi przedstawiają równanie dla x ₂ , a niebieskie strzałki dla x ₃ .

Innym przykładem jest ogólny przypadek trzech jednoczesnych równań o nieokreślonych współczynnikach:

{\ Displaystyle {\ rozpocząć {bmatrix} c_ {11} &c_{12}&c_{13}\\c_{21}&c_{22}&c_{23}\\c_{31}&c_{32}&c_{33}\end{bmatrix}}{\begin{bmatrix}x_{ 1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}}

Aby skonfigurować wykres przepływu, równania są przekształcane, aby każde z nich identyfikowało pojedynczą zmienną, dodając ją z każdej strony. Na przykład:

{\ Displaystyle \ lewo (c_ {11} + 1 \ prawo) x_ {1} + c_ {12} x_ {2} + c_ {13} x_ {3} -y_ {1} = x_ {1} \ .}

Korzystając z diagramu i sumując gałęzie incydentów do x ₁ , równanie to wydaje się być spełnione.

Ponieważ wszystkie trzy zmienne wchodzą do tych przekształconych równań w sposób symetryczny, symetria zostaje zachowana na wykresie poprzez umieszczenie każdej zmiennej w rogu trójkąta równobocznego. Obracanie figury o 120° po prostu zmienia indeksy. Tę konstrukcję można rozszerzyć na więcej zmiennych, umieszczając węzeł dla każdej zmiennej w wierzchołku wielokąta foremnego z tyloma wierzchołkami, ile jest zmiennych.

Oczywiście, aby mieć znaczenie, współczynniki są ograniczone do wartości takich, że równania są niezależne i spójne.

Zobacz też

Dalsza lektura

Richard A. Brualdi, Dragos Cvetkovic (2008). „Determinanty” . Kombinatoryczne podejście do teorii macierzy i jej zastosowań . Chapman & Hall/CRC. s. 63 i nast . ISBN 9781420082234 . Omówienie grafów przepływu Coatesa i Masona.