6. Обгрунтування угорського алгоритму

Метод ланцюгів, що чергуються, заснований на наступній теоремі.

Теорема 6. Наступні 4 умови еквівалентні:

1) у простому графі паросполучення максимальне;

2) у простому графі не існує ланцюгів, що чергуються;

3) у графі не існує шляху, що йде із вершини множини в вершину

множини ;

4) у графі кожну вершину можна позначити знаком «+» або «» так, щоб всі вершини множини одержали знак «+», а всі вершини множини  знак «» і щоб ніяка дуга не йшла з «+» в «».

Доведення. Покажемо, що має місце наступний ланцюжок імплікацій .

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

. Тому що по доведеному в попередньому пункті кожному шляху з у відповідає ланцюг, що чергується.

. Позначимо знаком «+» всі вершини графа , що належать множині , тобто, які є кінцями шляхів, що виходять із вершин , і знаком «» всі вершини множини . При цьому умова 4 буде виконаною. Дійсно, кожна вершина графа позначена. Вершини одержали знак «+», тому що (у кожній вершині є петля). Вершини одержали знак «–», тому що за умовою 3 й, виходить, . При цьому по визначенню множин і ніяка дуга не йде з «+» в «».

. У графі з паросполученням позначимо жирні дуги знаком «+» або «» відповідно до умови 4 і позначимо через множину початкових вершин жирних дуг, позначених знайомий «», а через множину кінців жирних дуг , позначених знайомий «+».

Для дуги , що задовольняє умові , розглянемо чотири випадки розташування (див. мал. 11.6).

Рис. 11.6

Випадок 1. Вершини й ненасичені. Цей випадок неможливий, тому що  повне паросполучення.

Випадок 2. Вершина не насичена, вершина насичена. Тоді існує дуга , інцидентна . Оскільки , дуга повинна бути позначена знайомий «». Далі, вершина  кінець дуги  суміжна з ненасиченою вершиною , тому й повинна бути позначена знайомий «+». Таким чином, і цей випадок неможливий.

Випадок 3. Вершина насичена, вершина не насичена. Цей випадок розглядається також, як і попередній, і так само неможливий.

Випадок 4. Вершини й насичені. Розглянемо дуги , перша з яких інцидентна , друга . Дуга повинна бути позначена знайомий «+», дуга  знаком «». Звідси, насамперед, треба, що . Далі, тому що вершина  кінець дуги  суміжна з початком дуги , позначеної знайомий «+», то . Останнє суперечить умові 4, відповідно до якого жодна дуга не повинна йти з «+» в «-». Таким чином, і цей випадок неможливий.

Тому що випадки 1  4 неможливі, то в кожної дуги або , тобто множина є опорою.

У силу теореми 5 для будь-якого паросполучення й будь-якої опори маємо . У нашому випадку будь-яка дуга паросполучення має тільки одну загальну вершину з опорою . Отже, і паросполучення є найбільшим (а опора  найменшою).

7. Внутрішньо стійкі множини простого графа

З визначення внутрішньо стійкої множини й угорського алгоритму випливає Т.7.

Теорема 7. Множина вершин простого графа тоді й тільки тоді є його опорою, коли множина внутрішньо стійка.

Для числа внутрішньої стійкості з Т. 7 слідує

.

Звідси й з Т.5 випливає Т.8.

Теорема 8. Число внутрішньої стійкості простого графа дорівнює .

Для побудови найбільшого внутрішньо стійкої множини простого графа в силу Т. 7 можна скористатися одним з наведених алгоритмів побудови найбільшого паросполучення в графі .

Відзначимо, що для довільного (не обов'язково простого) графа можна ввести паро сполуки, й з їхньою допомогою будувати його внутрішньо стійкі множини.