Введение в прикладную комбинаторику, Кофман А. (984071), страница 49
Текст из файла (страница 49)
Обозначим через Х- множество начальных вершин сильных дуг, помеченных знаком « — », и через Ч' множество конечных вершин сильных дуг, помеченных знаком «+». Пусть имеем дугу (Х„, У,) с Х, ~ Х и У,фу и рассмотрим четыре случая, показанных на рис. 471. гм а ф У, Х~ гг „1 Ггн 1' гг г, г Хс» Хс,, а) Ф) д) г) Рис. 47Н а) Х„н У, не могут быть обе ненасыщенными, так как по предположению Ч вЂ” полное паросочетание.
б) Х, не может быть ненасыщенной вершиной, так как тогда о; должна была бы (по определению Ч') быть помеченной знаком «+». в) У, не может быть ненасыщенной вершиной, так как тогда о; должна была бы (по определению Ч-) быть помеченной знаком « — ». г) Х, и У, не могут обе быть насыщенными, так как тогда, вопреки 4), в графе (Ч, Л) существовала бы дуга от о,сиЧ+ до п»~Ч Таким образом, дуги (Х„У,) с Х„~Х и У,ФЧ+ не существует, и множество Х ()Ч~ — опора. Имеем, кроме того, 1Ч1=(Х ()Ч+). (61.62) По теореме, обратной теореме Кенига, получаем, что Ч вЂ” максимальное паросочетанне. Нахождение минимальной опоры. Венгерский алгоритм.
Этот процесс распадается на две части. 1) Нахождение максимального паросочетания. Для этого подходит метод, описанный ранее, но мы дадим другой способ. 2) Нахождение минимальной опоры. 400 Первая частьс нахождение максимального паросочетания. Для получения максимального паросочетания берут какое-нибудь паросочетанне, образуют граф дуг паросочетания (У, Л) и определяют подмножества Ч+ и Ч-. Если существует путь от Ч' до Ч-, то взятое паросочетание не является максимальным. В этом случае можно найти цепь, состоящую поочередно из слабых и сильных ребер, н с ее помощью увеличить число сильных дуг. Так продолжают до тех пор, пока не приходят к.
графу (Ч, Л), в котором нет путей от Ч+ к Ч-. Вторая часть; нахождение минимальной опоры. Чтобы, исходя из максимального паросочетания Ч, построить минимальную опору, находят подмножества ЛЧь н Ч вЂ” ЛЧ+. Конечные вершины дуг, принадлежащих ЛЧ', обозначаются через Ч+, а начальные вершины дуг, принадлежащих Ч вЂ” ЛЧ+, — через Х-. Множество (61.63) 8о=Х ()Ч будет тогда минимальной опорой. П р и м е р 1 (рис. 472). Возьмем сначала паросочетание Ч, показанное на рис. 473.
Найдем для него граф дуг паросочетания и множества Ч' и Ч- (рнс. 474). Видим, что существуют пути нз Ч' до Ч, а именно — петли в вершинах (Хм Уз) и (Хм У,). Цепь (У,, Х,, У,, Х,) позволяет найти паросочетание с ббльшим числом дуг (рис. 475). Для него вновь строим граф (Ч, Л) и находим Ч' и Ч (рнс. 476). Здесь пути из Ч' в Ч- не сушествует, т. е. паросочетание на рис. 475 максимальное. Для определения минимальной опоры находим ЛЧ+ (подмножество, образованное элементами транзитивных замыканий элементов Ч+). Имеем ЛЧ+=)(Х„, У,), (Хм Уь), (Хь Уз)) (6164) и ЛЧ = )(Х~ У ) (Хм У И, (61.65) Концы дуг множества ЛЧ+ дают Ч+; )1 3 Уб У7)~ (61.66) а начала дуг Ч вЂ” ЛЧ дают Х (61.67) х =(х, х) (рис.
477 и 478). П р и м е р 2 (рис. 479). На рис. 480 показано некоторое паросочетание. Оно не максимальное, что показывает граф на рис. 481. Увеличиваем на ! число дуг в паросочетании, используя цепь (Ум Хп Ун Хм Ум Хь) 401 Х! Хб Уг /)/, 1/ Рис. 472. Рис 473. Рис. 474. У! ! ! ! ! и Хг 4 Хб Уб 5 5 Уг '.-- --' ( Щ Рис. 476. Рис. 478. х=- и /Х 1 1.Хг Х5,9 а ! х, Рис. 478. Рис 477. 402 У! Х, г Уа Х Х, У Х У б Уг "г ! Уа ! Уа \ ! Уб Уг Уа ! ! Уб / УХу" !' /Ха! "г) ) 1 1Ч /Хг! Уг) ' 1 ! ! ! + ! ! (/ /Х,,У,) Я У'=((Х„Уа), (Х„Уб) ), г(!(Х,,У,))=((Х,,У),(Х,,У,),(Х„У,)); Л((Х5,Уг))=((Ха!У),(Х,, У),(Х5!Уг) !! г(1(хб Уа)) 1(хб!Уб)! (рис. 482). Как показывает граф дуг паросочетания на рис.
483, можно увеличить число дуг в паросочетанни еще на 1, если использовать цепь (Ум Хи, Уз, Хм Уо Хг). Приходим к паросочетанию па рис. 484. Это паросочетание максимально, так как Ъе = И (рис. 485). Далее бЧ4. = Я, поэтому Ч+ = Ы и минимальная опора есть Ьс = Х. Нахождение минимальной опоры с помощью булевой матрицы. Если максимальное паросочетанне уже получено, то действуем следующим образом: а) помечаем знаком Я все строки, в которых нет 1, выделенной полужирным шрифтом; б) помечаем знаком Я все столбцы, содержащие 1, не выделенные полужирным шрифтом в помеченных строках; ~3 «и «3 «4 «5 «б «7 Х, «з Х, Х о о о о Хю щ о о Рис.
488. Рис. 487. в) помечаем все строки, содержащие 1, выделенные полужирным шрифтом в помеченных столбцах; г) повторяем б) и в) до тех пор, пока удается помечать новые столбцы или строки; д) помеченные столбцы и непомеченные строки дают минимальную опору. П р и м е р (рис. 486, где воспроизведен результат, полученный на рис. 459). Согласно описанной процедуре помечаем по порядку строку Хи, затем столбцы Уь и Уи, затем строки Хи и Хи, затем Уг и, наконец, Хм Помеченные столбцы Ум Ум Уг и непомеченные строки Хь Хи дают минимальную опору (Хь Хм Ум У,, У,) (рис. 487).
Имеются и другие решения, так как максимальное паросочетание не единственно. Рис. 487 иллюстрирует общий факт:минимальнал опора есть минимальное множество линий, содержащих все !. Под линией понимаем здесь столбец или строку, 404 УПРАЖНЕНИЯ 61А. Указать мкнил1альное покрытие для простых графов а) н б) нз упражнения 61Е. 616, Найти максимальное паросочетаане для простых графов а), б), е) н г) из упражнения 61Е. 61В. Найти число дуг максимального паросочетания для простых графов а), б), е) и г) из упражнения 6!Е. 61П Вычислить дефицит каждого из простых графов г), д) н е) нз упраж.
пения 61Е. 61Д. Найти минимальную опору и уназать число ее вершин в каждом из простых графов а), б), в), г), д), е) из упражнения 6!Е. Х Х/ Х Х, Хг Хб Хб Х А Е е) 61Е. Найти множество всех минимальных опор для каждого из гра. фов а) — е). й 62. Задача о назначении Эта задача уже была сформулирована в В 54. Здесь мы продолжим ее изучение и покажем ее связь с результатами предыдугцего параграфа. Пусть имеются пт работников, и должностей и мера ценности (стоимость) работника Х; на должности Уб равна 406 у у, х х, уг Х уг Х Уб Хб Уб Х, Уз :% ои = и(Хь У;))~ О.
Рассмотрим булеву матрицу )!хо)1 размера т Х п такую, что ~х! (1, /=1,2,..., п, (62.1) 4=! ~ хи ( 1, 4 = 1, 2, ..., 7а. )=! Матрица 1)хи)) называется нагрицей назначения. Имеем (62.2) У, хи ( ш! и (т, п), 4=! ! ! (62. 3) и если Н4 Л ~ ~4 ХН вЂ” — Пн'П(т, а), — 7=! то матрица назначения называется насыщенной. В этих терминах задача о назначении формулируется следующим образом: (62.4) ! 2 3 4 5 б )7 У! У2 УЗ ) 4 Уб Уб Ут х, х, х, 1) "Ч(- 3 4 Х5 з Х4 Хб !нуле не обозначена) Рис. 489. Рис. 488 найти насыщенную матрицу назначения, для которой л л Х Х х го!7 минимальна.
4=! 7=! На рис. 488 приведен пример матрицы ))п;,11, а на рис. 489— насыщенная матрица назначения с общей стоимостью пш+ пш + о„+ и„+ и„= 3 + 7+ 7 + 10+ 10 = 3?. Алгоритм решения задачи о назначении. Опишем этот алгоритм для т = а; позднее мы покажем, как общий случай (т Ф и) можно свести к рассматриваемому. В его основе— венгерский алгоритм '), позволяющий найти минимальную опо- 406 ') Венгерский алгоритм был найден около трпдпати лет вазад. В настоящее время предпочитают пользоваться методом последовательного ветвления и ограничения, который быстрее и проще приводит к цели в задачах с небольшими размерами матриц.
Но при решении задач с большимв размерамн матриц преимущество на стороне венгерского алгоритма. ру простого графа. Для иллюстрации приведем пример матрицы 1!011~! на рис. 490. Предварительно сформулируем одну несложную лемму. Л е м м а. Множество решений задачи о назначении не изменяется, если все элементь1 какой-нибудь строки или какого- нибудь столбца уменьшить или увеличить на одно и то же число 7..
Д о к а з а т е л ь с т в о. Действительно, каждое решение задачи о назначении использует одно и только одно число оп в каждой строке и каждом столбце. Поэтому единственным следствием уменьшения или увеличения элементов какой-нибудь ~1 ~2 ~з ~4 ~5 тб строки (илн столбца) на величину 7. будет уменьшение илн увеличение на 7. значения каж- Х2 6 3 9 ! 7 дого решения. (17)= х 5 з 5 в з Описание алгоритма.
Он рас- з падается на семь этапов. Х4 9 1 З 5 4 А) Получение нулей. Из ка>к- Х, 1 2 1 - 2 З дого элемента столбца Уз вычитаем наименьший элемент этого столбца и образуем матрицу с Рис 490. элементами о,",1 = 01 — ппп 01 11 Н . Ц' Далее, из каждого элемента строки Хз полученной матрицы вычитаем ее наименьший элемент и образуем матрицу с элементами о~." = о',.'~ — ппп о)п. и н ( Матрица ~~о121(~ имеет нуль в каждой строке и каждом столбце.
Для матрицы ~~о11!! на рис. 490 матрица !)о~.'2!) показана на рис. 491, а матрица ) о12')! — на рис. 492. Б) Нахождение полного паросочетания. Ищем решение с нулевым значением для матрицы ) 0~2,.'). Если такое решение удается найти, то оно будет оптимальным. В противном случае переходим к В). Для нахождения решения с нулевым значением рассматриваем сначала первую строку матрицы и отмечаем один из ее нулей, а остальные нули, а также другие нули того столбца, где отмечен нуль, зачеркиваем. Затем переходим ко второй строке; если она содержит незачеркнутый нуль, то отмечаем его н вычеркиваем остальные нули этой строки и все другие нули столбца, в котором находится отмеченный нуль.
Поступаем аналогично с остальными строками. В нашем примере (рис. 493) сначала отметили о1122 и зачеркнули о121 и о4",'. Затем отметили о425, оз122, зачеркнули овз2 и т. д. Насыщенное назначение получить не удалось (строка Х4 не содержит отмеченных нулей). Переходим к В). 407 В) Нахождение максимального паросочетания. Используем алгоритм, изложенный на стр. 390 — 391, но здесь вместо единиц будем обращать внимание на нули.
Помечаем косым крестиком каждую строку и каждый столбец, содержащие отмеченный нуль. В каждом из непомеченных столбцов найдем неотмеченный путь в какой-либо помеченной ! 3 «3 ~4 ~5 ~б 1 3 УЗ 4 «5 5 х, Х1 х, )(б "1)с «З Х4 Х5 «, () 3,'4)~с «з Х, х, Рис 492. Рис. 491. 408 строке. Исходя из отмеченного нуля в этой строке, находим не- отмеченный нуль в том же столбце и непомеченной строке. Если это удается сделать, то мы имеем возможность увеличить число отмеченных нулей. В противном случае ищем неотмеченнын нуль в том же столбце и помеченной строке и, исходя из отмеченного нуля в этой новой строке, ищем нуль в том же столбце н какой-либо непо- Х, з Я ° 3 меченной строке и т.
д. Эту процедуру е 4 проводим для каждого непомеченного столбца. Если таким путем не удается Хз 3 [ ] )3 4 3 увеличить число отмеченных нулей, то это означает, что найденное нами паросочетание максимальное. Х,Н 4 В нашем примере не помечается 3 (51 5 лишь столбец У,, В этом столбце имеется неотмеченный нуль на месте (Хм Уб) в помеченной строке Хз. Отмеченный нуль в этой строке находится на месте (Хм У1). Но в столбце У~ он вообще единственный. Поэтому дальше действовать нельзя, и полученное паросочетание максимальное. Если максимальное паросочетание дает насыщенное назначение, то оптимальное решение получено и процесс останавливается. В противном случае переходим к Г). Г) Нахождение минимальной опоры (минимального множества линий, содержащего все нули).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
