Введение в прикладную комбинаторику, Кофман А. (984071), страница 43
Текст из файла (страница 43)
Найдем минимальное дерево. Заменим значения ребер о(йг) на о'(йг) так, чтобы множество всех значений было строго упорядочено. Если й ребрам приписано одно н то же значение, т, е. о(йо) = о(йм) = ... ... = о(йга), то положим о' (йи) = о (йп), о'(йге) = о (йи) + е, о' (и,а) = о (ип) + 2е, о' (йы) = о (йп) + (Й вЂ” 1) в, где е определяется из условия о(ии)+(й — 1) е < о(й ) при о(й,) < о(йп) = о(й„) = ... = о(и„) < о(й,). Образуем полный неориентированный граф 6,=(Е, Ю,), соответствующий графу гг = (Е, С)), и припишем ребрам гог из О, — 1) такие значения о'(го ), что: 1) (Чйг еп(0,— О))о'(в ) > ~ о'(йг), (58.3) аглай 2) множество всех значений о'(гог) строго упорядочено.
(58.4) Построим дерево (Е, %) в О„где %= (йго гог, ..., йг„г), (58.5) действуя следующим образом. В качестве й~ берем ребро из О, с наименьшим значением, за вг — ребро с наименьшим значением среди таких го, что (йгг,го) не составляют цикла; поступаем аналогично до тех пор, пока не придем к такому графу (Е,%а), что добавление ребра между любыми двумя вершинами приводит к циклу. В силу свойств 4) и 2) определения дерева (э 38) (Е,%а) — дерево с й = и — 1 ребрами.
Покажем, что дерево (Е, %) минимальное. Предположим, что значение некоторого дерева (Е, %') меньше, чем значение (Е, %). Пусть в„— первое ребро, пе входящее в %'. В силу ') Л. В. К го а1г а 1, Оп 1не Япог1еа1 8рапп1пя 8пЫгее е1 а СгарЬ, Ргос. Апгег. Мага, 8ос. 7 (1986), 48, 881 свойства 4) $38 в (Е, %'() (сй,)) существует единственный цикл, а на нем ребро и, Ф%. Положим У=(%'() (Ф,1) — (ис). Граф (Е, Т) — дерево в силу свойства 2) 2 38, так как не обладает циклами и содержит л — ! ребер. С другой стороны, с помощью (юь Ум ..., У„1) () (йс) нельзя получить цикла, так как это множество содержится в %' и А В С Р Е Е 0 Рис. 38Ц Рис, 382.
вследствие выбора й„имеем о(йс) ) о(У„). Таким образом, дерево (Е, У) имеет значение меньшее, чем дерево (Е,%'). Пришли к противоречию. Если граф б полный, то все доказано. Пусть он не является полным. Покажем, что построенное выше дерево минимально А В С Р Е Е 0 Рис. 384. Рис. 383, и для такого б. Действительно, в силу (58.3) нн для какого ( невозможно, чтобы сйз ~ О. Отсюда следует также, что если все значения ребер й, различны, то минимальное дерево единственно.
Заметим, что в силу двойственности мы можем прийти к минимальному дереву, выбрасывая ребра с наибольшими значениями так, чтобы не нарушалась связность графа, 332 Очевидно, что по алгоритму Краскала можно найти и максимальное дерево. Обоснование в этом случае проводится аналогично, если приписать значение 0 ребрам в ~ !). П р и м е р. Рассмотрим неориентированный граф на рис. 38(, ребрам которого приписаны значения так, как показано на рис.
382. А В С Р Е Е 6 А В С Рис. 388. Рис. 385. По алгоритму Краскала найдем минимальное дерево для указанного графа. Очевидно, что за си1 нужно взять (А,0) с охи =! (на рис. 384 оно отмечено 1). Далее берем (В, С) и (В, б), для которых овс = ови = 4 (на рис. 384 они отмечены А В С Р Е и О Рис.
388. Рис. 387. 1! и 111). Затем берем (Р, 6). Следующим мы должны были бы выбрать (С, 6), но его добавление приводит к циклу. Поэтому переходим к (В, ~Э) и т. д. Результат приведен на рис. 383. Значение минимального дерева: 3+4+4+5+7+8=3!. (58.6) Действуя по двойственному методу, мы должны искл|очать ребра в следующем порядке: (О, Е), (В, Е), (А, Е), (А, Е), 353 (А, О), (С, Е), (К Г), (Е, Г), (КВ), (А, С), (С, Е), (С, 6), как показано на рис. 386 и 386.
На рис. 387 и 388 представлено максимальное дерево того же графа. Его значение 13+ 12+ 11+ 10 + 9+ 9 = 64. (68.7) УПРАЖНЕНИЯ 58А. Указать пути с максимальным значением из корня з до висячих вершин прадерева (закон композиции — сложение) . М 1 ! шз 58Б.
То же, что и в упражнении 58А, но закон композиции — умножение. 58В. Для прадерева в упражнении 58А найти 2-максимальные пути от корня до висячих вершин. 58Г. Простым перечислением найти все классы й-оптнмальных путей для прадерева из упражнения 58А. 58Д. Найти минимальные деревья, являющиеся частичными графамн для следующих графов: 1 2 3 4 б 8 7 8 9 1О л'в с п к р а н 10 58Е. Найти максимальные деревья для графов из упражнения 58Д. 854 5 59. Задачи о временнбм упорядочении Для некоторых задач оптимизации, имеющих комбинаторный характер, подход с помощью теории графов не представляется наиболее естественным. Таковы часто встречающиеся задачи о временнбм упорядочении '). Рассмотрим следующую задачу. Пусть и изделий Рь Рм ...
..., Р„ должны последовательно проходить обработку на станках М, и Мз, причем станок в каждый момент времени может обрабатывать одно изделие. Продолжительность обработки изделия Рз станком М; пусть задается матрицей ))тг)~), 1 = 1, 2; 1 ! Рз Р Рз Ра Рз Ра П~~ ! ', Рз 1 Рг Рк Ря Рк Р« ггк !() 1 Рис. 389. = 1, 2, ..., и.
Требуется минимизировать время, в течение которого станок остается незанятым; задача иногда формулируется как требование минимизировать общее время обработки изделий, включающее время работы и время простоя ставка Мя На рис. 389 схематически показан случай обработки шести изделий двумя станками. Время обработки каждого из изделий дается белым прямоугольником, время простоя — заштрихованными прямоугольниками. Можно обобщить задачу на случай п изделий и гп станков.
При пг ) 2 минимизирование общего времени обработки и минимизирование времени простоя станков — задачи, вообще говоря, различные. Известен алгоритм для случая т = 2 и, с одним ограничением, для гп 3. Это — алгоритм Джонсона; можно также использовать метод ветвления и ограничения з). В общем случае можно применять эвристические методы'). Алгоритм Джонсона. Случай двух станков. Сначала сформулируем алгоритм и дадим пример его использования, а затем уже приведем обоснование алгоритма. 1) Выберем в матрице )~тг1~) наименьший элемент тн. 2) Если этот элемент находится в первой строке, то начинаем с изделия Р), если во второй, то заканчиваем изделием Рь ') В литературе на английском языке употребляется термин «заначи о составлении расписания» («Ясьег(ндпя ргоЫегпз»). ') См.
Игн ел и С кр ей лж (С. !к па !1, Ь. 9 с Ь г а Ке), Лрр1!сацоп о( нйе Вгапсь апг( Воняй Ме!Ьод 1о зогпе Г1оя -зьор зсьедп!(пи ргоЫепгз, 3 О. К. Б. А. 13, № 3 (1966), 400 — 412 ') Д ж и р (Цг. Б. О е г е), Ненпз((ся !п Лоь.зьор зсйег(н1)пв, Манан. 5с(епсе 13, № 3 (!966), 167 — 190, 3) Рассматриваем все изделия, исключая Р,, и действуем, как указано в 1) и 2). Поступаем так, пока не исчерпаем все Рь)=1,2,...,п. П р и м е р. Рассмотрим следующую матрицу 11тмП: (59. 1) 3 8 б 7 3 5 4 2 Наименьший элемент матрицы (59.1) есть т22 = 8. Он находится во второй строке, поэтому процесс надо заканчивать обработкой изделия Р,.
Затем идет элемент т24 = 1О, следовательно, Рис 390, предпоследним нужно обрабатывать изделие Р,. Далее, тзз=11, поэтому перед Р4 должно проходить обработку изделие Рм Так Рис. 391. как затем тм = тзи = 12, то начинать нужно с Р„а Р, обрабатывать перед Рз Точно так же определяется порядок прохождения остальных изделий, Результат представлен на рис. 390. На рис. 391 представлен результат другого упорядочения (всего их 8! = 40320): Обоснование алгоритма. Пусть Т вЂ” общее время, которое проходит с начала обработки первого изделия на станке М, и до конца обработки последнего изделия на станке Мз. Фиксируем некоторый порядок прохождения изделий(Р7Р Р7Р ...
...,Р7,..., Р7„). Пусть Хз — время простоя второго станка Ма 356 после окончания обработки Р; , и до начала лием Р; . Тогда 'Р' Ю з т=УВ! +ХХг, где В! = тг! Так как Вг, г=!, 2...,, п, известны, то для работы с изде- (59,2) (59.3) минимизации Т Рис. 392. достаточно найти минимум ~ Х! . Обозначим также с=! А! =тгг, г=1, 2, ..., и. г с Очевидно, что (рис. 392) (59. 4) Аналогично у з г г Х! = и!ах Я А! — ~х", В! — ~ч"„Х,, 0 (59.9) з с с у з г гпах~~~з А, — ~ В;, с=! ! з =игах Я А,— ьх,) Х В! Х Аг,— Вгп Аг, .
(59.10) ,=! г'с ! З5"! з Х Хг,= Х г, = Аг„ (59.5) Аг, + Ап — Вп — Хг„если Ал + А; ) Вг, -1- Хгв Следовательно, Хп= игах(Аг, + Аг,— Вг, — Хг„0) = / г ! ! = игах( Х Аг, — ~ Вг, — ~ Хг, О, (59,у) с=! ' с=! Для суммы Хг, + Хл получаем Хп+ Хп — — Хл+ игах(Ап+ А!.— Вл — Хг„0) = = игах(Аг, + Аг,— Вг„Хг,) =игах(Аь+ Ап — Вг„Аг,) = / г ! = игах ~ ~ А! — ~ Вг, Аг, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
