Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 73
Текст из файла (страница 73)
Ребра графа 6 соединяют все пары совместимых наборов значений ис~инности. Положим й=т. Утверждается, что в построенном выше графе 6 имеется клика размера й тогда и только тогда, когда формула г" выполнима. Дей- ствительно, предположим, что в 6 имеется клика размера й. Так как й=-т и нет ребер, соединяющих две вершины в одном и том же столбце (два различных частичных набора значений истинности, определенных на одних и тех же переменных, заведомодолжны быть несовместимы), то эта клика содержит по одной вершине из каждого из т столбцов. Поскольку все эти частичные наборы значений истин- ности попарно совместимы, то все они получаются из одного и того же полного набора значений истинности 1 (в примере на рис. 15.4 1=-1011).
Этот набор 1должен выполнять все дизъюикты из Р, так как для каждого дизъюнкта в соответствующем столбце единствен. ный частичный набор значений истинности, обращающий этот дизь- юнкт в ложь, опущен. Следовательно, 1 выполняет формулу Е. Для доказательства обратного утверждения предположим, что "существует набор значений истинности 1, выполняющий Е; тогда ограничение этого набора на переменные, появляющиеся в произ- вольном дизъюнкте, должно быть существующей вершиной в столб- це, соответствующем этому дизъюнкту.
Так как эти частичные на. боры являются ограничениями одного и того же набора значений . истинности, они попарно совместимы и, следовательно, образуют клику размера 1г. Гл. И, НР.поппыа задачи Таким образом, мы преобразовали задачу 3-ВЫПОЛНИМОСТЬ в задачу КЛЙКА, и это построение можно выполнить за полиномиальное время; следовательно, задача КЛИКА Гт'Р-полна, (х! +х~ +х1) (х~ ! х~ ! х~) ~ !и!+аз+к!) (т~ +х1 4х4) Оооа 0 О О а' оноо аооо ИОО! ОИО! О01 ! 00!И 1и! 1 О!аа а!11 — — 0110 1ооа а)ОО 1аоо 1ОО 1 1О! 1 10!а а'101 О 111 1 1 0 ~! ! 10Н а!10 1а10 111~1 1Н11 а! 11 Рис.
15.4. !ал), Драгие ИР-полные эадачи: КЛИКА и ЗК 373 В теории графов имеются две задачи, очень тесно связанные с задачей КЛИКА. ВЕРШИННОЕ ПОКРЫТИЕ Для данных графа 6 и целого числа й выяснить, существует ли такое множество С, содержащее (г вершин, что любое ребро из 6 инцидентно по крайней мере одной вершине из С.
НЕЗАВИСИМОЕ МНОЖЕСТВО Для данных графа 6 и целого числа (г выяснить, существует ли такое множество (, содержащее й вершин, что никакие две вершины из ! не связаны ребром. Лемма (б.4. Для графа 6=-(У, Е) и подмножества 5 множества У следующие утверждения эквивалентны: а) 5 — клика в 6; б) 5 — независимое множество в графе 6, дополнении графи 6, в) У вЂ” 5 есть вершинное покрытие в 6. Доказательство (см. рис. !б.б). Если 5 — клики и ~', о~ и ь и любыми двумя вершинами из 5 имеезся ребро в 6; поэтому в 6 между любыми двумя вершинами из 5 нет ребра, т.
е. 5 независимо в 6. Далее, если 5 независимо в 6, то у каждого ребра из 6 по крайней мере одна вершина должна лежать вне 5; следовательно, У вЂ” 5 есть вершинное покрытие в 6. Наконец, если У вЂ” 5 вершинное покрытие в 6, то это означает, что у любого ребра, отсутствующего в 6, не могут обе вершины содержаться в 5; следовательно, 5 — клика в6. П Следствие. Задачи НЕЗАВИСИМОЕ МНОЖЕСТВО и ВЕРИ!ИННОЕ ПОКРЫТИЕ НР-полны. Доказательство. Очевидно, в 6 имеется клика размера (г тогда и только тогда, когда в О имеется независимое множество мощности й, и тогда и только тогда, когда в 6 имеется вершинное покрытие мощности ~У! — и. Следовательно, все три задачи полипомиально преобразуются друг в друга.
() Докажем теперь, что одна интересная задача о расписании (вспомните пример 13.2) НР-полна. В этой задаче требуется построить расписание заданий с одинаковым, скажем единичным, временем выполнения на некотором числе идентичных процессоров при наличии некоторых ограничений предшествования, определяющих, что некоторые задания могут выполняться только тогда, когда уже выполнены некоторые другие задания.
Гл. 1Б. Ир.полиси ладони (а) (б) (в) Рис. 15.5. а) Независимое множество в 6. 6) Вершинное покрытие в 6. в) Клика в С. МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ даны множество заданий де= (1,, „,)„), ориентированный ациклический граф Р=(7, А) (частичный порядок предшествования), целое число т (число машин) и целое число Т (директивный срок).
Спрашивается, существует ли функция Я (расписанией отображающая Я в (1, 2, ..., Т), такая, что выполняются следующие условия: 1 !РН с(1~)=1)~Кт дпя ВСЕХ (~Т; 2. Если (1о,)1) ЕА, то 3(/,)<Я() ), 1б.б. другие ИР-палил!в эадачи: КЛИКА и ЗК 376 Пример 15.9. Рассмотрим индивидуальную задачу МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ, представленную на рис. 15.5(а). г!г ~!! Т 5 лг (а) Время ! 2 3 4 3 Машина 1 Машина 2 Машина 3 (б) Рис.
!6.6. На рис. !5.5(б) схематически представлено допустимое расписа!1ие 3 П Теорема 15.5. Задача МНОГОПРОЦЕССОРНОЕ РАСПИСА Н ИЕ '!еР-полна. Доказательство. Эта задача лежит в ИР, поскольку, если г ествует допустимое расписание, оно может быть предъявлено довольно легко проверено на допустимость. Преобразуем за. з76 Га 1д. 'лГР.иолные задачи дачу КЛИКА в задачу МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ.
Пусть даны произвольный граф 6=((л, Е) и целое число л. Построим множество работ 7, частичный порядок Р=(у', А) и целые числа т и Т, такие, что допустимое расписание для У существует тогда н только тогда, когда в 6 имеется клика размера й. Будем считать, что в 6 нет изолированных вершин; это не приводит к потере общности, так как удаление изолированных вершин не влияет на размер клик. Положим дл=(л() Е() () ВВСЦ0, где В, С и 0 — непустые непересекающиеся множества В = (Ь„ ..., Ь, а 1 ), С = (с„ ..., с~ с ~1 и 0 = (й„ ..., й~ о ~ ), такие, что (В(,1С( и 10! удовлетворяют условиям~ 1) гл=й+~В~1=( )+~и! — А+~С~=!Е! — (" ) +(0~ и 2) пйп (! В), (С ), ~ 0!)=-1.
Нетрудно понять, что такие мощности существуют; лг определяется из (!); Т возьмем равным 3. Для построения Р=ф, А) вначале отнесем к А всевозможные дуги вида (Ь„сг) н (сь с(,). Затем добавим к А дуги (о, е) для всех о4 1', г Е Е, таких, что е пнцпдентно ш Этим завершается построение индивидуальной задачи МНОГОПРОЦЕССОРНОЕ РАСПИСАНИЕ. Описанный переход проиллюстрирован на рис. 15.7(а) и (б). Докажем теперь, что допустимое расписание для у' при данных А, т н Т существует тогда н только тогда, когда в 6 имеется клика размера й. Предположим, что существует допустимое расписание 5. Так как Т=3 и все работы нз В должны выполняться раньше работ из С, а работы нз С раньше, чем работы из О, то, очевидно, 5(Ь,)=1, 5(с,)=-2 и 5(г(;)=3 для всех Е Кроме того, замечаем, что 1дл1= =Т.т; следовательно, все гп машин должны вйполнять некоторую работу в течение всех трех периодов времени. В последний период, кроме работ й, могут выполняться только т — 10|=)Е~ — (~з) ра.
бот, соответствующих ребрам. Это следует из того, что если работа, соответствующая вершине, выполняется в третьем периоде, то работы, соответствующие ребрам, инцидентным этой вершине, не могут выполняться до окончания третьего периода; здесь мы используем тот факт, что в 6 нет изолированных вершин. Но тогда это расписание не было бы допустимым расписанием с Т=3, как предпо. лагается.
В результате заключаем, что остальные (з) работ, соответствующих ребрам, должны выполняться во втором периоде, а работы, соответствующие вершинам, выполняются в первом периоде (хч — )В 1=А из них) и во втором периоде, При этом й вершин, соответствующих работам, выполняемым в первом периоде, должны включать в себя концы всех (г) ребер, соответствующих работам, выполняемым во втором периоде. Однако л вершин могут включать в себя все концы (2) ребер только в том случае, если эти и вершин образуют клику.
Следовательно, из существования допу. )о.6. другие ИР-волнам эаоанис КЛИКА и ЗК 377 н~ е, иг )снЗ (а) п~ пг и, на т З,даню 1В1-2,1(1- 1,101 * О 1 ег еа с, д, (б) Время 1 ' 3 Машина 1 Машина 2 Машина 3 Машина 4 Машина 5 (В) Рнс. 15.7. а) Гра$6. о) Отношение предшествованнн Р. в) г)опустнное расписание, соответствующее вершинному покрытнн) (и,, иа, оа), стимого расписания Я вытекает существование клики С= (ш о(п)= = !) размера )г. Обратно, если в 0 имеется клика С размера)г, то допустимое рас писание 5 могкио построить по следующим правилам: Я(Ь;1 — -1, Я(с~)=2, Я(й;)=3 для всех 1; Я(о)=1, если пЕС, и 5(о)=2 в про- Гл. тз.
КР-полные эадачи 878 Теорема 1б.б. Задача ГАМИЛЬТОНОВ ЦИКЛ )УР-полна. Доказательство. Мы знаем, что задача ГАМИЛЬТОНОВ ЦИКЛ входит в л7Р; покажем, что задача 3-ВЫПОЛНИМОСТЬ полиномиально преобразуется в задачу ГАМИЛЬТОНОВ ЦИКЛ. Пусть и' (а) (в) (б) н' (г) Рис. 15.8 дана булева формула Р, состоящая из ле дизъюнктов С„..., С„и содержащая и переменных х„..., х„. Построим такой граф 0 ()е, Е), что гамильтонов цикл в О имеется тогда и только тогда, когда Р выполнима. Наша конструкция включает в себя построение ком- тнвном случае; 5((о, и!)=2, если о, и б С, и 5(!о, и)) 3 в противном случае, Этот переход проиллюстрирован на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
