Iv. Динамические структуры данных

 Метод чередующихся цепей 
Задача о наибольшем паросочетании решается методом 
чередующихся цепей. Пусть M – некоторое паросочетание в дву-
дольном графе B. Ребра, которые входят в M, будем обозначать 
толстыми линиями, а все остальные – тонкими. Цепь, в которую 
входят поочередно жирные и тонкие ребра, будем называть че-
редующейся. Например, цепь (1, 6, 2, 8) – чередующаяся. По 
определению цепь из одного ребра тоже чередующаяся.
Вершины, которые связаны с жирными ребрами (участвующими в паросочетании), назы-
ваются занятыми или насыщенными). Остальные вершины называются свободными или не-
насыщенными.
Очевидно, что если в графе есть цепь, которая начинается и заканчивается на свободной 
вершине, то в ней тонких ребер на 1 больше, чем жирных. Поэтому такую цепь можно «пере-
красить», то есть заменить все жирные ребра тонкими и наоборот. При этом пар станет на 1 
больше, то есть решение улучшится. Такая цепь называется увеличивающейся. 
Можно доказать, что паросочетание является наибольшим тогда и только тогда, когда в 
графе нет увеличивающихся цепей. На этой идее основан следующий алгоритм.
1. Построим начальное паросочетание «жадным» алгоритмом: будем брать по очереди неза-
нятые вершины первой части и, если существует допустимое ребро, вводить его, не думая 
о последствиях. 
2. Строим ориентированный граф так: все дуги, вошедшие в паросочетание («жирные») на-
правляем вверх, а все остальные – вниз. 
1
2
3
4
5
7
6
1
2
3
4
5
6
7
8
9
10

---

Программирование на языке Си
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
45
3. Просматриваем все свободные вершины первой части. Если среди достижимых вершин 
есть незанятая вершина из второй части, то есть увеличивающаяся цепь. Ее надо увеличить 
и перейти снова к пункту 2.
4. Если увеличивающихся цепей нет, получено наибольшее паросочетание. 
Например, граф на рисунке а) (паросочетание получено «жадным» алгоритмом) после введения 
ориентации принимает вид б). 
Из свободной вершины 5 достижимы вершины 7, 3, 4, 9 и 10, причем из них вершина 10 сво-
бодна, то есть существует увеличивающаяся цепь (5, 9, 4, 7, 3, 10). После ее увеличения полу-
чаем наибольшее паросочетание (рисунок в). 
в) 
1
2
3
4
5
6
7
8
9
10
б) 
1
2
3
4
5
6
7
8
9
10
а) 
1
2
3
4
5
6
7
8
9
10