Потоковый график (математика)

Потоковый граф — это форма орграфа , связанная с набором линейных алгебраических или дифференциальных уравнений: [1] [2]

«Граф потока сигналов — это сеть узлов (или точек), соединенных между собой направленными ветвями, представляющими набор линейных алгебраических уравнений. Узлы в графе потока используются для представления переменных или параметров, а соединительные ветви представляют коэффициенты, связывающие эти переменные друг с другом. Граф потока связан с рядом простых правил, которые позволяют получить все возможные решения [относящиеся к уравнениям]». [1]

Хотя это определение использует термины «граф потока сигналов» и «граф потока» взаимозаменяемо, термин «граф потока сигналов» чаще всего используется для обозначения графа потока сигналов Мейсона , который был создателем этой терминологии в своей работе по электрическим сетям. [3] [4] Аналогично, некоторые авторы используют термин «граф потока» для обозначения строго графа потока Коутса . [5] [6] Согласно Хенли и Уильямсу: [2]

«Номенклатура далека от стандартизации, и... в обозримом будущем не следует ожидать никакой стандартизации».

Обозначение «граф потока», которое включает в себя как граф Мейсона, так и граф Коутса, а также множество других форм таких графов [7], представляется полезным и согласуется с подходом Абрахамса и Коверли, а также с подходом Хенли и Уильямса. [1] [2]

Направленная сеть – также известная как потоковая сеть – это особый тип потокового графа. Сеть – это граф с действительными числами, связанными с каждым из его ребер, и если граф является орграфом, результатом является направленная сеть . [8] Потоковая графа является более общим, чем направленная сеть, в том смысле, что ребра могут быть связаны с усилениями, усилениями ветвей или коэффициентами пропускания , или даже функциями оператора Лапласа s , в этом случае они называются передаточными функциями . [2]

Существует тесная связь между графами и матрицами, а также между орграфами и матрицами. [9] «Алгебраическая теория матриц может быть применена к теории графов для получения элегантных результатов», и наоборот, теоретико-графические подходы, основанные на потоковых графах, используются для решения линейных алгебраических уравнений. [10]

Вывод графа потока из уравнений

Пример графика потока сигналов
Граф потока для трех одновременных уравнений. Ребра, инцидентные каждому узлу, окрашены по-разному только для акцента.

Представлен пример потокового графа, связанного с некоторыми исходными уравнениями.

Набор уравнений должен быть согласованным и линейно независимым. Пример такого набора: [2]

[ 1 2 0 0 1 1 5 − 1 − 1 ] [ х 1 х 2 х 3 ] = [ 5 5 0 ] {\displaystyle {\begin{bmatrix}1&2&0\\0&1&1\\5&-1&-1\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\end{bmatrix}}={\begin{bmatrix}5\\5\\0\end{bmatrix}}}

Согласованность и независимость уравнений в системе устанавливается, поскольку определитель коэффициентов отличен от нуля, поэтому решение можно найти с помощью правила Крамера .

Используя примеры из подраздела Элементы графов потока сигналов , мы строим граф На рисунке, в данном случае граф потока сигналов. Чтобы проверить, что граф действительно представляет приведенные уравнения, перейдите к узлу x 1 . Посмотрите на стрелки, входящие в этот узел (окрашенные в зеленый цвет для акцента), и веса, прикрепленные к ним. Уравнение для x 1 удовлетворяется путем приравнивания его к сумме узлов, прикрепленных к входящим стрелкам, умноженной на веса, прикрепленные к этим стрелкам. Аналогично, красные стрелки и их веса дают уравнение для x 2 , а синие стрелки — для x 3 .

Другим примером является общий случай трех одновременных уравнений с неопределенными коэффициентами: [11]

[ с 11 с 12 с 13 с 21 с 22 с 23 с 31 с 32 с 33 ] [ х 1 х 2 х 3 ] = [ у 1 у 2 у 3 ] {\displaystyle {\begin{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}}}

Чтобы настроить потоковую диаграмму, уравнения переформулируются так, чтобы каждое определяло одну переменную, добавляя ее к каждой стороне. Например:

