Упражнения 1.

Решите, истинно или ложно следующее утверждение. Если оно истинно, при- ведите краткое объяснение, а если ложно — контрпример.

Пусть G — произвольный связный ненаправленный граф с различающимися стоимостями c(e) всех ребер e.

Предположим, e* — ребро с минимальной сто- имостью в G, то есть c(e*) < c(e) для каждого ребра e ф e*. Тогда существует минимальное остовное дерево T графа G, содержащее ребро e*

2. Решите, истинно или ложно каждое из следующих двух утверждений. Если ут- верждение истинно, приведите краткое объяснение, а если ложно — контрпример.

(a) Предположим, имеется экземпляр задачи нахождения минимального остовного дерева для графа G, все стоимости ребер которого положительны и различны. Пусть Т — минимальное остовное дерево для этого экземпляра. Стоимость каждого ребра ce заменяется его квадратом t'k"; так образуется новый экземпляр задачи с тем же графом, но другими стоимостями. Истинно или ложно? Дерево T должно остаться минимальным остовным деревом для нового экземпляра задачи.

(b) Предположим, имеется экземпляр задачи нахождения кратчайшего пути s-t в направленном графе G. Все стоимости ребер положительны и раз- личны. Пусть Р — путь s-t для этого экземпляра с минимальной стоимостью. Стоимость каждого ребра ce заменяется его квадратом t£; так образуется новый экземпляр задачи с тем же графом, но другими стоимостями.

Истинно или ложно? Путь P должен остаться путем s-t c минимальной стоимо- стью для нового экземпляра задачи.

3. Вы консультируете транспортную компанию, которая перевозит грузы между Нью-Йорком и Бостоном. Объем перевозок достаточно велик, чтобы ежедневно между двумя городами отправлялось несколько грузовиков. У каждого грузови- ка имеется предельный вес перевозимых грузов W. Грузы прибывают на склад в Нью-Йорке один за другим, каждый пакет i имеет вес w. Склад невелик, по- этому в любой момент времени на нем может находиться только один грузовик. По действующим в компании правилам грузы отправляются в порядке их по- ступления, чтобы покупатели не сердились, если груз, отправленный позднее их груза, доберется до Бостона раньше. Сейчас в компании используется простой жадный алгоритм упаковки: грузы упаковываются в порядке поступления, а если следующий груз не помещается, то грузовик отправляется без него.

Но владельцы компании подозревают, что они используют слишком много грузовиков, и хотят повысить эффективность. Нельзя ли сократить количество машин, отправляя незаполненный грузовик, чтобы следующие грузовики за- полнялись более эффективно?

Докажите, что для заданного набора грузов с заданными весами жадный алгоритм, используемый в настоящее время, действительно минимизирует количество используемых грузовиков. Доказательство должно строиться по

тому же образцу, что и приведенное выше доказательство для задачи интер- вального планирования: оптимальность жадного алгоритма устанавливается определением метрики, в соответствии с которой он «опережает» все осталь- ные решения.

4. Ваши друзья занялись расширяющейся областью анализа временных рядов. Це- лью анализа является поиск закономерностей в последовательностях событий, происходящих во времени. Одним из источников таких данных с естественным упорядочением по времени могут служить покупки на биржах (что и когда покупается). Ваши друзья хотят иметь эффективный механизм обнаружения некоторых «закономерностей» в заданной последовательности S таких собы- тий: например, они хотят знать, происходят ли в последовательности S четыре события

купить Yahoo, купить eBay, купить Yahoo, купить Oracle в такой очередности (но не обязательно подряд).

Они начинают с набора всех возможных событий (например, возможных транзакций) и последовательности S из n таких событий. Заданное событие может встречаться в S несколько раз (например, акции Yahoo могут покупаться многократно в одной последовательности S). Последовательность S' называется подпоследовательностью S, если из S возможно удалить некоторые события так, чтобы оставшиеся события (с соблюдением порядка) были равны последова- тельности S'. Так, приведенная последовательность из четырех событий явля- ется подпоследовательностью для последовательности

купить Amazon, купить Yahoo, купить eBay, купить Yahoo, купить Yahoo, купить Oracle

Ваши друзья хотят вводить короткие последовательности и быстро узнавать, являются ли они подпоследовательностями S. Поставлена следующая задача: предложите алгоритм, который получает две последовательности событий — S' длины m и S длины n (в обеих последовательностях события могут повторяться) и за время O(m + n) решает, является ли S' подпоследовательностью S.

5. Представьте длинную, спокойную проселочную дорогу, на которой редко встре- чаются отдельные дома. (Будем считать, что дорога представляет собой отрезок прямой с двумя концами, восточным и западным.) Также предположим, что несмотря на пасторальную обстановку, жители этих домов активно пользуются мобильными телефонами. Требуется разместить базовые станции сотовой связи вдоль дороги так, чтобы любой дом находился на расстоянии не более четырех миль от одной из базовых станций.

