Page 96 - 4496

Алгоритм заснований на цьому твердженні. Будується
послідовний ланцюг і описаною процедурою збільшується
число ребер у паросполученні, поки це можливо.
Приклад. Розглянемо граф, наведений на рис 3.17.
Виділимо в ньому послідовний ланцюг, наприклад,
1,2,3,5,10,11,7,12,8,4, у якому ребра (1,2),
(3,5),(10,11),(7,12),(8,4) включені в паросполучення.
1 2 3 4

5 6 7 8

9 10 11 12

Рисунок 3.17 - Граф
Рис. 9

Для цього ланцюга шукаємо ланцюг, в який пробуємо
включити вільні вершини 6 і 9 так, щоб вони були початковою
й кінцевою вершинами ланцюга. Такий ланцюг знаходиться:
(9, 10, 11, 7, 12, 8, 4, 3, 5, 1, 2, 6). Виходить, одержуємо нове
паросполучення, у якому число ребер на одиницю більше за
перше. Так як це паросполучення містить усі вершини, воно є
найбільшим. Розв'язком буде множина {(9, 10), (11, 7), (12, 8),
(4, 3), (5, 1), (2, 6)}.
Можна переконатися, що цей розв'язок не єдиний.
Паросполучення називають досконалим, якщо в ньому
беруть участь усі вершини. Очевидно, що досконале
паросполучення, якщо воно в графі існує, буде й найбільшим.
Тому що з кожним ребром пов'язана пара вершин і
ребра у паросполученні не суміжні, то з будь-яким

93