( с 11 + 1 ) х 1 + с 12 х 2 + с 13 х 3 − у 1 = х 1   . {\displaystyle \left(c_{11}+1\right)x_{1}+c_{12}x_{2}+c_{13}x_{3}-y_{1}=x_{1}\ .}

Используя диаграмму и суммируя падающие ветви в x 1, можно увидеть, что это уравнение удовлетворяется.

Поскольку все три переменные входят в эти переработанные уравнения симметричным образом, симметрия сохраняется в графике, поскольку каждая переменная располагается в углу равностороннего треугольника. Поворот фигуры на 120° просто переставляет индексы. Эту конструкцию можно распространить на большее количество переменных, поместив узел для каждой переменной в вершину правильного многоугольника с таким же количеством вершин, как и переменные.

Конечно, чтобы иметь смысл, коэффициенты ограничены такими значениями, чтобы уравнения были независимыми и непротиворечивыми.

Смотрите также

Дальнейшее чтение

  • Ричард А. Бруальди, Драгош Цветкович (2008). «Определители». Комбинаторный подход к теории матриц и ее приложениям . Chapman & Hall/CRC. стр. 63 и далее . ISBN 9781420082234.Обсуждение потоковых графиков Коутса и Мейсона.

Ссылки

  1. ^ abc JR Abrahams, GP Coverley (1965). "Глава 1: Элементы потокового графа". Анализ потока сигналов. Elsevier. стр. 1. ISBN 9781483180700.
  2. ^ abcde Эрнест Дж. Хенли, Р. А. Уильямс (1973). "Основные концепции". Теория графов в современной инженерии; автоматизированное проектирование, управление, оптимизация, анализ надежности . Academic Press. стр. 2. ISBN 9780080956077.
  3. ^ Мейсон, Сэмюэл Дж. (сентябрь 1953 г.). «Теория обратной связи — некоторые свойства графов потока сигналов» (PDF) . Труды IRE . 41 (9): 1144– 1156. doi :10.1109/jrproc.1953.274449. S2CID  17565263. Архивировано из оригинала (PDF) 2018-02-19 . Получено 2015-01-09 .
  4. ^ SJ Mason (июль 1956 г.). «Теория обратной связи — дополнительные свойства графов потока сигналов» (PDF) . Труды IRE . 44 (7): 920–926 . doi :10.1109/JRPROC.1956.275147. hdl : 1721.1/4778 . S2CID  18184015.Электронная версия доступна в Исследовательской лаборатории электроники Массачусетского технологического института.
  5. ^ Вай-Кай Чен (май 1964). "Некоторые приложения линейных графов" (PDF) . Лаборатория координированной науки, Иллинойсский университет, Урбана.
  6. ^ RF Hoskins (2014). "Анализ потоковых графов и сигнальных потоковых графов линейных систем". В SR Dears (ред.). Последние разработки в теории сетей: Труды симпозиума, состоявшегося в Колледже аэронавтики, Крэнфилд, сентябрь 1961 г. Elsevier. ISBN 9781483223568.
  7. ^ Казуо Мурота (2009). Матрицы и матроиды для системного анализа. Springer Science & Business Media. стр. 47. ISBN 9783642039942.
  8. ^ Гэри Чартранд (2012). Введение в теорию графов (переиздание графов как математических моделей , 1977 г.). Courier Corporation. стр. 19. ISBN 9780486134949.
  9. ^ Фрэнк Харари (январь 1967). "Графы и матрицы" (PDF) . Обзор SIAM . 9 (2). Архивировано из оригинала (PDF) 2016-03-04 . Получено 2015-01-09 .
  10. ^ K. Thulasiraman, MNS Swamy (2011). Графы: теория и алгоритмы. John Wiley & Sons. стр. 163 и далее . ISBN 9781118030257.
  11. ^ Нарсингх Део (2004). Теория графов с приложениями к инженерии и информатике (переиздание издания 1974 года). Prentice-Hall of India. стр. 417. ISBN 9788120301450.
Взято с "https://en.wikipedia.org/w/index.php?title=Flow_graph_(математика)&oldid=1219368534"