6.11. Графы Коутса и Мэзона

В этом разделе мы рассматриваем теоретико-графовый подход к решению линейных алгебраических уравений. Обсуждаются два тесно связанных метода, принадлежащих Коутсу [6.10] и Мэзону [6.11, 6.12].

6.11.1. Метод Коутса

Рассмотрим линейную систему, описываемую системой уравнений

где — невырожденная матрица порядка — вектор-столбец неизвестных переменных . В — вектор-столбец элементов — входная переменная.

Решение для можно записать в виде

где — алгебраическое дополнение элемента матрицы А.

Пусть А — матрица, полученная добавлением —В к правой части матрицы А и затем к нижней части поручившейся матрицы нулевой строки. Свяжем взвешенный ориентированный граф с матрицей А.

Пусть имеет вершину . Если , то пусть в будет дуга имеющая вес Очевидно, что А — транспонированная матрица смежности . Граф называется графом потоков Коутса или просто графом Коутса, связанным с матрицей А. Будем также говорить, что граф Коутса связан с системой уравнений (6.26).

Рассмотрим в качестве примера систему уравнений

В этом случае матрица А имеет вид

Граф Коутса связанный с системой уравнений (6.28), представлен на рис. 6.12, а.

Заметим, что каждую вершину (1 i и) графа можно рассматривать как представляющую уравнение в системе (6.26). Например, уравнение в (6.26) можно получить, приравнивая к нулю сумму произведений весов дуг, заходящих в вершину переменных, соответствующих вершинам, из которых эти дуги исходят. Кроме того, удаляя из графа вершину можно получить граф Коутса связанный с матрицей А. В случае системы уравнений (6.28) граф Коутса представлен на рис. 6.12, б.

Поскольку А — транспонированная матрица смежности а сама матрица и ее транспонированная матрица имеют равные определители, из теоремы 6.27 следует, что

где — 1-фактор графа — весовое произведение подграфа , a — число контуров в нем. Таким образом знаменатель выражения (6.27) можно выразить через весовые произведения -факторов графа Для вывода подобного выражения для числителя формулы (6.27) необходимо выражение для ДЛ.

Рис. 6.12. а — граф Коутса б — граф ; в - 1-факториальное соединение графа

1-факториальным соединением вершины с вершиной в графе является остовный подграф графа который содержит а) ориентированный путь Р из вершины в вершину множество вершинно-непересекающихся контуров, содержащих все вершины графа за исключением контуров, входящих в путь -факториальное соединение, например вершины с вершиной графа (рис. 6.12, а), представлено на рис. 6.12, в.

Теорема 6.28. Пусть — граф Коутса, связанный с матрицей А порядка Тогда

2) графа, полученного из удалением вершины - 1-факториальное соединение в вершины с вершиной число контуров в соответственно.

Доказательство. 1. Следует из теоремы 6.27.

2. Заметим, что определитель матрицы, полученной из матрицы А заменой столбца на столбец, состоящий из нулевых элементов, за исключением который равен 1. Обозначим эту матрицу через Тогда граф Коутса получается из исходного графа удалением всех исходящих из вершины (включая и петли, инцидентные вершине ), и введением дуги с весом 1. Теперь из теоремы 6.27 получаем

где -фактор графа — число контуров в

В каждом -факторе На обязательно должна содержаться введенная дуга с весом I. Удаляя эту дугу из -фактора На, мы получаем -факториальное соединение графа При этом Легко убедиться также в том, что между в графе в графе существует такое взаимнооднозначное соответствие, что Поскольку число контуров в -факториальном соединении на единицу меньше, чем в Поэтому из выражения (6.30) получаем

Рассмотрим теперь числитель выражения (6.27) . Эта сумма равна определителю матрицы, полученной из матрицы А заменой столбца на В. Легко связать его с — матрица, полученная из матрицы А удалением строки и столбца):

Из части 2 теоремы 6.28 получаем

где — число контуров в -факториальном соединении в графе Объединяя выражения (6.31) и (6.32), получим

Из выражений (6.29) и (6.33) получаем следующую теорему:

Теорема 6.29. Если матрица коэффициентов А невырожденная, то решение уравнения (6.26) определяется следующим образом:

1. - 1-факториальное соединение вершины с вершиной в графе

2. 1-фактор графа .

3. — число циклов в t и Я соответственно.

