Введение в прикладную комбинаторику, Кофман А. (984071), страница 35
Текст из файла (страница 35)
Например, пусть для графа на рис. 229 (функция ~ указана там же) свойство У вЂ” «быть гамильтоновым путем», а закон композиции — сложение, 273 Например, для графа иа 7 (А, В) = ап ~ (В, В) = ам, 7(Е, Л)=аг, г(А, Р)=а,, 7 (Е, С) = а,, 7 (Р, Р) = акь ( (Р, В) = ам ( (Е, Р) = а,, рис. 228 имеем 7(С, Е) =акь КР, Е) =ап, ~(В С)=а ((С Р)=аз ~ (А, Е) = ам ((С, С) = аиь Из рис. 207 имеем р(А, С, В, Е, Р, Е)=9+4+8+5+9=35, р(В, Е, Р, С, Е, А)=8+ 5+3+0+2=18, р(В, Е, Р, Е, А, С) =8+ 5+ 9+2+ 9=33, р(В, А, С, Е, Е, Р) = 5+ 9+ 0+ 2+ 5=21, 1г(С, В, Е, Р, Е, А) = 4+ 8+ 5+ 9+2=28, р(Р, С, В, Е, Е, А) = 3+ 4+ 8+ 11+ 2 =28, р(Р, Е, А, С, В, Е) =9+ 2+9+ 4+8=32, 1!(Е, Р, Е, А, С, В) =5+ 9+ 2+ 9+ 4=29, 1!(Е, Е, Р, С, В, А)=2+5+3+4+5=19, р(Е, А, С, В, Е, Р) =2+9+ 4+ 8+ 5=28. (50.9) Гамильтонов путь (А, С, В, Е, Р, Е) максимальный, а путь (В, Е, Р, С, Е, А) мннимальныи.
! Юг!!! Я (А! ! ! ! ! ! ! ! ! ! ! ! ! ! ! А ! Рнс. 235. 275 3 а м еч а н и я. 1) В задачах оптимизации рассматриваются также числовые функции, определенные на других упорядоченных множествах. 2) В графе без контуров ог значений на дугах можно перейти к значениям па вершинах и обратно. Например, па рис. 23! показано, как от графа на рис. 230 со значениями, приписанными ребрам, перейти к графу на рис.
232 со значениями, приписанными вершинам, а на рис. 234 показано, как от графа на рис. 233 со значениями, приписанными вершинам, перейти к графу на рнс. 235 со значениями, приписанными дугам. Итак, от графа без контуров со значениями, приписанными как дугам, так и вершинам, можно перейти к графу со значениями, приписанными только вершинам (только дугам). Подпуть.
Подпутеж называют отрезок данного пути. Например, для графа на рис. 229 (В, С, Е, Е) — подпуть пути (В, С, Е, Е, О, С), (В, С) — подпуть пути (Е, Е, О, С), а (Е, О, С) — подпуть пути (Е, Е, В, С, В). УПРАЖНЕНИЯ 50А. Для графов а), б), в), приведенных ниже: Е б б) б) а) 1) указать пути, начинающиеся в А и имеющие максимальные значения, считая законом композиции сложение; 2) то же для путей с минимальным значением; 3) то же, что и в 1), но закон композиции — умножение.
505. Для графов а), б), в) из упражнения 50А указать максимальный гамильтонов путь, если: 1) закон композиции — слозкение, 2) закон композиции — умножевие, 505. Для графа а) из упражнения 50А указать пути длины 3; 1) с минимальным значением, закон композиции — сложение по модулю 4; 2) с максимальным значением, закон композиции — сложение по модулю 5. 50Г. !) Перейти от графа а) к графу со значениями, приписанными вер- шинам. 2) Перейти от графа б) к графу со значениями, приписанными дугам. 1 и) 50Д. !) Перейти от графа а) к графу со значениями, приписанными только дугам. 276 2] Перейти от графа б] к графу со значениями, приписанными только перлинам. 3 3 О О 2 8 1 А В С Р В К О О 3 5 8 2 О 8 11 А В С Р Е У С 77 ЗА ОА ЗВ ЗВ ОС ОР ОГ а) 1!Н $51.
Оптимизация пути в графе без контуров. Теоремы оптимальности Рассмотрим граф 6=(Е, Г)=(Е, О) без контуров и его порядковую функцию й = 0(Хт), Хт ~ Е, принимая за началь- ный уровень подмножество таких вершин Х„что Г-'Х; = Я. Зададимся также функцией >ч = тр(Хт). Теорема оптимальности 1.
Пусть задан макси- мальный (минимальнглй) путь через вершингл между верши- нами Х, и Х,, принадлежащими соответственно уровням пт и 3. Тогда его подпуть между вершинами Х и Хр, принадле- жащими соответственно уровням и и р, и ( т ( р ( 3, также максимален (минимален). До к аз а тельство. Пусть(Х и..., Х,,..., Х,..., Хв„,... ..., Х,,) — путьсмаксимальным значеиием(х *... х, а... *хе... ~1 ... *хрь*... *х,, (Х отсутствует, если (Хтр Хр ) — дуга).
Пред- положим, что значение х, * ... а хе...ехи подпути (Х, тг ''' ''' вв ту~ ... Х, ..., Хр ) не максимально. Тогда существует подпуть (Х, ..., Х', ..., Х,а) со значением, большим указанного. Но это противоречит максимальности заданного пути между Х и Х, . зт Для путей с минимальным значением доказательство прово- дится таким же образом.
П р и м е р (см. рис. 236, закон композиции — сложение), Лег- ко убедиться, что путь (Вз, Св Вз, Еа, Ег) между вершинами Вв и Е> максимальный (со значением 44) и что его подпуть (Сз, Вз, Е,) (со значением 3!) между вершинами Сз и Е, также максимальный, 277 Теорем а опт и м а л ь ности 11. Пусть задан максил!альный (минимальный) путь через дуги между вершинами Х, и Х,, принадлежащими соответственно уровням т и з. Тогда его ' Е!', ', тг,' Ео Е! Ез Еь Е, Ег Ег Рис. 23б. подпуть между вершинами Х, и Хь, принадлежащими соответ- ! отвеина уровням т и р, т ( т ( Р ( з, также максимален (минимален).
Доказательство аналогично доказательству теоремы 1. ,' Е!1 Еь Е! Ег Еь Ел Ез Ез Ряс. 237. П р и м е р (см. Рис, 237, закон композиции — сложение), Легко убедиться, что путь (Вм См Вм с!) между вершинами В, и с, максимальный (со значением 23) и что его подпуть (Сь Ем Р!) (со значением 15) также максимален, 27В 2 52.
Метод динамического программирования Графы без контуров. Рассмотрим граф 6=(Е, Г) без кон. туров и его порядковую функцию 0(Х;), Х; еп Е. Еб Е? Еб ' г~г,с? Еб Еб Еб Ег Е1 Ез Рис 238. Пусть, например, 6-граф на рис. 238, а 0(А) =О, 0(В)=0(С)=1, 0(0)=0(6)=2, 0(Е)=3, 0(В)=4, (52.1) 0(/) =5, 0 (Н) = 0(~) =6, 0(У) = 0(К) =7, 0(М) =8 — его порядковая функция. Ишем путь из М в А с минимальным значением (закон композиции — сложение). Начиная с А, рассматриваем последовательно все вершины графа в порядке возрастания его Рис. 239. порядковой функции (вершины одного и того же уровня рассматриваются в произвольном порядке) и приписываем каждой вершине Х; «потенциал», равный минимальному значению пути из Х, в А. Этот процесс иллюстрирует рис.
239, на котором минимальный путь (он единственный) выделен. Для графа на 2?9 рис. 238 с порядковой функцией О'(А) = 8, О'(В) = 7, О'(С) = О'(О) = 6, О'(Е) = 5, О' (г") = О' (О) =- 4, (52.2) О'Я = 3, О'(О) = 2, О'(7) = О'(К) = О'(Е) = 1 О'(М) = 0 (см. рис. 240) получаем тот же результат (см. рис. 241). 'У 1 1 Ео Е!' Е,' Е,' Е,' Е,' Еа Етс Еа Рис 240. Теоремы оптимальности ($ 5!) дают обоснование изложенного способа, называемого методом динамического программирования.
Он предложен Беллманом и развит им для последовательных графов (см. 3 53). Лвтор и Крюон перенесли его на случай графов без контуров. Условия его применимости; !) граф должен обладать порядковой функцией; 2) закон композиции ассоциативен, т. е. структура системы значений должна быть моноидом, илн полугруппой, Случай, когда начальный и (или) конечнгяй уровень содержат более одной вершины. Пусть заданы граф без контуров О = = (Е, 1э) со значениями, приписанными дугам, и его порядковая функция. Оптимальный путь между его уровнями Еи и Е„ц ( т, можно найти изложенным выше способом.
Для этого достаточно дополнительно ввести две вершины: вход Е и выход 5. Вход Е соединим дугами, приписывая каждой из них значение О, со всеми вершинами Еи, а все вершины Е, соединим дугами с 5, приписывая им также значение 0 (предполагается, что закон композиции — сложение; в случае умножения приписываем этим дугам значение 1). Тогда длина искомого оптимального (т. е. максимального или минимального) пути 1,ср~(Еи, Е,) = (.,м(Е, 3).
(52.3) Графы с контурами. Для таких графов мы не будем заниматься задачей на максимум, так как он может не сушество- 280 вать, а также будем предполагать в дальнейшем, что значения приписываются его дугам. Для отыскания минимальных путей графа существуют различные методы. Алгоритм Форда [23). Будем предполагать, что всем дугам (Хь Х,) рассматриваемого графа приписаны положительные значения 1(Хь Х,) (в противном случае мы могли бы, например, добиться этого, прибавляя к каждому значению абсолютную величину наименьшего из них, увеличенную на 1, и будем Пв Рис. 24к Л, — Л, =1(Хр, Х,) (52.4) и т. д. Так как последовательность Л„, Лрп Лр, ... строго убывающая, то при некотором й получим Хр —— Хо, Покажем, рь+~ = что (Хо, Хрл, ..., Х„) — минимальный путь со значением Л„, т.
е. ') Под символом оо Месь следует понимать достаточно большое положи. тельное число. (Приап перев,) 28! искать минимальный путь из Хо в Х„следующим способом. Каждой вершине Х; будем приписывать символы по следующему правилу: 1) положим Ло = О и Лт = со *) при ю' Ф О; 2) далее каждый раз ищем дугу (Х;, Х;) с условием Л; — Лч ) 1(Хь Х;) и заменяем Л) на Л; =Л; +1(Хь Х;) ( Лт', действуем так до тех пор, пока возможно найти дугу, позволяющую уменьшить Ль Покажем, что по указанным правилам мы можем найти минимальные пути. Действительно, так как при этом Л„монотонно уменьшается, то мы придем к такой вершине Хр, (принадлежащей дуге, с помощью которой в последний раз уменьшилось Л„), что ˄— Лр, — — 1(Хр, Х„). По этой же причине найдется Хр, с что значение 1(Хо, Х»Р Х»„, Х»з ю = Хо) любого другого пути (Х,, Х»Р Х»,, ..., Х„) между Х, и Х„не меньше Л„.
Имеем л,,— О<1(х,, х,,), л,,— л,,<1(х,, х,,), (52,5) л„— л» <1(х», х„). Отсюда л„— О~(1(Хо, Х»,, Х»Р .. Х»,,). Точно так же можно получить Ло = 1 (Хо~ Хр» Хр» ° Хр Х ) т. е. (Хо, Хр, ..., Х,) — минимальный путь. (52.6) (52.7) Рис. 242.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