Предложите эффективный алгоритм для достижения этой цели с минимальным количеством базовых станций.

6. Ваш друг работает в детском лагере и отвечает за проведение мероприятий в группе подростков. В его планы входит проведение мини-триатлона: каждый участник должен проплыть 20 дорожек в бассейне, проехать на велосипеде 10 миль, а потом пробежать 3 мили. Участники будут выходить на дистанцию поочередно, по следующему правилу: в любой момент времени бассейн будет использоваться только одним участником. Другими словами, первый участник проплывает 20 дорожек, выходит и садится на велосипед. Как только он по- кидает бассейн, второй участник начинает проплывать свои 20 дорожек; когда он выходит из бассейна, заплыв начинает третий участник... и т. д.

У каждого участника имеется прогнозируемое время плавания (время, за кото- рое он должен проплыть 20 дорожек), прогнозируемое время проезда (время, за которое он должен проехать 10 миль) и прогнозируемое время бега (время, за которое он пробежит 3 мили). Ваш друг хочет спланировать расписание триатлона: порядок, в котором участники будут выходить на дистанцию. За- вершающим временем расписания будет называться самое меньшее время, за которое все участники пройдут все три стадии триатлона, при условии, что они точно выдержат спрогнозированное время во всех трех стадиях (еще раз: участ- ники могут ехать на велосипеде и бежать одновременно, но в бассейне в любой момент времени может находиться только один человек). Как выглядит опти- мальный порядок выхода участников, чтобы соревнования закончились как можно раньше? А точнее, предложите эффективный алгоритм, который строит расписание с минимальным завершающим временем.

7. Невероятно популярная испаноязычная поисковая система Goog проводит огромный объем вычислений при каждом пересчете индекса. К счастью, в рас- поряжении компании имеется один суперкомпьютер с практически неограни- ченным запасом мощных рабочих станций.

Вычисления разбиты на n заданий Jv J2, ..., J , которые могут выполняться полностью независимо друг от друга. Каждое задание состоит из двух фаз: сначала оно проходит предварительную обработку на суперкомпьютере, а за- тем завершается на одной из рабочих станций. Допустим, обработка задания J. требует р . секунд на суперкомпьютере, а затем f секунд на рабочей станции. На площадке доступны как минимум n рабочих станций, поэтому завершаю- щая фаза обработки всех заданий может проходить параллельно — все задания будут выполняться одновременно. Однако суперкомпьютер может работать только с одним заданием, поэтому администратор должен определить порядок передачи заданий суперкомпьютеру. Как только первое задание в этом порядке будет обработано на суперкомпьютере, оно передается на рабочую станцию для завершения; после обработки на суперкомпьютере второе задание передается на рабочую станцию независимо от того, завершилось первое задание или нет (так как рабочие станции работают параллельно), и т. д.

Допустим, расписание представляет собой упорядоченный список заданий для суперкомпьютера, а время завершения расписания определяется самым ранним временем завершения всех заданий на рабочих станциях. Очень важно свести к минимуму эту характеристику, так как она определяет, насколько быстро El Goog сможет построить новый индекс.

Предложите алгоритм с полиномиальным временем, который находит распи- сание с минимальным временем завершения.

8. Имеется связный граф G, стоимости всех ребер которого различны. Докажите, что в G существует уникальное минимальное остовное дерево.

9. Одна из практических целей для задачи нахождения минимального остовного дерева — построение остовной сети для множества узлов с минимальной общей стоимостью. Однако сейчас нас интересует другой тип целей: проектирование остовной сети, в которой максимальная стоимость ребра настолько низка, на- сколько это возможно.

