Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 60
Текст из файла (страница 60)
для всех )ФЕ 3(г Гл. 12. Осшоаныг деревья и матроида а) Покажите, что клетки Дирихле для множества Р являются выпуклымн миогоугольными областями (некоторые из них неограниченны), покрывающими всю плоскость и пересекающимися только по границам. б) Найдите клетки Дирихле для приведенного ниже множества точек Р.
° ° ° ° в) Покажите, что клетка Дирихле точки р ограничена тогда и тельно тогда. когда ру — выпуклая комбинация трех неколлинеарных гочек из Р. 5. Две точки Рп ру~ Р называются соседями по Лирикле, если пересечение их клеток Дирихле не пусто и отлично от единственной точки. Графом Дирихле для множества Р называется граф 0?э=(Р, егз), где егз=((рг, рз»: рг и рг — соседи по Дирихле».
а) Говоря неформально, граф планарен, если его можно нарисовать иа плоскости так, чтобы никакие два ребра не вересенались Покажите, что граф Дирихле для любого множества точек Р планарен. Можно показать, что если граф (г', Е) связен и плвнарен, то (Е( ~3~ р( — 6 при ) )г)>3, б*) Донажите, что граф Дирихле для множества, содержасцего л точек, можно построить за время 0(п!ой и). в) Покажите, что МОД для множества точек Р с расстояниями г(г? является подграфом графа Днрнхле множества Р.
Выведите отсюда, что МОД длн множества Р может быть вычислено за время 0(п )ой л). г) Приведите пример с шестью точками, показывающий, что кратчайшее лиросочетание для множества точек не является подграфом графа Дирихле. д*) Является ли кратчайший обход в ЗК для лгножесгва точек нодграфолг графа Дирихле? 8. Пусть Р— множество точек на плоскости. Покажите, что никакие два ребра из МОД для Р (относительно г(0) не пересекаются, если их представить соответствующими отрезками на плоскости. 7.
Пусть Р— множество точен Покажите, что существует МОД для Р, в котором степени всех вершин не превосходят 5. 8. Задачи о бродямм торгозаа (ЗБТ) совпадает с ЗК, за исключением того что торговец может начать свой путь в любом месте и не обязан вернуться в исходный город после обхода всех городов. а) Покажите, как за полиномиальное время преобразовать любую индивиду. альную ЗБТ в эквивалентную индивидуальную ЗК. б) Покажите, как за полиномиальное время преобразовать любую индивидуальную ЗК в эквивалентную индивидуальную ЗБТ.
(Под словом зквизаленглную мы имеем в виду, что оптимальный обход в одной задаче легко получается из оп. тимального обхода в другой.) 9. Какие из следующих задач, по существу, не изменяются при переходе от задачи минимизации к задаче максимизации? Почему? а) ЗК. б) Кратчайший путь из з в в) Полное паросочетание минимального веса. г) МОД. !О (задача о паросочетании с весами вершин). Для данных графа 0=(г', Е) и весов ш: )г -ь 2" иа вершинах графа 0 требуется найти паросочетание М в тра. 313 Задами фе б, максимизирующее ем и(о), где сумма берется повеем вершинам а, инциденгным некоторому ребру из М. Покажите, что жадный алгоритм решает зту задачу: а) непосредственными рассуждениями; б) показав, что определенная система независимости ()?; а)2) уловлетворвет свойству 2 пз теоремы 12.5; в) показав, что ()», едс) удовлетворяет свойству 3 из теоремы 12.5; г) уяснив, что представляют собой циклы, оболочки н функция ранга в ()», а)2).
(Прпл»счаиис мзтронды, аналогичные (р,аФ), называются матроидами пауосочс»пинии.) !1. Пусть Š— конечное множество, С вЂ”. (5,, ..., 5м) — семейство подмножеств множества Е, и пусть Т =-(с», ..., ег) с: — Е, Будем говорить, что Т- трансасусас»ь семенствз С, если существуют разжшные целые числа 1 (1), ... ..., 1(1), такие, что сгц5 «», ~ — -1, ..., 1. Пусть 3 множество исех транс- версалей в Е. Покажите, что Мс.—. (Е, 3) — матронд. Что представляют собой циклы, оболочки и функция ранга в Мс? 12. Покажите, что каждый из следующих матроидов М является матричным, полобрав поле К, размерность г( и вектор 1. (с) ~Ки для каждого элемента.с из Е. а) Графический матроид Мсу б) Матроид разбиения Мгт.
в) Матроид трансверсалей Мс. 13. Рассмотрим принеденную ниже систему, состоящую из семи точек и семи линий (шести отрезков и окружности). Определим систему нещвиснмости М =(Е, 3), где Е=(а, а, с, »(, е, г', и) и полмножество 5 из Е входит в 3 тогда и только тогда, котла выполняется одно из следующих условий. (») 151 < 3. (й) 151= — 3, н никакая из семи линий не проходит через все три точки, входящие в 5.
а) Покажите, что М вЂ” м»гранд. Что представляют собой циклы, оболочки и функция ранга в М? б') Пок жите, что М нс является матричным матроилом, т. е, не существует системы из семи векторов над произвольным полем, такая. чтобы независимые множества имели в точности такую же структуру, как данная система 5. 14. Пусть М =(Е, 7) — ммтроид, и пусть (р» — множество его циклов а) Покажите следующие утверм»денни. (») Если С,, С,цй и С, »= С,, то С».= С».
(й) Если С», С»цй, «цС»ПСг н с'цС» — С», то найлетсяС»цв, такое, что Сассй(С»()С,) — с и е'~С». б) К; к выглядит интерпретация утверждения (й) аля графических матроидов? »паля матричных матроидов? в*) Локажите обратное утверждение, т, е. что если система (Е, м) удовлетворяет (1) и (й), то (Е, 3) — матроид, где Э =-(1»:.Е: С сй( для всех Сц(а»). >"л. 72. Остозные дереаьв и матроиды зы 15. Даны конечное множество Е и семейство С=(5„5„..., 5„под.
множеств множества Е. Спрашивается, существует лн такое множество Нс=Е, что ) Н(==а и ( НП5;(=1 для > =1, ..., и. Сформулируйте эту задачу как задачу о пересечении мзтроида грансверсалей и матроида разбиения. Затем решите ее наиболее простым способом. 1О. Даны грэй 0=(У, Е) и множество I с:.)>. Требуется определить, существует ли такое остовное дерево Т в О, чтобы все вершины из Е бьии листьями дерева Т. Сформулируйте зту задачу как задачу о пересечении грзфнческого матрондз и мзтроида разбиения Затем решите ее наиболее простым способом, 17. Найдите максимальное пересечение двух графических матроидов, пред.
ставленных па рис. 12.16. !8ч (задача о разбиении относительно мзтроида). Даны матроид М =.(Е, О) и множество 539 Е, и требуется выяснить, можно ли разбить 5 иа два множества 1„)э~3 Покажите, что эга задача эквивалентна задаче о пересечении м>грандов. 19. Покажите, что задача о матроиде с соответствием (см. равд. !2.6.2) для матроидов разбиения совпадает с задачей о н.>росочетании. 20. Покажите, что задача о матроиде с соответствием для графических мзтроидов является обобщением двух задач. задачи о пересечении двух графических матрондов и задачи о паросочетании.
(аким>ние. возможно, вам придется использовать мульлшграфы, т. е. графы, в которых допускаются повторения ребер.) 21. Пусть М =(Е, 3) — матроид, и пусть хз — множество базисов мзтроида М. Пусть 3 .=(( г Е: Š— ! .:Л В для некотг>ро> о В ~Я. Покажите, что М =-(Е, У) — мзтроид. (Нгшмечание, М называется»азраилом, )аайст. агиным к М.) 22.
Пусть даны граф 0 =(у, Е), вершина гц. у и целое число з, и требуется определить, существует ли остовное .дерево в 0, в котором степень вершины о не превосходит й. Покажите, что это задача о пересечении мзтроидов. Кеммектаркк м ссылки Похоже, что самый ранний источник >влачи МОД ие известен Одним из наиболее ранних является >ехословацкяя статья (Во) Вогичйз, О Оп а Мппша! РгоЫеш, Ргасе й!огач>зйе Ргебочебесйе Зро!есгоз(1, 3 (1926) Алгоритм, представленный иа рис. !2цй обычно приписывается Приму (Рг) Ргцп К С. Зног!ез1 СоппесНоп Ке!шогйз апб югпе Оепега!>за!>опз, ВЗТ3, 36 (1957), 1369 — !401.
(Имеется перевод: Прим Р К. Кратчайшие связывающие сети и некоторые обобщения.— В сбл Киберн. сб, вып. 2 (старая серия).— Мл Мир, 1961, с. 95 — 107.) (О!) ОВЦз!га Е. >>>. А Г(о1е оп Тыо РгоЫегпз !и Соппех>оп ш!Ра Огарйз, 1(ишемзсйе Мариета(йн ! (1959), 269 — 271 Алгоритм, приведенный иа рис. !2.5, описан в книге (ВЯ Вегйе С„ОПошйа-Ноип А. Ргойгз.папий, Оашез апд Тгапзрог1а1>оп Ме1- ч>огйз )(еч> Уог(г (ойп %!!еу Е 5опь !пс., 1965 Алгоритм с оценкой 0((Е!(ой !ой! У!). описанный в задаче 2, взят из работы (Уа) уао А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
