Граф потока (математика) - Flow graph (mathematics)

Для потокового графа в информатике см. График потока управления, Корневой граф § Поточные графы, и Схема.

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

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

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

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

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

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

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

Получение потокового графа из уравнений

Пример графика потока сигналов

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

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

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

${\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}}}$

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

Используя примеры из подраздела Элементы графиков потоков сигналов, мы строим график. На рисунке в данном случае представлен график потока сигналов. Чтобы убедиться, что график действительно представляет данные уравнения, перейдите к узлу Икс₁. Посмотрите на стрелки, входящие в этот узел (выделены зеленым для выделения), и на прикрепленные к ним веса. Уравнение для Икс₁ удовлетворяется путем приравнивания его к сумме узлов, прикрепленных к входящим стрелкам, умноженной на веса, прикрепленные к этим стрелкам. Точно так же красные стрелки и их веса дают уравнение для Икс₂, а синие стрелки - Икс₃.

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

${\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}}}$

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

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

Используя диаграмму и суммируя инцидентные ветви в Икс₁ это уравнение выполняется.

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

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

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

• График Коутса
• График потока сигналов

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

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

Рекомендации

1. Дж. Р. Абрахамс, Дж. П. Коверли (2014). «Глава 1: Элементы потокового графа». Анализ потока сигналов. Эльзевир. п. 1. ISBN  9781483180700.
2. Эрнест Дж. Хенли, Р. А. Уильямс (1973). "Базовые концепты". Теория графов в современной технике; автоматизированное проектирование, управление, оптимизация, анализ надежности. Академическая пресса. п. 2. ISBN  9780080956077.
3. Мейсон, Сэмюэл Дж. (Сентябрь 1953 г.). «Теория обратной связи - некоторые свойства графов прохождения сигналов» (PDF). Труды IRE. 41 (9): 1144–1156. Дои:10.1109 / jrproc.1953.274449. S2CID  17565263.
4. SJ Mason (июль 1956 г.). "Теория обратной связи - дополнительные свойства графов потоков сигналов" (PDF). Труды IRE. 44 (7): 920–926. Дои:10.1109 / JRPROC.1956.275147. HDL:1721.1/4778. S2CID  18184015. Он-лайн версия находится на Исследовательская лаборатория электроники MIT.
5. Вай-Кай Чен (май 1964 г.). «Некоторые приложения линейных графиков» (PDF). Скоординированная научная лаборатория, Иллинойский университет, Урбана.
6. РФ Хоскинс (2014). «Блок-граф и сигнальный анализ линейных систем». В SR Deards (ред.). Последние разработки в теории сетей: материалы симпозиума, проведенного в Колледже аэронавтики, Крэнфилд, сентябрь 1961 г.. Эльзевир. ISBN  9781483223568.
7. Казуо Мурота (2009). Матрицы и матроиды для системного анализа. Springer Science & Business Media. п. 47. ISBN  9783642039942.
8. Гэри Чартранд (2012). Вводная теория графов (Переиздание Графы как математические модели, 1977 изд.). Курьерская корпорация. п. 19. ISBN  9780486134949.
9. Фрэнк Харари (январь 1967). «Графики и матрицы» (PDF). SIAM Обзор. 9 (2).
10. К. Туласираман, М. Н. С. Свами (2011). Графики: теория и алгоритмы. Джон Вили и сыновья. стр.163 ff. ISBN  9781118030257.
11. Нарсинг Део (2004). Теория графов с приложениями в инженерии и информатике (Перепечатка изд. 1974 г.). Прентис-холл Индии. п. 417. ISBN  9788120301450.