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) має вигляд Тому