Введение в прикладную комбинаторику, Кофман А. (984071), страница 39
Текст из файла (страница 39)
Д) Строим вершину Е„ПЕ„ПЕ,з Вычеркивая строку Х, и столбец Ха в матрице на рис. 273, приходны к матрице на рис. 274, в клетку (Хм Х,) которой ставим оо, Е) Рассматривая матрицу на рнс. 274, видим, что нужно только вычесть ! из строки Хз, что приводит к матрице на рис. 275. Х, Хз ХзХлХт Х~ Хз Хт Хв Хз Хз Х„ «3 Хз Хт х, Рнс. 275.
Рпс. 275. Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна !. Следовательно, для вершины Ем() Ела() Е1з имеем границу 19+ 1 = 20 3) Имеем матрицу порядка 5, поэтому переходим к И). И) Висячие вершины с наименьшим значением, равным 20,— это Езт() Ете() Ем и Е,7й Ем() Еез Произвольно выбираем последнюю '). К) Езт() Е,зП Ев, получилась с помо:цью Уат Переходим к В). В) Рассматривая матрицу на рис.
269 (воспроизведенную иа рис. 276 — выкладки дтя вершины 7 прадерева) н вычисляя у(Хь Х;) для нулевых элементов этой матрицы, получаем, что 0 (Хт, Хз) = 1. Г) Строим вершину Езт() Ем П Ем П Ем, которой отвечает граница 20'+ 1 = 21. Д) Строим вершинУ ЕлПЕ1зПЕвтПЕ,з. Вычеркивая строку Хт и столбец Хз матрицы на рис. 276, приходим к матрице на рис. 277, в клетку (Хз, Хв) которой ставим со, чтобы не получить контура (Хз, Хв, Хм Хт, Хз). Е) Рассматривая матрицу на рис. 278, видим, что ее элементы либо О, либо со.
') По понятной причине предпочтительнее использовать свойство Эя,ь а не У;н 808 Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна О. Следовательно, для вершины Езу Й Ем Й Езз Й Еуз имеем границу 20+ 0 = 20. 3) Имеем матрицу порядка 3, поэтому переходим к И). И) Висячие вершины с наименьшим значением, равным 20,— это Е,уЙ Е,ОЙ Ем и Е„ЙЕ„Й Е, ЙЕм. Выбираем последнюю. К) Е.„Й Е„Й Е„Й Ем получалась с помощью Ууз. Переходим к В).
Х, ХзХз Х, Х, Х, Хз Хз Хз Х, Хз Оуммм О Рис. 218. Рис 277. В) Очевидно, что для матрицы на рис. 278 все у(Хо Х,) равны О. Произвольно выбираем клетку (Хм Х4). Г) Строим вершину Ез,ЙЕ„ЙЕ,ЙЕмЙЕз„которой отвечает граница 20+ 0= 20. Д) Строим вершину Езу Й ЕмЙ ЕззЙ Ем Й Езе Вычеркивая строку Хз и столбец Х, в матрице на рнс. 278, приходим к матрице на рис.
279, в клетку (Хо Х1) которой ставим со, Х~ Хз Х, Хз Хз О Х. 4, Х4 О Рис 280. Рис. 279. Е) Рассматривая матрицу на рис. 279, видим, что ее элементы либо О, либо со. Ж) Сумма элементов, вычтенных из строк и столбцов по Е), здесь равна О. Следовательно, для вершины Е,„Й ЕмЙ Е,зЙЕ„Й Й Ем имеем границу 20+ 0 = 20. 3) Имеем матрицу порядка 2, поэтому переходим к И), И) Выбираем вершину Ем Й Еуз Й Езз Й Ем Й Е„с наименьшим значением, равным 20. зов К) Вершина, выбранная в И), строилась с помощью У54. Переходим к В).
В) Очевидно, что для матрицы па рис. 280 все значения у(Хи Хз) равны со (что означает, что мы больше не можем ис- г Кз Рис 281. Рис. 282 пользовать свойств Узь исходя из Выбираем клетку (Хм Х~). Г) Строим вершину Е„П Ем () Ем граница 20 + сс = сс, рассматриваемой вершины). () Е54() Ез| которой отвечает Х~ Хз Хз Х4 Хз Хз Х7 Х| Хз Хз Х4 Хз Хз Х7 х, х, з Х4 Хз ' 7 х, х, Хз Х4 Хз Хб Х7 3+2+8+2+2+2+3 = 20 Рис. 284. Рис. 283. Д) Строим вершину Е27 П Ем П Ем () Ем П Ем. Вычеркивая строку Хз и столбец Хь переходим к матрице на рнс. 281. Очевидно, что символ сс ставить не нужно'. Е) Очевидно, что в матрице на рис, 281 ничего вычитать не требуется. Ж) Очевидно, что для вершины в Д) нижняя граница 20+ +0=20. 3) Имеем матрицу порядка 1, Процесс закончен.
Для последних двух вершин прадерева имеем нижние границы соответственно сс и 20. 310 Добавляя дугу (Хь Х,), получаем искомый гамильтонов контур со значением 20, так как объединение висячих вершин построенного прадерева дает Е. Найденное решение представлено на рис. 282 — 284. Это решение не единственно, что получается из-за того, что при построении прадерева выбор вершин в некоторых случаях ие однозначен. Одно из других решений представлено на рис. 285 — 287. 3 а м е ч а н и я, При применении алго- Х иг ритма Литтла в случае произвольного графа следует приписать символ с всем парам вершин Хь Хп для которых в гра- ~г фе нет дуги (Хь Х,).
Если задача не имеет решения, то мы более или менее быстро придем к прадереву, все висячие Х вершины которого имеют нижнюю гра- Рис 288. ницу со. Поэтому предпочтительнее узнать заранее, существует ли решение (об этом см.стр. 335 и Я 61,62). Изложенный алгоритм позволяет находить некоторые другие решения, например почти оптимальные, т. е.
решения, значения которых отличаются от оптимального на величину, пе ббльшую некоторого а. Нахождение гамильтонова контура с максимальным значением. Лйожно видоизменить для этого алгоритм Литтла, но предпочтительнее свести задачу к предыдущей. Припишем символ Х~ Хс Хз Х4 Хи Хс Х7 Х, Х Х, Хс Хс Х7 3 + 2 ' 1 ' 7 -',. 2 + 2 Э З = 20 Рис.
287. Рис. 288 ( — оо) всем парам вершин Хь Х„для которых в графе нет дуги (Х„Х,). Пусть си = гпах оьи 7' где 11пп~~ — матрица стоимостей графа с и вершинами. 811 Тогда построим матрицу, элементы которой определяются гак: (54.2) и применим к ней алгоритм Литтла. Полученное минимальное решение дает нам максимальное для матрицы 11 оп |~. Заметим, что минимальное значение с 2 о(~'2 и максимальное с 11 он 1~ в сумме дают пом. П р и м е р. Найдем гамильтонов контур с максимальным значением графа с матрицей стоимостей на рис. 288. Имеем (54.3) ом — — 13. Матрица с элементами (54.4) о,.
=о — о и и о изображена на рис. 289. Л| Хз Хз Х4 Хи Х~ Хз Хз Х4 Хи Х~ Хс ХЗ х, х Хз Хи Рис. 289. Рис. 288 Если назначение (Хь У;) невозможно, то о;, = со. Требуется назначить р работников на р должностей так, чтобы сумма соответствующих значений ои была минимальной (оо могут означать время, стоимость и т. п.). Эта задача равносильна отысканию подстановки с минимальным значением (см. Г! 16). 8!2 Читателю предоставляется возможность провести выкладки, приводяшие к построению прадерева на рис. 290 (см.
рнс, 29!в 300). В результате получаем гамильтонов контур (Хь Х4, Хм Хм Х,, Х1) с минимальным значением 19 для матрицы на рис. 289. Он является гамильтоновым контуром с максимальным значением 5 )с', 13 — 19 = 46 для матрицы на рис.
288 и представлен на рис. 301 — 303. Задача о назначениях. Пусть имеется р работников Хь Х„..., Х„и р должностей Уп Ум..., У„. Каждому назначению (Хо У;) сопоставим число пи=о(Хо У,))0, 1,!'=1, 2, ..., р, Для решения этой задачи можно применить алгоритм Литтла, не используя в пункте Д) символа оо, который не позволял получать контуры длины меньшей п, н отождествляя Х; и Уь Для графа с матрицей стоимостей на рис. 304 процесс вычислений по этому алгоритму иллюстрируют рис. 305 †3.
На рис. 331 приведено другое решение. Нахождение минимального гамильтоиова пути. Для нахождения минимального гамильтонова пути с фиксированным началом Х. следует видоизменить матрицу ~~о,,11: 1) поставить символ со на главную диагональ; 2) в столбце Х. все элементы, кроме о„, заменить нулями и действовать по алгоритму Литтла. Х! Х2 Хз Хэ Хэ Хэ Хг ~2 Хз Х4 Х5 х Рнс 304.
Для нахождения минимального гамильтонова пути с нефиксированным началом следует ввести новую вершину 5, соединяя ее с каждой вершиной Х; дугами (5, Х;) и (Хь 5) с нулевыми значениями, и найти минимальный гамильтонов контур нового графа. Исключая затем из него 5, получают искомый путь. Заметим, что если не существует гамильтонова пути, исходящего из заданной вершины, то об этом нас предупредит со, появившаяся в качестве нижней границы. П р им ер. Вновь рассмотрим матрицу на рис. 257 н найдем минимальный гамильтонов путь с началом в Х,. Процесс вычислений иллюстрируют рис. 332 †3. (Рис.
333 получается из матрицы на рис. 332, если положить ом = 0 (! Ф 2). Этим путем будет (Х2, Х„Хм Х,, Хз, Хь Хз). Нахождение максимального гамильтонова пути.Оно свод)!тся к задаче отыскания максимального гамильтонова контура. Если начало пути не фиксируется, то достаточно ввести новую вершину 5 и соединить ее с вершинами Хь которые могут быть взяты в качестве начала, дугой (5,Х;) со значением 0 и с вершинами Хь которые могут быть взяты в качестве конца, дугой (Х„5) со значением О, а с остальными вершинами — ду.
гами (5, Хь) и (Хь 5) со значением — сю 3!Б 7 /в Е 2 /7 2' /в Е74 Е/„ Бв/ О и Св/ в О~' 67 Е, пЕ пЕипЕипЕи Е/БПЕББПЕББПЕББПЕ47 ЕмпЕипЕи/7ЕипЕС ЕипЕипЕ4777Е75пЕи О /б Е, ПЕББпЕ БпЕБ,ПЕППЕ,Б Е74пЕ БПЕ БПЕ 7ПЕППЕ76 О /в Е/БПЕ ПЕипЕипЕ47ПЕ76пЕ Б Е/БПЕ БпЕ ПЕ 7ПЕ47ПЕ ПЕ25 О Рис. 303. ХБ Хз Хз ХБ Хз Хв Ху Х, Х7 Хз Хз Х4 Хз ХБ Ху хз Х4 ХБ х ХБ ХБ Ху Сумма 13 Рис. 300, Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