Уравнение (6.34) называется формулой коэффициента усиления Коутса. Проиллюстрируем применение этой формулы, решая уравнение (6.28) относительно

1-факторы графа (рис. 6.12, б), связанные с матрицей А из уравнения (6.28), приведены ниже со своими весовыми произведениями. Различные контуры в -факторе отличаются порядком вершин в скобках

Подсчитаем числитель выражения (6.34):

Приведем -факториальныесоединения (рис. 6.12, а). Сейчас в скобки заключаются также вершины, лежащие в ориентированном пути.

Подсчитаем числитель выражения (6.34):

Таким образом,

6.11.2. Метод Мэзона

Для иллюстрации метода Мэзона перепишем уравнение (6.26) в виде

Можно представить эти уравнения в матричном виде следующим образом: где А — определенная ранее матрица порядка — единичная матрица порядка вектор-столбец переменных

Рис. 6.13. а — граф Мэзона б — граф .

Граф Коутса называется сигнальным графом потоков Мэзона или просто графом Мэзона, связанным с матрицей А, и обозначается через Например, на рис. 6.13 приведены граф Мэзона и граф , связанный с системой уравнений (6.28).

Каждую вершину в графе можно рассматривать как переменную. Если между вершинами есть дуга, то можно считать, что переменная делает вклад в переменную Х). Другими словами, равна сумме произведений весов дуг, заходящих в вершину и переменных, соответствующих вершинам, из которых исходят эти дуги. Таким образом, граф Мэзона — удобное графическое представление потока переменных в системе.

Заметим, что для получения графа Коутса из данного графа Мэзона из веса каждой петли мы просто вычитаем единицу, а на

каждую вершину графа Мэзона без петли вводим петлю с весом —1. Иначе говоря, граф Коутса можно получить из графа Мэзона простым введением на каждую вершину петли с весом —1. Будем обозначать множество таких петель веса —1, добавляемых для построения графа через 5. Отметим, что построенный таким образом граф будет иметь в каждой вершине, самое большее, две и в то же время не менее одной петли.

Рассмотрим связанный с матрицей А граф Мэзона ; пусть граф будет соответствующим графом Коутса. Пусть — 1-фактор графа имеющий петель из множества . Пусть — общее число контуров Я. При удалении из добавленных петель множества 5 получим первоначальный подграф Q графа являющийся набором из вершинно-непересекающихся контуров. Кроме того, при

Заметим, что если , то Q — пустой подграф имеющий по определению вес . Поэтому в этом случае

Легко видеть также, что всякому подграфу Q графа являющемуся набором из вершинно-непересекающихся контуров, в графе соответствует единственный -фактор, который получается введением на вершины, не входящие в Q, петель (из множества S) весом —1.

По теореме 6.27 мы имеем

Последний шаг в этом выводе следует из выражений (6.35) и (6.36). Выражение (6.37) можно представить в виде

где — весовое произведение подграфа являющегося набором из k вершинно-непересекающихся контуров.

Таким образом, мы выразили знаменатель выражения (6.27) в весовых произведениях соответствующих подграфов графа Мэзона.

Назовем определителем графа и обозначим его через А. Тогда, используя выражение (6.33) и рассуждая точно так же, как при выводе выражения (6.38), выразим числитель в виде

где ориентированный путь из вершины к вершине в графе — определитель подграфа того же графа,

вершинно-непересекающегося с ориентированным путем . Таким образом, приходим к следующему утверждению:

Теорема 6.30. Если матрица коэффициентов А в выражении (6.26) — невырожденная, то

где ориентированный путь в графе от вершины к вершине — определитель подграфа вершинно-непересекающегося с ориентированным путем к, определитель графа

Уравнение (6.39) называется формулой коэффициента усиления Мэзона. В литературе по теории систем — прямой путь от вершины к вершине Контуры называются петлями обратной связи. Проиллюстрируем применение формулы (6.39) к решению уравнения (6.28) относительно

Приведем различные наборы вершинно-непересекающихся контуров (рис. 6.13, б) и их весовые произведения.

Вычислим знаменатель выражения (6.39):

Приведем различные ориентированные пути (рис. 6.13, а) из вершины в вершину вместе с их весовыми произведениями:

Контурами, вершинно-непересекающимися с прямыми путями являются петли соответственно. Поэтому

. Контуров, вершинно-пересекающихся с прямыми путями нет, т. е.

Таким образом, числитель выражения (6.39) имеет вид Поэтому