Графи Коутса і Мезона

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

Схожі статті