Шаг 6 алгоритма дает

Ai = min[9 + 6 -10, 11 + 6 - 13, 4 + 3 - 5] =

ребро (ж ж,) ребро (ж ж.) ребро (ж , ж )

= 2 соответствует ребру {xz, Хц),

А2= 2 f + - соответствует ребру (xq, Х12),

д3 = 00 ограничение отсутствует.

Таким образом, А = min [2, 1, 00] = 1.

После изменения весов новый вектор л принимает вид [л^] = = (8, 3, 10, 6, 2, 3, 7, 7, 6, 5, 3, 3), а вес К^, соответствующий нечетному множеству вершин = (хз, Х4, Xg, Xg, х,}, равен 2.

га; (б)

Рис. 12.20. (а) Граф Gj. (б) Граф G.

Для нового вектора весов [л;, Яг] новый специальный остовный подграф Gi графа Gi изображен на рис. 12.21; ребро (xjj, Xbj) входит в старый подграф Gj.

Так как дерево на рис. 12.19 сохраняется, то новое вошедшее ребро приводит к образованию цветка, состоящего из нечетного цикла (xi2, Xg, Xbi). Это сразу же обнаруживается на шаге 3, а на шаге 4 цветок срезается; возникает псевдовершина хьг и получается новое дерево, показанное на рис. 12.22. Сам граф теперь будет Gj, а его специальный остовный подграф - G3; эти графы представлены соответствецно на рис. 12.23а и рис. 12.236.

Дерево, изображенное на рис. 12.22, является венгерским деревом в G3, и на шаге 6 вычисляется новое значение А для изменения

вектора весов:

Ai = min[84-6-10, 104-6-13, 7-f-5-9, 3-f-3-5] =

ребро7ж ж,) ребро (ж„ ж,) ребро (ж„ ж, ) ребро (ж, ж„)

= 1 соответствует ребру {Xiz, Хц),

Д2=оо и Ао = 00.

Новое только что вошедшее ребро

Рис. 12.21. Новый специальный остовный подграф Gj для графа Gj из рис. 12.20(a).

Соответствует множеству

Рис. 12.22. Альтернирующее дерево в Gj из рис. 12.21.

(а) (б)

Рис. 12.23. (а) Граф Gj. (б) Граф G.

Следовательно, А = 1. Используя это значение А, получаем [л;] = (7, 4, 9, 5, 1, 2, 6, 6, 6, 5, 3, 2), а вес Яз, соответствующий нечетному множеству вершин Sq = {жд, х^, х^, Xg, ж Xg, Ху}, равен Яг = 2. 26 н. Кристофидес

Новое только что вошедшее ребро

Рис. 12.24. Новый специальный остовный подграф Gg для графа 6 из рис. 12.23(a).

Для этих новых весов [nj-, К] новый специальный остовный подграф графа изображен на рис. 12.24. После введения нового ребра {xi2, Хц) альтернирующее дерево на рис. 12.22 становится аугментальным, так что новое ребро входит в паросочетание. Это дерево отбрасывается , и строится новое дерево с корнем в одной из оставшихся экспонированных вершин графа G, т. е. в вершине х^ или Хю- В любом случае ребро {хд, х^) сразу же попадает в паросочетание и получается совершенное паросочетание. Это совершенное паросочетание графа показано на рис. 12.25 (а). Чтобы найти соответствующее паросочетание в Gq, мы сначала распустим цветок и построим в нем совершенное паросочетание, как показано на рис. 12.25 (б), а затем распустим цветок bi и построим в нем совершенное паросочетание (см. рис. 12.25 (в)). На этом рисунке жирными линиями изображено максимальное совершенное паросочетание графа G; вес этого паросочетания равен 66. Так как в соответствии с теорией линейного программирования максимум величины z из (12.11) равен минимуму величины и из (12.16), то можно сделать проверку. Поскольку I 5i I = 2gi 4- 1 = 5 и I I = 2д2 4- 1 = 7, Togi = 2 и g2 = 3, так что

и = (7-f4-f9-f5-fl + 2 + 6 + 6-f 6 + 5 + 34-2) +

+ (2x2 + 3x2) = 66

3.3. Некоторые вычислительные результаты

Алгоритм для ЗНП, а следовательно, и для ЗМП, является хорошим алгоритмом в том смысле, что необходимое для него число операций является полиномиальной функцией от числа п вершин графа. Для ЗНП требуемое для вычислений время растет какО[п^], хотя на практике этот рост значительно медлен-