Говоря конкретнее, пусть G = (V, E) — связный граф с n вершинами, m ребрами и положительными стоимостями ребер (предполагается, что все стоимости различны). Пусть T = (V, E') — остовное дерево G; критическим ребром дерева T будет называться ребро из T с наибольшей стоимостью.

Остовное дерево T графа G называется минимально-критическим остовным де- ревом, если не существует остовного дерева T' графа G с меньшей стоимостью критичного ребра.

(a) Является ли каждое минимально-критичное дерево графа G минималь- ным остовным деревом G? Докажите или приведите контрпример.

(b) Является ли каждое минимальное остовное дерево графа G минимально- критичным деревом графа G? Докажите или приведите контрпример.

10. Пусть G = (V, E) — (ненаправленный) граф со стоимостями ce > 0 ребер e E.

Допустим, вам известно минимальное остовное дерево T для G. Предположим, что в G добавляется новое ребро, соединяющее два узла v, w V со стоимостью с.

(a) Предложите эффективный алгоритм проверки того, остается ли T остов- ным деревом минимальной стоимости при добавлении нового ребра в G (но не в дерево T). Алгоритм должен выполняться за время O(E|). Удастся ли вам заставить его выполняться за время O(|V |)? Отметьте все предположения, которые вам пришлось сделать относительно структуры данных, использу- емой для представления дерева T и графа G.

(b) Допустим, T уже не является минимальным остовным деревом. Пред- ложите алгоритм с линейным временем (O(|E|)) для замены T новым мини- мальным остовным деревом.

11. Предположим, имеется связный граф G = (V, E), ребро e которого имело стои- мость сВ предыдущей задаче было показано, что при различных стоимостях ребер G содержит уникальное минимальное остовное дерево. Но если в графе имеются ребра с одинаковой стоимостью, G может содержать несколько мини- мальных остовных деревьев. Вопрос: можно ли заставить алгоритм Крускала найти все минимальные остовные деревья графа G?

Вспомните, что алгоритм Крускала сортирует ребра в порядке увеличения стоимости, а затем жадно обрабатывает ребра одно за другим, добавляя ребро e при условии, что оно не приводит к образованию цикла. Когда некоторые ребра имеют одинаковую стоимость, выражение «в порядке увеличения сто- имости» необходимо задать более тщательно: упорядочение ребер называется действительным, если соответствующая последовательность стоимостей ребер
не уменьшается. Действительным выполнением алгоритма Крускала будет на- зываться выполнение, начинающее с действительного упорядочения ребер G.

Для любого графа G и любого минимального остовного дерева T графа G су- ществует ли действительное выполнение алгоритма Крускала для G, которое выдает T как результат? Приведите доказательство или контрпример.

12. Предположим, имеется n видеопотоков, которые необходимо передать один за другим по каналу связи. Поток i состоит из b битов, которые должны переда- ваться с постоянной скоростью за период t. секунд. Два потока не могут пере- даваться одновременно, поэтому необходимо составить расписание потоков, то есть порядок их отправки. Какой бы порядок ни был выбран, задержек между концом одного и началом следующего потока быть не должно. Предположим, расписание начинается во время 0 (а следовательно, завершается во время

независимо от выбранного порядка). Предполагается, что все значения

b и ti — положительные целые числа.

Владелец канала не хочет, чтобы один пользователь создавал слишком большую нагрузку на канал, поэтому он устанавливает следующее ограничение с фикси- рованным параметром r:

(*) Для каждого натурального числа t > 0 общее количество битов, передава- емых за интервал времени от 0 до t, не может превышать rt.

Обратите внимание: ограничения устанавливаются только для интервалов, на- чинающихся с 0 (но не для любой другой начальной точки).

Расписание называется действительным, если оно удовлетворяет ограниче- нию (*), установленному для канала.

Задача. Для заданного множества из n потоков, каждый из которых задается количеством битов bi и продолжительностью ti, а также для параметра канала r определите, существует ли действительное расписание.

Пример. Предположим, имеются n = 3 потока с параметрами (b1, t1) = (2000, 1), (b2, t2) = (6000, 2), (b3, t3) = (2000, 1), а параметр канала r = 5000. В этом случае расписание, передающее потоки в порядке 1, 2, 3, будет действительным, так как ограничение (*) соблюдается:

t = 1: весь первый поток отправлен, 2000 < 5000 · 1 t = 2: отправлена половина второго потока, 2000 + 3000 < 5000 · 2

Аналогичные вычисления проводятся для t = 3 и t = 4.

(a) Рассмотрим следующее утверждение:

Действительное расписание существует в том, и только в том случае, если каждый поток i удовлетворяет условию b. < rt .

Решите, истинно или ложно это утверждение. Предоставьте доказательство или контрпример.

(b) Предложите алгоритм, который получает множество из n потоков, каж- дый из которых задается количеством битов bi и продолжительностью ti,
а также параметр канала r и определяет, существует ли для них действи- тельное расписание. Время выполнения алгоритма должно быть полиноми- альным по n.

13. Небольшая фирма — скажем, копировальный центр с одним большим копиро- вальным аппаратом — сталкивается с проблемой планирования. Каждое утро она получает множество заказов от клиентов. Заказы должны быть выполнены на единственном аппарате в порядке, который устроит большинство клиентов. На выполнение заказа клиента i требуется время t. Пусть при заданном рас- писании (то есть порядке заказов) время завершения заказа i обозначается C. Например, если задание j должно быть выполнено первым, то C = t ; а если за- дание j выполняется сразу же после задания i, то C. = C. + t.. Каждому клиенту i также назначается вес wi, представляющий его важность для фирмы. Настрое- ние клиента i зависит от времени завершения его заказа. Таким образом, фирма стремится упорядочить заказытак, чтобы свести к минимуму взвешенную

сумму времен завершения,

Предложите эффективный алгоритм для решения этой задачи. Алгоритм по- лучает множество из n заказов с временем обработки ti и весом wi для каждого заказа. Требуется упорядочить заказы так, чтобы минимизировать взвешенную

сумму времен завершения

Пример. Предположим, получены два заказа: первый с временем t1=1 и весом w1=10, и второй с временем t2 = 3 и весом w2 = 2. Если заказ 1 будет выполнен первым, то взвешенное время завершения составит 10 · 1 + 2 · 4 = 18, а если начать со второго заказа, то взвешенное время увеличится до 10 · 4 + 2 · 3 = 46.

14. Вы работаете с группой консультантов в области безопасности, которые на- блюдают за работой большой компьютерной системы. Особый интерес вызы- вают процессы с пометкой «системный». Для каждого такого процесса задано начальное и конечное время; в промежутке между этими моментами процесс непрерывно работает; у консультантов имеется список начального и конечного времени для всех системных процессов, запланированных на сегодняшний день.

Консультанты написали программу status_check, которая выполняется не- сколько секунд и сохраняет различную информацию о системных процессах, выполняемых в системе в настоящее время. (В нашей модели каждый вызов status_check относится только к одному конкретному моменту времени.) Кон- сультанты хотели бы запускать программу status_check как можно меньше раз за день, но достаточно для того, чтобы на протяжении выполнения каждого системного процесса P программа была запущена хотя бы один раз.

(a) Предложите эффективный алгоритм, который получает начальное и ко- нечное время для всех системных процессов и находит минимальное мно- жество временных точек для вызова status_check, с которым программа будет вызвана хотя бы один раз на протяжении работы каждого системного процесса P.

(b) Пока вы работали над алгоритмом, консультанты тоже пытались найти подход к решению задачи. «Допустим, нам удастся найти множество из к си- стемных процессов, обладающих тем свойством, что никакие из них никогда не выполняются одновременно. Тогда, очевидно, алгоритм должен вызвать status_check минимум к раз; каждый отдельный вызов status_check сможет обработать только один из таких процессов».

Конечно, это правильно, и в дальнейшем обсуждении возник вопрос: а не дей- ствует ли более сильное правило, своего рода обратное приведенному? Предпо- ложим, к* — наибольшее значение к, позволяющее найти множество из к систем- ных процессов, никакие два из которых никогда не выполняются одновременно. Значит ли это, что должно существовать множество из к* моментов времени для запуска status_check, чтобы хотя бы один вызов случился во время выполнения каждого системного процесса? (Другими словами, не является ли аргумент из предыдущего абзаца единственной причиной, по которой приходится много раз вызывать status_check?) Решите, истинно или ложно это утверждение, и при- ведите доказательство или контрпример.

15. К вам обращается менеджер крупного студенческого объединения. Она руково- дит группой из n студентов, каждый из которых по графику должен отработать одну смену за неделю. Со сменами связаны различные виды работ (помощь в до- ставке пакетов, перезагрузка зависших информационных терминалов и т. д.), но мы можем рассматривать каждую смену как один непрерывный интервал времени. Несколько смен могут проходить одновременно.

Менеджер хочет выбрать подмножество из этих n студентов и сформировать наблюдательный комитет, с которым будет проводить встречи раз в неделю. Комитет будет считаться полным, если у каждого студента, не входящего в ко- митет, смена перекрывается (по крайней мере частично) со сменой студента, входящего в комитет. Таким образом, качество работы каждого студента будет видно по крайней мере одному участнику комитета.

Приведите эффективный алгоритм, который получает расписание из n смен и выдает состав полного наблюдательного комитета с минимальным количе- ством участников.

Пример. Предположим, n = 3 и смены проводятся в следующее время: понедельник 16:00 — понедельник 20:00 понедельник 18:00 — понедельник 22:00 понедельник 21:00 — понедельник 23:00 В этом случае наименьший полный наблюдательный комитет будет состоять только из второго студента, потому что вторая смена перекрывается как с пер- вой, так и с третьей.

16. Консультанты по вопросам финансовой безопасности в настоящее время ра- ботают с клиентом, исследующим потенциальную схему отмывания денег. Проведенные исследования показали, что за последнее время состоялось n сом- нительных операций, каждая из которых была связана с переводом денег на некий счет.

К сожалению, отрывочный характер доказательств означает, что исследователям неизвестен сам счет, суммы переводов и точное время про- ведения операций. Известна лишь приблизительная временная метка каждой операции; из доказательств следует, что операция i состоялась во время t. ± e. с некоторой «погрешностью» e.. (Иначе говоря, операция состоялась где-то в интервале от t.- e. до t. + e,) Не забывайте, что у разных операций могут быть разные погрешности.

Недавно был обнаружен подозрительный банковский счет, который, как предполагается, мог быть использован в преступлении. За последнее время со счетом выполнялись n операций, происходивших во время x1, x2, ..., xn. Что- бы узнать, тот это счет или нет, нужно связать каждое из n событий с одной из n сомнительных операций так, чтобы если событие x. связывается с со- мнительной операцией t., то выполнялось условие |t. - хj < e. (Иначе говоря, клиент хочет знать, можно ли связать события с сомнительными операциями так, чтобы временные расхождения находились в пределах разумной погреш- ности; задача усложняется тем, что заранее неизвестно, какое событие с какой погрешностью должно связываться.)

Предложите эффективный алгоритм, который получает данные и решает, су- ществует ли такая ассоциация. Если возможно, алгоритм должен выполняться за время не более O(n2).

17. Рассмотрим следующую вариацию на тему задачи интервального планиро- вания. Имеется компьютер, который может работать ежедневно по 24 часа в сутки. Пользователи подают заявки на выполнение ежедневных заданий на компьютере. У каждого задания имеется начальное и конечное время; если задание принято на выполнение, оно выполняется каждый день в период между начальным и конечным временем. (Обратите внимание: задания могут начинаться до полуночи и завершаться после полуночи; из-за этого ситуация отличается от той, какую мы видели в задаче интервального планирования.) Получив список из n таких заданий, нужно принять как можно больше заданий (независимо от их длины) с учетом ограничения, согласно которому в любой момент времени на компьютере может выполняться только одно задание. Пред- ложите алгоритм решения этой задачи с временем, полиномиальным по n. Для простоты можно считать, что не существует заданий с одинаковым начальным и конечным временем.

Пример. Получены следующие четыре задания, заданных парами (начало, конец):

(18:00, 6:00), (21:00, 4:00), (3:00, 14:00), (13:00, 19:00)

В оптимальном варианте выбираются два задания (21:00, 4:00) и (13:00, 19:00), которые могут быть запланированы без перекрытия по времени.

18. Ваши друзья собрались в зимний поход к небольшому городку возле канадской границы. Они проанализировали все варианты перемещений и построили на- правленный граф, узлы которого представляют промежуточные пункты, а ре- бра — соединяющие их дороги.

Также известно, что из-за плохой погоды некоторые дороги в этой местно- сти зимой заметает и перемещение по ним может существенно замедлиться. К счастью, имеется отличный сайт с точными прогнозами скорости переме- щения по дорогам; однако эта скорость зависит от времени года. Точнее, сайт отвечает на запросы следующего вида: имеется ребро e = (v, w), соединяющее два пункта v и w; для заданного начального времени t для пункта v сайт воз- вращает значение fe(t) прогнозируемое время прибытия в w. Сайт гарантирует, чтоf (t) > t для всех ребер e и моментов времени t (обратные перемещения во времени невозможны), а fe(t) является монотонно возрастающей функцией t (то есть отправившись в путь позднее, вы не приедете раньше). В остальном функции fe(t) могут быть произвольными. Например, в местах, в которых скорость перемещения не зависит от времени года, fe(t) = t + ie, где ie — время, необходимое для перемещения от начала ребра e к его концу.

Ваши друзья хотят использовать сайт для определения самого быстрого спо- соба перемещения по направленному графу от начальной точки до места на- значения. (Предполагается, что они отправляются во время 0, а все прогнозы сайта полностью верны.) Предложите алгоритм с полиномиальным временем для решения этой задачи; отправка одного запроса на сайт (с заданным ре- бром e и временем t) рассматривается как отдельный шаг вычислений.

19. Группа планирования сети из коммуникационной компании CluNet столкну- лась со следующей задачей. Имеется связный граф G = (V, E); узлы графа пред- ставляют точки, с которыми требуется организовать обмен данными. Каждое ребро e представляет канал связи с заданной пропускной способностью b

Для каждой пары узлов и, v V требуется выбрать один путь P из и в v, по

которому эта пара будет обмениваться данными. Критической пропускной спо- собностью b(P) этого пути P называется минимальная пропускная способность всех входящих в него ребер; иначе говоря, b(P) = mineep be. Лучшей достижимой пропускной способностью для пары u, v в графе G называется максимум значения b(P) по всем путям P для пар и-v в графе G.

С какого-то момента отслеживать пути для всех пар узлов в сети становится слишком сложно, и один из проектировщиков сети выступает со смелым пред- ложением: нельзя ли найти остовное дерево T для G, в котором для каждой пары узлов u, v уникальный путь и-v в дереве будет обеспечивать лучшую до- стижимую пропускную способность для маршрута и-v в G? (Иначе говоря, хотя путь и-v может выбираться по всему графу, улучшить результат по сравнению с путем и-v в T все равно не удастся.)

В CluNet эта идея подверглась дружной критике, и у этого скептицизма имеется естественная причина: пути, которые будут использоваться для обеспечения пропускной способности между двумя узлами, могут сильно отличаться. С чего бы полагать, что одно дерево одновременно решит все проблемы? Но после не- скольких неудачных попыток опровергнуть идею люди начинают подозревать, что это все же возможно.

Докажите, что такое дерево существует, и предложите эффективный алгоритм его построения. Иначе говоря, предложите алгоритм построения остовного дерева T, в котором для каждой пары u, v 0 каждого ребра; при этом стоимости ребер могут совпадать. Если граф может содержать ребра с одинаковой стоимо- стью, то и решений с минимальной стоимостью может быть несколько. Предпо- ложим, имеется остовное дерево T !Ξ E с гарантией того, что каждое ребро e

T принадлежит некоторому минимальному остовному дереву графа G. Можно ли заключить, что T является минимальным остовным деревом G? Представьте доказательство или контрпример с объяснением.

23. Вспомните задачу вычисления ориентированного дерева с минимальной стои- мостью в направленном графе G = (V, E) со стоимостями ребер ce > 0. Здесь мы рассмотрим случай, в котором G является направленным ациклическим графом (DAG), то есть не содержит направленных циклов.

Как и в случае с направленными графами вообще, разных решений с мини- мальной стоимостью может быть много. Допустим, имеется направленный ациклический граф G = (V, E) и ориентированное дерево A !Ξ E с гарантией того, что каждое ребро e A принадлежит некоторому ориентированному де- реву с минимальной стоимостью в G. Можно ли сделать вывод, что A является ориентированным деревом с минимальной стоимостью в G? Представьте до- казательство или контрпример с объяснением.

24. Цепи синхронизации — один из важнейших компонентов больших интеграль- ных схем. Ниже представлена простая модель такой цепи. Возьмем полное сбалансированное бинарное дерево с n листьями, где n — степень 2. С каждым ребром e дерева связана длина i, которая является положительным числом. Расстояние от корня до заданного листа вычисляется суммированием длин всех ребер пути от корня к листу.

Корень генерирует синхросигнал, который распространяется по ребрам к ли- стьям. Будем считать, что время, необходимое сигналу для перехода к задан- ному листу, пропорционально расстоянию от корня до листа.

Если расстояния от листьев до корня различны, то сигнал дойдет до листьев в разное время, и это создаст большие проблемы. Мы хотим, чтобы листья были полностью синхронизированы и получали сигнал одновременно. Для этого необходимо увеличить длины некоторых ребер, чтобы все пути от корня до листьев имели одинаковую длину (уменьшить длины ребер нельзя). Если эта задача будет решена, то дерево (с новыми длинами ребер) имеет нулевой сдвиг. Наша цель — обеспечить нулевой сдвиг так, чтобы сумма длин всех ребер оста- валась минимальной.

Предложите алгоритм, увеличивающий длину некоторых ребер так, чтобы по- лученное дерево имело нулевой сдвиг, а общая длина ребер была минимально возможной.

Пример. Рассмотрим дерево на рис. 4.20, на котором буквами обозначены узлы, а числами — длины ребер.

Рис. 4.20. Задача нулевого сдвига из упражнения 23


Уникальное оптимальное решение для этой задачи — взять три ребра длины 1 и увеличить каждую из этих длин до 2. Полученное дерево имеет нулевой сдвиг, а сумма длин ребер равна 12 (минимальная из возможных).

25. Имеется множество точек P = {р 1, p2, ..., рn} и функция расстояния d для мно- жества P; d — функция для пары точек в P, обладающая тем свойством, что

d(р,р) = d(р,р) > 0, если i ф j, а d(р,р) = 0 для каждого i.

1 j j 1 1

Определим иерархическую метрику для P как произвольную функцию рас- стояния τ, которая строится следующим образом: строим корневое дерево T с n листьями и назначаем каждому узлу v дерева T (как листьям, так и дочерним узлам) высоту hv. Высоты должны удовлетворять следующим условиям: h(v) = 0 для каждого листа v, и если и является родителем v в T, то h(u) > h(v). Каждая точка из P ставится в соответствие отдельному листу T. Теперь для каждой пары точек р. и р определяется расстояние между ними τ( р,, рj): мы находим наименьшего общего предка v в T для листьев, содержащих рi и рj, и определяем

τ( р,, рр = h

Иерархическая метрика τ называется согласованной с функцией расстояния d, если для всех пар i, j выполняется условие ^р.,р ) < d(р,р ).

Предложите алгоритм с полиномиальным временем, который получает функ- цию расстояния d и выдает иерархическую метрику τ со следующими свой- ствами:

(i) метрика τ согласована с d, и

(ii) если τ' — любая другая иерархическая метрика, согласованная с d, то

τ'(р,р ) < τ(ρ,p ) для каждой пары точекр. ир..

26. Одна из первых задач, рассматриваемых в курсе математического анализа, — задача минимизации дифференцируемой функции (например, y = ax2 + bx + с для a > 0). С другой стороны, задача нахождения минимального остовного дерева относится к совершенно иной разновидности задач минимизации: количество вариантов для достижения минимума ограничеyно, но вычисле- ния должны проводиться без перебора этого (огромного) конечного числа возможностей.

Что произойдет, если свести воедино эти две разновидности минимизации? Ниже приведен пример задачи такого рода. Допустим, имеется связный граф G = (V, E); переменная стоимость каждого ребра изменяется во времени в соответ- ствии с функцией fe: R^∙R. Таким образом, в момент времени t ребро имеет стоимость fe(t). Предполагается, что все функции принимают положительные значения на всем интервале значений. Заметьте, что множество ребер, образу- ющих минимальное остовное дерево графа G, может изменяться со временем. Конечно, стоимость минимального остовного дерева графа G также становится функцией времени t; обозначим эту функцию cG(t). Возникает естественная за- дача: найти значение t, при котором минимизируется cG(t).

Предположим, каждая функция fe определяется многочленом степени 2: f,(t) = at2 + bet + ce, где ae > 0. Предложите алгоритм, который получает граф G и набор значений {(ae, be, с) : e E} и возвращает значение времени t, при ко-

тором минимальное остовное дерево имеет минимальную стоимость. Алгоритм должен выполняться за полиномиальное время в зависимости от количества узлов и ребер графа G. Считайте, что арифметические операции с числами {(ae, be, ce)} выполняются за постоянное время.

27. В ходе анализа комбинаторной структуры остовных деревьев можно рассмо- треть пространство всех возможных остовных деревьев заданного графа и изу- чить свойства этого пространства. Эта стратегия также применяется во многих похожих задачах.

Один из возможных подходов выглядит так. Пусть G — связный граф, а T и T — два разных остовных дерева графа i. Деревья T и T называются соседями, если T содержит ровно одно ребро, не входящее в T', а T' содержит ровно одно ребро, не входящее в T.

Теперь на базе любого графа G строится (большой) граф H. Узлами H явля- ются остовные деревья G, а ребро между двумя узлами H существует в том случае, если соответствующие остовные деревья являются соседями. Правда ли, что для любого связного графа G полученный граф H является связным? Приведите доказательство того, что граф H всегда связный, или представьте контрпример (с объяснением) связного графа G, для которого граф H не яв- ляется связным.

28. Предположим, вы работаете на сетевую компанию CluNet, и вам предложена следующая задача. Сеть, над которой в настоящий момент работает компания, моделируется связным графом G = (V, E) с n узлами. Каждое ребро e представ- ляет оптоволоконный кабель, арендуемый CluNet у его владельцев — компа- ний X и Y. Ваши клиенты хотят выбрать остовное дерево T графа G и обновить каналы, соответствующие ребрам T. Специалисты по деловым отношениям уже заключили с компаниями X и Y договор, в котором указано число k. При выборе дерева T к из его ребер будут принадлежать X, а n-k-1 ребер будут при- надлежать Y.

Теперь руководство CluNet столкнулось с проблемой: ему совершенно неоче- видно, существует ли остовное дерево T, удовлетворяющее таким критериям, и как найти его, если оно существует. Перед вами поставлена задача: найти алгоритм с полиномиальным временем, который получает граф G с ребрами, помеченными X или Y, и либо (i) возвращает остовное дерево, в котором ровно к ребер помечено X, либо (ii) обоснованно сообщает о том, что такое дерево не существует.

29. Имеется список из n натуральных чисел d1, d2, ..., dn. Покажите, как за полиноми- альное время решить, существует ли ненаправленный граф G = (V, E), степени узлов которого равны d1, d2, ..., dn. (То есть если V={v1, v2, ..., vn}, степень v должна быть равна d..) Граф G не может содержать нескольких ребер между одной парой узлов, или «циклических» ребер с одинаковыми конечными точками.

30. Граф G = ( V, E) содержит n узлов; каждая пара узлов соединяется ребром. Каж- дому ребру ( , j) присвоен положительный вес wj значения весов соответствуют неравенству треугольника wk < Wj + wjk. Для подмножества V' Έ Vподграф (с ве- сами ребер), определяемый множеством узлов V', обозначается G[ V'].

Имеется множество X !Ξ V из k точек, которые должны быть соединены ребра- ми. Деревом Штейнера для X называется такое множество Z, что X !Ξ Z Έ V, в сочетании с остовным поддеревом T подграфа G[Z]. Весом дерева Штейнера называется вес дерева T.

Покажите, что задача нахождения дерева Штейнера с минимальным весом для X может быть решена за время O(nO(k)).

31. Вернемся к исходной формулировке задачи нахождения минимального остов-

ного дерева: имеется связный ненаправленный граф G = (V, E) с положитель- ными длинами ребер {le}; нужно найти для него остовной подграф. Теперь допустим, что нас интересует подграф H = (V, F) c большей «плотностью», чем у дерева, и с гарантиями того, что для каждой пары вершин и, v V длина

кратчайшего пути u-v в H не намного больше длины кратчайшего пути u-v в G. Под «длиной пути P» подразумевается сумма ie по всем ребрам e в P. Следующая разновидность алгоритма Крускала строит такой подграф:

• Ребра сортируются в порядке возрастания длин. (Предполагается, что все длины ребер различны.)

• Затем строится подграф H = (V, F) с последовательным рассмотрением всех ребер.

• При переходе к ребру e = (u, v) ребро e включается в подграф H, если в на- стоящее время в H не существует пути и-v. (Алгоритм Крускала делал бы то же самое.) С другой стороны, если путь и-v в H существует, обозначим duv кратчайший из таких путей (как и прежде, длина определяется значениями {£e}). Ребро e добавляется в H, если 3ie < duv.

Иначе говоря, ребро добавляется даже в том случае, если и и v уже находятся в одной компоненте связности, — при условии, что добавление ребра в доста- точной степени сокращает их расстояние кратчайшего пути.

Пусть H = ( V, F) — подграф G, возвращенный алгоритмом.

(a) Докажите, что для каждой пары узлов u, v Vдлина кратчайшего пути и-v в H не более чем в три раза превышает длину кратчайшего пути и-v в G.

(b) Несмотря на приближенное сохранение расстояний кратчайших путей, подграф H, произведенный алгоритмом, не должен быть слишком плотным. Пусть f(n) — максимальное количество ребер, которые могут быть получены на выходе алгоритма для всех входных графов из n узлов с длинами ребер. Докажите, что


32. Рассмотрим направленный граф G = (V, E) с корнем r Vи неотрицательными

стоимостями ребер. В этой задаче рассматриваются разновидности алгоритма ориентированного дерева с минимальной стоимостью.

(a) Алгоритм, рассмотренный в разделе 4.9, работает следующим образом: мы изменяем стоимости, рассматриваем подграф с ребрами нулевой стои- мости, ищем направленный цикл в этом подграфе и сжимаем его (если та- кой цикл существует). Возможно ли вместо циклов найти и сжать сильные компоненты подграфа? Приведите краткое обоснование.

(b) В алгоритме мы определяли величину yv как минимальную стоимость ребра, входящего в v, и изменяли стоимости всех ребер e, входящих в узел v, по формуле c'e = ce - yv. Допустим, вместо этого используется следующая модифицированная стоимость: c''e = max(0, ce - 2yv). Вероятно, в результате этого изменения у большего количества ребер стоимость будет равна 0. Теперь предположим, что мы нашли ориентированное дерево T со стоимо- стью 0. Докажите, что стоимость T не более чем вдвое превышает стоимость ориентированного дерева с минимальной стоимостью в исходном графе.

(c) Предположим, что ориентированное дерево со стоимостью 0 не найдено. Сожмите все сильные компоненты со стоимостью 0 и рекурсивно примените ту же процедуру к полученному графу, пока не будет найдено ориентиро- ванное дерево. Докажите, что стоимость T не более чем вдвое превышает стоимость ориентированного дерева с минимальной стоимостью в исходном графе.

33. Имеется направленный граф G = (V, E), в котором стоимость каждого ребра рав- на либо 0, либо 1. Предположим, в G имеется такой узел r, что существует путь от r к любому другому узлу G. Также дано целое число к. Приведите алгоритм с полиномиальным временем выполнения, который либо строит ориентиро- ванное дерево с корнем r, стоимость которого равна точно к, либо обоснованно сообщает о том, что такое дерево не существует.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения 1.:

  1. УПРАЖНЕНИЕ
  2. Приведем список всех упражнений и их номера:
  3. 5.4. Планирование упражнений
  4. Упражнение 2
  5. Упражнение 3
  6. Упражнение 4
  7. Упражнение 5
  8. Упражнение 6
  9. Упражнение 7
  10. Упражнение 8