2015-05-14
554
Паросочетание, отображающее X в Y, существует тогда и только тогда, когда 
Это значит, что подмножество B должно быть не меньше любого подмножества A 
X. В качестве подмножества A рассматриваются все сочетания из | X | вершин по 1, 2, 3,…, | X | вершин.
Дефицитом двудольного графа G (X, Y, E) называется число
Для графа рис. 24.2 имеем
|{ x 1}| – |Г{ x 1}| = 1 – 3 = – 2, |{ x 2}| – |Г{ x 2}| = 1 – 2 = – 1,…,
|{ x 1, x 2}| – |Г{ x 1, x 2}| = 2 – 5 = – 3, …, |{ x 4, x 6}| – |Г{ x 4, x 6}| = 2 – 1 = 1,…,
|{ x 1, x 2, x 3, x 4, x 5, x 6}| – |Г{ x 1, x 2, x 3, x 4, x 5, x 6}| = 6 – 5= 1.
Следовательно, дефицит графа 
=1.
Максимальное паросочетание – это паросочетание V 0 с максимально допустимым числом ребер (дуг).
Для отыскания максимального паросочетания по матрице смежности графа проделаем следующее.
1. Реализуем некоторое паросочетание, выделяя полужирным шрифтом одну и только одну 1 в строке и столбце (см. табл. 24.6).
Таблица 24.6
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | |
| x1 | |||||||
| x2 | |||||||
| x3 | |||||||
| x4 | |||||||
| x5 | |||||||
| x6 |
2. Помечаем крестиком все строки и все столбцы, которые содержат 1, выделенные полужирным шрифтом (табл. 24.7).
|
|
|
Таблица 24.7
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | ||
| x1 | 
| |||||||
| x2 |
| |||||||
| x3 |
| |||||||
| x4 | ||||||||
| x5 | ||||||||
| x6 |
| |||||||
|
|
|
|
|
3. Рассмотрим непомеченные столбцы.
В непомеченном столбце выбираем 1, которая одновременно принадлежала бы помеченной строке. Находим в этой строке 1, выделенную полужирным шрифтом, и в соответствующем ей столбце ищем 1, которая принадлежала бы непомеченной строке.
Если такая единица есть, то число выделенных полужирным шрифтом единиц можно увеличить. В противном случае ищем 1 в помеченной строке, по 1, выделенной шрифтом, в этой строке ищем…
Если не можем больше найти столбца, с помощью которого можно увеличить число выделенных шрифтом 1, то единицы, выделенные полужирным шрифтом, дают максимальное паросочетание.
В рассматриваемом примере столбец y 7 не помечен. Он содержит 1 в клетке (x 3, y 7). В строке x 3 единица, выделенная полужирным шрифтом, стоит в клетке (x 3, y 6). В столбце y 6 в клетке (x 5, y 6) стоит 1 и соответствующая ей строка x 5 не помечена. Следовательно, возможно увеличить число единиц, выделенных полужирным шрифтом. Выделяем полужирным шрифтом 1 в клетке (x 3, y 7), а перед этим запишем обычным шрифтом 1 в клетку (x 3, y 6), и выделяем полужирным шрифтом 1 в клетке (x 5, y 6) табл. 2.8.
|
|
|
Таблица 2.8
| y1 | y2 | y3 | y4 | y5 | y6 | y7 | ||
| x1 |
| |||||||
| x2 |
| |||||||
| x3 |
| |||||||
| x4 | ||||||||
| x5 | ||||||||
| x6 |
| |||||||
|
|
|
|
|
Нетрудно проверить, что процедуру нельзя продолжить. Единицы, выделенные полужирным шрифтом, дают максимальное паросочетание
V 0 = {(x 1, y 2), (x 2, y 1), x 3, y 7), (x 5, y 6), (x 6, y 3)}.
На рис. 2.38 приведен граф, соответствующий матрице табл. 2.8, на котором максимальное паросочетание выделено толстыми линиями.
Рисунок 24.5
В общем случае может быть несколько возможных решений.
Список литературы
1. Федоров В.Н. Введение в теорию множеств– М.: МГУПИ, 2006. – 85 с.
2. Федоров В.Н. Введение в теорию графов – М.: МГАПИ, 2005. – 120 с.
3. Р. Хаггарти Дискретная математика для програмистов. – М.: Техносфера 2012. – 400 стр.
4. Новиков Ф. А. Дискретная математика: Учебник для вузов. – СПб.: Питер, 2011. – 384 с.
5. Тишин В. В. Дискретная математика в примерах и задачах. – СПб.: БХВ-Петербург, 2012. – 352 с.
6. Микони С. В. Дискретная математика для бакалавра. Множества, отношения, функции, графы. – СПб.: Лань, 2013. – 192 с.
7. Спирин П.А., Спирина М.С. Дискретная математика. Учебник – М.: Academia, 2014. – 268 с.
8. Осипова В. А. Основы дискретной математики. – М.: Инфра-М, 2012. – 160 стр.
Учебное пособие
Смирнов Александр Михайлович
ДИСКРЕТНАЯ МАТЕМАТИКА
–––––––––––––––––––––––––––––––––––––––––––––––––––––––
ЛР № 020418 от 08 октября 1997 г.
Подписано в печать _________________
Формат 60x84 1/16
Объем 4 п.л. Тираж 100 экз. Заказ № _________
–––––––––––––––––––––––––––––––––––––––––––––––––––––––
