Введение в прикладную комбинаторику, Кофман А. (984071), страница 50
Текст из файла (страница 50)
Действуем последовательно: а) помечаем кружком каждую строку, не содержащую отмеченных нулей; б) помечаем кружком каждый столбец, содержащий зачеркнутые нули какой-либо из помеченных кружком строк; в) помечаем кружком каждую строку, содержащую отмеченный нуль в каком-нибудь столбце, помеченном кружком; г) повторяем б) и в) до тех пор, пока оказывается возможным получать новые строки или столбцы, помечаемые кружком. Можно нумеровать помечаемые строки и столбцы по мере их получения (как это сделано для нашего примера на рис. 494, 495), но необходимости в этом нет.
«2 «5 «'4 «3 Х, х «4 «2 «3 «4 «5 «6 Оз Х1 Х, Х4 Х5 Х5 О Хб О2 О Рнс. 495. ххххх Рнс. 494. Таким образом, приходим к минимальному множеству линий (т. е. строк или столбцов), содержащих все нули матрицы ) п452«>). Д) Выделеяие минимальной опоры. Проведем пунктирные линии через все не помеченные кружком строки (в нашем примере Хз, Хз, Хз) и все помеченные кружком столбцы (в нашем примере Уз, Уз). Эти пунктиры обозначат минимальную опору. Е) Возможная перестановка некоторых нулей. Рассмотрим подматрицу, образованную элементами, через которые не проходят пунктирные линии, и возьмем наименьший элемент этой подматрицы. Вычтем это число из элементов всех тех столбцов, через которые не проходят пунктирные линии, и затем прибавим его к элементам всех тех строк, через которые пунктирные линии проходят ').
Заметим, что, действуя таким образом, мы изменяем не множество решении, а только общее значение решений. В нашем примере единица вычитается из элементов столбцов Уо У„У4, У, и прибавляется затем к элементам строк Хз, Хзь Хз. Получаем матрицу на рис. 496. Ж) Переход к В). Продолжаем так до тех пор, пока не получим решения с нулевым значением. Пусть в422 — элементы 42 полученной матрицы; оптимальное решение дается тогда такими ее нулевыми элементами о<52=0, что никакие два из них Ц ') При этом все элементы поцматрицы уменьшаются на это число, элементы на пересечении пунктиров увеличиваются на это число, а остальные элементы матрицы остаются без изменения, 409 не расположены в одной строке или одном столбце (это решение монсет не быть единственным).
Значение этого решения определяется через числа оц, стоящие на тех же местах в матрице !!о4,11. В нашем примере оптимальное решение получено уже на рис. 495 (легко показать, что оно единственно). На рис. 497 1 2 3 «4 «5 «б «5 12 13 4 «5 «б Х1 Х1 Х2 Х, Х4 х, Х5 Х, Хб Рис 497. Рис. 498. 11 2 «3 «4 «5 «б х, х, оо = гпах о„ 1=1,2, °, т (очевидно, что матрица не должна содержать символа со). 410 приведены значения оо и видно, что значение оптимального решения равно вы+ о2,+ о 3+ о4,+ ем+ о 5= — 5+1+3+ 4+! + 3= 17. (62,6) Случай т Фп. 1) Если п2 ( и, то присоединим к матрице размера п2 «4 п т — и строк, состоящих из нулей, и с полученной матрицей поступаем так, как было описано.
ГГример дается матрицей на рис. 498; процесс вычислений пока- Х, 7 . б 3 5 5 7 зан на рис. 499 — 502. Х3 5 б 3 7 "'~ 3 4 2) Если т ) и, то присоединяем к матрице размера т К и гп — и 13 -' 13 " " столбцов, состоящих из нулей, и с полученной матрицей поступаем так, как было описано. Рис 498. Пример этого дается матрицей на рис.
503; процесс вычислений показан на рис. 504 †5. Нахождение максимального решения. В некоторых задачах требуется найти насыщенное назначение, которое бы осущест- 45 54 вляло максимум ~б ~ х17обр В этих случаях поступают так. 1 1!=1 1) Находят число 2) Находят далее минимальное решение задачи о назначении для матрицы ~(о,' ~) с о', =о — ооп л=1,2,..., т; !=1,2, ..., и; (627) тогда ои — — о,— о,', 1=1,2, ..., т; )=1,2, ..., и.
(62.8) Если А — множество насыптенных назначений и 5 ен А, то гпах ~ ~зхнон=шш(т, и) о,— ппп ~ ~хио,'1. (62.9) аыа г ! / ! алзд г 1 1 ! Рис. 510. Рис. 511. Насышенное назначение. з+З+Зегт+4+а ЗО а+ 2+2+0+ 7 . 3=та Рис. 512. Рис. 513. П р и м е р. Минимальное назначение для матрицы (о,' 1) имеет значение !6. Отсюда значение максимального назначения! есть 6 К 1! — 16 = 50. Процесс вычислений представлен на рис. 508 — 513. УПРАЖНЕНИЯ 62А.
Используя венгерский алгоритм, найти назначение с минимальным значениелл для графов а), б), в), г), о) из упражнения 54А. 62Б. То же, что в упражнении 62А, но для назначения с ллаксимальнылл значением (оо везде заменить на — со), 413 626. То же, что в упражнении 62А для графов а), б), а) ния 54Е. 62Г. Для каждой нз следующих матриц указать назначение ным значением: «4 «2 «3 «4 «3 «6 из упражнес минималь- «6 «6 О О О 3 !В 9 3 9 3 6 9 8 2 8 О О «! 6 4 9 О О 3 !4 Х4 Х2 а) Х3 х, 2 ! 3 4 5 2 5 3 оо 17 33 оо 7 О 3 62Д.
Метод Исгмена '). Метод Истмена заключается в отыскании гамильтонова контура с минимальным значением, исходя пз решений задачи о назначении с минимальным значением. Предположим, что минимальное решение задачи о назначении содержит нсгамильтонов контур. Из этого контура следует вычеркнуть по крайней мере одну дугу. Пусть, например, в оптимальном решении задачи о назначении содержится контур (Х4, Х3, Х6, Х4); тогда проводят процесс ветвления и ограничения, используя следующие свойства: У43: гамильтонов контур не проходит через (Х4, Х2), У36. .гамильтонов контур не проходит через (Х2, Х6), У64. гамильтонов контур не проходит через (Хз, Х,).
Таким образом, исходя из оптимального решения задачи о назначении, ыожно получить оптимальное решение задачи об оптимальном гамильтоновом контуре Эаметим, что прадерево, получающееся в ходе решения, строят, используя каждый раз разбиение не на две части, а на й частей, где й меняется в ходе процесса (й ) 2). Рассмотреть упражнение 543 и получить его решение с помощью веагерского алгоритма для задачи о назначении, а затем перейти к задаче о гамильтоновом контуре, решая ее методом последовательного ветвления и ограничения.
') См, И стм си (Е а 21ш а п «ч'. Е], А зо!цЕоп 1о йе Тгаче««пй Ва!езгпап Рго5!еш, Ашепсап Бцпппег Мее«!пй о1 йе Есопоше1пс Бос«е1у, СагпЬгЫде, Маза., Ацб. «958. Х4 б) Хз Х4 х, Х6 Хг х «4 «2 «3 «4 4 28 !6 6 3 2 5 7 4 !3 4 О 28 О оо 6 О 5 2 6 !9 4 оо 5 О О 2 8 «3 3! оо О ПРИЛОЖЕНИЕ А БИНАРНАЯ БУЛЕВА АЛГЕБРА. КОЛЬЦО КЛАССОВ ВЫЧЕТОВ ПО МОДУЛЮ в. ПОЛЯ ГАЛУА ХАРАКТЕРИСТИКИ р А1.
Введение В этом приложении мы достаточно подробно рассмотрим некоторые понятия и структуры, которые играют важную роль в комбинаторике; возможно, они известны читателю в той или иной мере. Бинарная булева алгебра есть не что иное, как представление булевой алгебры на подмножествах некоторого множества с помощью переменных функций, принимающих только значенияОи!. Кольца классов вычетов по модулю и рассматриваются главным образом для того, чтобы ввести поля Галуа. Предполагается, что читатель имеет представление о группах конечного порядка. А2. Булева алгебра Рассмотрим следующий простой пример булевой структуры, построенной на множестве (О, 1), на котором заданы операции ~ иД: Ох70=0, Ох71=1, 1 с7 0=1, 1 ч7 1=1, (А2.1) !ДО=О, 1Д!=1, (А22) ОДО=О, ОД1=0 и операция дополнения: 0=1 и 1=0.
(А2.3) В этом частном случае операцию Д можно рассматривать как обычное умножение: 0 х', 0 = О, 0 х', 1 = О, 1;х', О = О, 1 х', 1 = 1, (А2.4) Ввиду того, что операция Ху очень близка к сложению, используют вместо ху символ +. и говорят, что имеют дело со следующей булевой операцией: 0+0=0, 0+1=1, 1+0=1, 1+ 1=1.
(А25) 415 Мы рассмотрели в 5 39 (пример 3) булеву структуру У(Е) для множества Е. Кажется естественным исследовать вопрос о том, существует ли гомоморфизм ') У(Е) в крайне простую структуру (О, 1); в такой постановке гомоморфизм не представляет интереса, так как при этом невозможно различать подмножества с несколькими элементами. Тем не менее, желая сохранить простоту булевой записи, определяют гомоморфизм У(Е) й в множество функций (называе° х мых характеристическими), при- нимающих только два значения: ° у 0 или 1.
Характеристическая функция подмножества. Рассмотрим подРис. 514. множество А множества Е (рис. 514). Соотнесем подмножеству А характеристическую функцию г (х) = Г (А; х) (А2.6) т акую, что ~ (х)= 1, если х~ А, (А2.7) О, если хФ А, т е. х~ А=СвА. Например, на рис. 514 х~А: Г,(х)=1, (А2.8) уев А: 1„(у) =О. (А2.9) Чтобы показать, что таким путем реализуется гомоморфизм, нужно доказать, что для каждой операции, определенной на У'(Е) (т, е, для дополнения, пересечения и объединения), существует соответствующая операция на множестве характеристических функций. Характеристическая функция отрицания. Достаточно обра- титься к определению характеристической функции, чтобы найти связь между Г(А; х) и Г(А; х). Если положим Г(А; х) =(,(х), (А2.10) то либо 1,(х) = 1 и х не принадлежит дополнению (отрицанию) А, следовательно, Г(А)х) =-О, (А2.11) либо 1',(х) = 0 и х ен А, следовательно, Г(А; х) =1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
