Упражнения с решениями - Урок 7 - Нахождение потока в сети

Упражнение с решением 1

Имеется направленный граф G = (V, E) с положительной целочисленной пропускной способностью c_e каждого ребра e, источником s ∈ V и стоком t ∈ V. Также задан целочисленный максимальный поток s-t в G, определяемый величиной потока f_e по каждому ребру e.

Допустим, мы выбираем некоторое ребро e ∈ E и увеличиваем его пропускную способность на одну единицу. Покажите, как найти максимальный поток в полученном графе за время O(m + n), где m — количество ребер в G, а n — количество узлов.

Решение

Важно заметить, что времени O(m + n) недостаточно для вычисления нового максимального потока “с нуля”, поэтому нужно как-то использовать заданный поток f Интуитивно понятно, что даже после увеличения пропускной способности ребра e на 1 поток f не может сильно отдалиться от максимума; в конце концов, сеть изменилась не так уж значительно.

На самом деле нетрудно показать, что максимальная величина потока может увеличиться не более чем на 1.

(7.68) Рассмотрим потоковую сеть G', полученную увеличением пропускной способности e на 1. Величина максимального потока в G' равна либо v(f), либо v(f) + 1.

Доказательство. Величина максимального потока в G' равна минимум v(f), так как f остается действительным потоком в сети. Кроме того, он еще и является целочисленным, поэтому достаточно показать, что величина максимального потока в G' не превышает v(f) + 1.

Согласно теореме о максимальном потоке и минимальном разрезе, в исходной потоковой сети G существует разрез s-t (A, B) с пропускной способностью v(f). Зададимся вопросом: какова пропускная способность (A, B) в новой потоковой сети G'? Все ребра, пересекающие (A, B), имеют в G' ту же пропускную способность, что и G, с возможным исключением e (если e пересекает (A, B)). Но с_е возрастает только на 1, поэтому пропускная способность (A, B) в новой потоковой сети G' не превышает v(f) + 1. ■

Утверждение (7.68) предполагает естественный алгоритм. Начиная с действительного потока f в G', мы пытаемся найти один увеличивающий путь от s к t в остаточном графе G'_f. Поиск выполняется за время O(m + n). Теперь возможен один из двух вариантов: может быть, найти увеличивающий путь не удастся, и тогда мы знаем, что f является максимальным потоком. В противном случае увеличение проходит успешно с поучением потока f' с величиной не менее v(f) + 1. В этом случае согласно (7.68) мы знаем, что f' является максимальным потоком. Итак, в любом случае после вычисления одного увеличивающего пути будет получен максимальный поток.

Упражнение с решением 2

Вы помогаете медицинской фирме “Врачи без выходных” составить рабочее расписание врачей в крупной больнице. Расписание на обычные дни в основном готово, но теперь нужно разобраться с особыми случаями — и в частности позаботиться о том, чтобы в праздники всегда был доступен хотя бы один врач.

Система работает так: определены к праздничных периодов (Рождественская неделя, выходные Дня независимости, выходные Дня благодарения, ...), каждый из которых занимает несколько смежных дней. Пусть D_j — множество дней, включенных в j-й праздничный период; объединение всех этих дней U_jD_j будет называться множеством всех праздничных дней.

В больнице работают n врачей, за каждым врачом i закреплено множество праздничных дней S_i, когда он может выйти на работу. (В это множество может входить лишь часть дней из некоторых праздничных периодов; например, врач может работать в пятницу, субботу и воскресенье в период Дня благодарения, но не в четверг.)

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

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

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

Алгоритм должен либо возвращать распределение, удовлетворяющее этим ограничениям, либо (обоснованно) сообщать о том, что такое распределение не существует.

Решение

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

Для начала посмотрим, как бы решалась эта задача без такого требования — в упрощенном случае, когда у каждого врача i имеется множество S_i дней, когда он может работать, и каждый врач должен работать не более c дней. Схема изображена на рис. 7.23(a). Узлы и представляют врачей, и связываются с узлами v, представляющими дни, когда они могут выйти на работу; ребро имеет пропускную способность 1. Суперисточник s связывается с каждым узлом врача и ребром с пропускной способностью с, и каждый узел дня v₁ связывается с суперстоком t ребром, верхняя и нижняя границы которого равны 1. В этом случае назначенные дни “переходят” по врачам на дни, в которые те могут работать, а нижние границы ребер от дней до стока гарантируют, что каждый день будет обеспечен врачом. Наконец, предположим, что общее количество праздничных дней равно d; мы назначаем стоку уровень потребления +d, источнику — уровень потребления -d, а затем ищем действительную циркуляцию. (Вспомните, что после введения нижних границ для некоторых ребер алгоритмы формулируются в терминологии циркуляции с потреблением, а не максимального потока.)

Рис. 7.23. a — врачи связываются с выходными днями без ограничения того, сколько дней за один праздничный период может отработать врач; b — потоковая сеть дополняется “регуляторами”, не позволяющими врачу работать более одного дня в каждый праздничный период. Множества, выделенные серым цветом, соответствуют разным праздничным периодам

Но мы должны обеспечить выполнение дополнительного требования: что каждый врач может отработать не более одного дня за каждый праздничный период. Для этого берется каждая пара (i, j), состоящая из врача i и праздничного периодаj, и добавляется “регулятор” — новый узел w_ij с входящим ребром с пропускной способностью 1 от узла врача u_i, и выходящими ребрами с пропускной способностью 1 к каждому дню праздничного периода j, когда врач i доступен для работы. Регулятор “сужает” поток от u_i к дням праздничного периода j, чтобы к ним могла проходить максимум одна единица потока. Схема изображена на рис. 7.23, b. Как и прежде, мы назначаем для стока уровень потребления +d, для источника — уровень потребления -d, и ищем действительную циркуляцию. Общее время выполнения соответствует времени построения графа, которое равно O(nd), плюс время поиска одной действительной циркуляции в этом графе.

Правильность алгоритма следует из следующего утверждения.

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

Доказательство. Во-первых, если вариант связывания врачей с праздничными днями с соблюдением всех ограничений существует, то мы можем построить следующую циркуляцию. Если врач iработает в день l праздничного периода j, мы передаем одну единицу потока по пути s, u_i, w_ij, v_i, t; это делается для всех таких пар (i, l). Так как распределение врачей удовлетворяет всем ограничениям, полученная циркуляция соблюдает все пропускные способности; кроме того, она отправляет d единиц потока из s и доставляет его в t, а следовательно, соблюдает уровни потребления.

И наоборот, предположим, что существует действительная циркуляция. В этом направлении доказательства мы покажем, как использовать циркуляцию для построения расписания для всех врачей. Прежде всего, согласно (7.52), существует действительная циркуляция, в которой все величины потоков являются целыми числами. Теперь мы построим расписание следующим образом: если ребро (w_ij, v_i) передает единицу потока, то врач i работает в день l. Из-за пропускных способностей в полученном расписании каждый врач работает не более c дней, не более одного в каждом праздничном периоде, и в каждый день работает один врач. ■

Упражнения

1. (а) Перечислите все минимальные разрезы s-t в потоковой сети, изображенной на рис. 7.24. Рядом с каждым ребром на схеме обозначена его пропускная способность.

(b) Какова минимальная пропускная способность разреза s-t в потоковой сети на рис. 7.25? Как и в предыдущем случае, пропускная способность каждого ребра обозначена рядом с ним.

2. На рис. 7.26 изображена потоковая сеть с вычисленным потоком s-t. Рядом с каждым ребром на схеме обозначена его пропускная способность, а числа в прямоугольниках задают величину потока, передаваемого по каждому ребру. (Ребра без чисел в прямоугольниках — а именно четыре ребра с пропускной способностью 3 — не передают поток.)

(a) Какова величина этого потока? Является ли он максимальным потоком (s, t) в этом графе?

(b) Найдите минимальный разрез s-t в потоковой сети, изображенной на рис. 7.26. Укажите, чему равна его пропускная способность.

Рис. 7.24. Найдите минимальные разрезы s-t в этой потоковой сети

Рис. 7.25. Определите минимальную пропускную способность разреза s-t в этой потоковой сети

Рис. 7.26. Найдите величину изображенного потока. Является ли он максимальным? Найдите минимальный разрез

3. На рис. 7.27 изображена потоковая сеть с вычисленным потоком s-t. Рядом с каждым ребром на схеме обозначена его пропускная способность, а числа в прямоугольниках задают величину потока, передаваемого по каждому ребру. (Ребра без чисел в прямоугольниках не передают поток.)

(a) Какова величина этого потока? Является ли он максимальным потоком (s, t) в этом графе?

(b) Найдите минимальный разрез s-t в потоковой сети, изображенной на рис. 7.27. Укажите, чему равна его пропускная способность.

Рис. 7.27. Найдите величину изображенного потока. Является ли он максимальным? Найдите минимальный разрез

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

Пусть G — произвольная потоковая сеть с источником s, стоком t и положительной целочисленной пропускной способностью с_е для каждого ребра е. Если f — максимальный поток s-t в G, то fнасыщает каждое ребро, выходящее из s (то есть для всех ребер е, выходящих из s, выполняется условие f(е) = с_е).

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

Пусть G — произвольная потоковая сеть с источником s, стоком t и положительной целочисленной пропускной способностью с_е для каждого ребра е; пусть (A, B) — минимальный разрез s-t для этих пропускных способностей {с_е : е ∈ E}. Предположим, каждая пропускная способность увеличивается на 1; в этом случае (A, B) останется минимальным разрезом s-t для новых пропускных способностей {1 + с _е : е ∈ E}.

6. Представители Комиссии по архитектурной эргономике обратились к вам за консультацией.

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

Иногда это возможно, иногда нет. Возьмем два простых плана домов на рис. 7.28; на них размещены три светильника (a, b, c) и три выключателя (1, 2, 3). На рис. 7.28, а выключатели можно связать со светильниками так, чтобы от каждого выключателя проходила линия видимости к светильнику, но на рис. 7.28, b это невозможно.

Рис. 7.28. План (а) эргономичен, потому что выключатели можно связать со светильниками так, что каждый светильник будет виден от управляющего им выключателя. (Выключатель 1 связывается с а, выключатель 2 с b, а выключатель 3 с c). План (b) не эргономичен, потому что такое связывание невозможно

Назовем план с n позициями светильников и n позициями выключателей эргономичным, если каждый светильник можно связать с выключателем так, чтобы каждый светильник был виден от управляющего им выключателя. План представляется множеством из m горизонтальных или вертикальных отрезков на плоскости (стены), при этом i-я стена определяется конечными точками (x_i, у_i), (х'_i, у'_i). Положение каждого из n переключателей и каждого из n светильников задается его координатами на плоскости. Светильник виден от переключателя, если соединяющий их отрезок не пересекает ни одну стену.

Предложите алгоритм, который будет решать, является ли заданный план эргономичным. Время выполнения алгоритма должно быть полиномиальным по m и n. Считайте, что у вас имеется процедура с временем выполнения O(1), которая получает два отрезка и проверяет, пересекаются ли они на плоскости.

7. Рассмотрим группу клиентов мобильных устройств, которые должны быть подключены к одной из нескольких возможных базовых станций. Всего клиентов n, позиция каждого клиента задается координатами (х, у) на плоскости. Также существуют к базовых станций; их позиции тоже заданы координатами (х, у). Требуется, чтобы каждый клиент подключался ровно к одной станции. Выбор вариантов подключения ограничивается парой факторов.

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

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

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

Как известно, в крови каждого человека присутствуют определенные антигены (своего рода молекулярная сигнатура); пациенту нельзя переливать кровь с определенным антигеном, если этот антиген отсутствует в его крови. А если говорить конкретнее, в соответствии с этим правилом кровь делится на четыре группы: A, B, AB и O. Кровь группы A содержит антиген A, кровь группы B — антиген B, кровь группы AB содержит оба антигена, и кровь группы O не содержит ни одного. Таким образом, пациентам с группой крови A при переливании могут получать только кровь групп A и O, пациентам с группой B — только B и O, пациентам с группой O — только O, и пациенты с группой крови AB могут получать кровь любой группы³.

(a) Пусть s_O, s_A, s_B и s_AB — запасы крови разных групп. Известны прогнозируемые потребности в крови всех четырех групп d_O, d_A, d_B и d_AB на следующую неделю. Предложите алгоритм с полиномиальным временем для определения достаточности имеющихся запасов при прогнозируемой потребности.

(b) Рассмотрим следующий пример: ожидается, что за следующую неделю потребуется не более 100 единиц крови. Типичное распределение крови по группам среди пациентов в США выглядит так: примерно 45 % — группа O, 42 % — группа A, 10 % — группа B, и 3 % — группа AB. Больница хочет знать, хватит ли имеющегося запаса при поступлении 100 пациентов с ожидаемым распределением групп. Всего на складе доступно 105 единиц. В следующей таблице приведена сводка прогнозируемой потребности и имеющихся запасов.

Группа крови	Запас	Потребность
O	50	45
A	36	42
B	11	8
AB	8	3

Достаточно ли имеющихся 105 единиц для потребности в 100 единиц? Найдите распределение, удовлетворяющее максимально возможное количество пациентов. Чтобы показать, почему не все пациенты смогут получить донорскую кровь, воспользуйтесь аргументом, основанным на разрезе с минимальной пропускной способностью. Также приведите объяснение этого факта, понятное администрации больницы, не искушенной в алгоритмах (соответственно, в этом объяснении не должны встречаться слова “поток”, “разрез” или “граф” в том смысле, в котором они использовались в книге).

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

Рассмотрим следующую ситуацию: из-за серьезного наводнения спасатели обнаружили n пострадавших, которых необходимо срочно доставить в больницу. В этом регионе имеются k больниц, и каждый из n пострадавших должен быть доставлен в больницу, находящуюся не более чем в получасе езды от его текущего местонахождения (таким образом, у каждого пострадавшего имеется свой выбор больницы в зависимости от его текущего местонахождения).

В то же время было бы нежелательно создавать чрезмерную нагрузку на отдельную больницу, направляя в нее слишком много пациентов. Спасатели общаются по мобильным телефонам, и хотят совместными усилиями подобрать больницы для пострадавших так, чтобы сбалансировать нагрузку: в каждую больницу должны поступить не более [n/k] пострадавших.

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

10. Имеется направленный граф G = (V, E) с положительной целочисленной пропускной способностью с_е каждого ребра е, источником 5 ^ V и стоком t ^ V. Также задан максимальный поток s-tв G, определяемый величиной потока f по каждому ребру е. Поток f является ациклическим: в G не существует цикла, в котором по всем ребрам передается положительный поток. Поток f также является целочисленным.

Допустим, мы выбираем некоторое ребро е* ∈ E и уменьшаем его пропускную способность на одну единицу. Покажите, как найти максимальный поток в полученном графе за время O(m + n), где m — количество ребер в G, а n — количество узлов.

11. Ваши знакомые программисты написали очень быстрый код нахождения максимального потока, основанный на многократном нахождении увеличивающих путей (как описано в разделе 7.1). Однако просматривая результаты выполнения, вы обнаруживаете, что алгоритм не всегда находит поток с максимальной величиной. Ошибка обнаруживается очень быстро; ваши знакомые не разобрались в проблеме обратных ребер, и их реализация строит остаточный граф, который включает только прямые ребра. Другими словами, она ищет пути s-t в графе G_j, состоящем только из ребер е, для которых f(e) < с_е, и завершается при отсутствии улучшающего пути, состоящего только из таких ребер. Назовем эту реализацию “алгоритмом с прямыми ребрами”. (Обратите внимание: мы не пытаемся указывать, как этот алгоритм выбирает свои пути с прямыми ребрами; он может выбирать их так, как считает нужным, при условии, что его выполнение будет завершено только при отсутствии путей с прямыми ребрами.) Вам будет нелегко убедить своих знакомых, что код придется переписывать. Они утверждают, что алгоритм не только быстро работает, но и никогда не возвращает поток, величина которого меньше фиксированной части оптимального. А вы этому верите? Суть их утверждений можно выразить следующим образом. Существует такая абсолютная константа b > 1 (не зависящая от конкретной входной потоковой сети), что для каждого экземпляра задачи максимального потока алгоритм с прямыми ребрами гарантированно находит поток с величиной не менее 1/b величины максимального потока (независимо от того, как он выбирает свои пути).

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

12. Имеется потоковая сеть с ребрами единичной пропусной способности: она состоит из направленного графа G = (V, E), источника s ∈ V и стока t ∈ V; c_e = 1 для всех e ∈ E. Также задан параметр k. Требуется удалить к ребер таким образом, чтобы максимальный поток s-t в G сократился как можно сильнее. Другими словами, нужно найти множество ребер F ⊆ E, для которого │F| = k, а максимальный поток s-t в G' = (V, E-F) был как можно меньше.

Предложите алгоритм с полиномиальным временем для решения этой задачи.

13. В стандартной задаче о максимальном потоке s-t предполагается, что ребра имеют пропускные способности, а величина потока, проходящего через узел, не ограничена. В этой задаче рассматривается разновидность задач о максимальном потоке и минимальном разрезе с пропускными способностями узлов. Пусть G = (V, E) — направленный граф с источником s ∈ V, и стоком t∈ V и неотрицательными пропускными способностями узлов {c_v ≥ 0} для всех v ∈ V. Для потокаf в этом графе поток через узел v определяется как fⁱⁿ(v). Поток называется действительным, если он удовлетворяет обычным ограничениям сохранения потока и ограничениям пропускной способности узлов: fⁱⁿ(v) ≤ c_v для всех узлов. Предложите алгоритм с полиномиальным временем для нахождения максимального потока s-t в такой сети, определяющей пропускные способности для узлов. Определите разрез s-t для сетей с пропускными способностями узлов и покажите, что аналогия теоремы о максимальном потоке и минимальном разрезе остается истинной.

14. Задача о выходе определяется следующим образом. Имеется направленный граф G = (V, E) (схема дорожной сети). Узлы некоторой совокупности X ⊂ V называются населенными, а узлы другой совокупности S ⊂ V называются безопасными. (Предполагается, что X и S не пересекаются.) При возникновении чрезвычайной ситуации требуется найти эвакуационные пути из населенных узлов в безопасные. Множество эвакуационных путей определяется как множество таких путей в G, что (i) каждый узел вX является начальным для одного пути, (ii) последний узел каждого пути принадлежит S, и (iii) пути не имеют пересекающихся ребер. Такой набор путей позволяет “вывести” обитателей населенных узлов в S без чрезмерной перегрузки ребер G.

(a) Для заданных G, X и S покажите, как за полиномиальное время принять решение о том, существует ли множество эвакуационных путей.

(b) Предположим, поставлена та же задача, что в (a), но мы хотим обеспечить еще более сильную версию запрета на перегрузку (iii). Таким образом, формулировка (iii) приводится к виду “пути не имеют общих узлов”.

Покажите, как с таким новым условием за полиномиальное время принять решение о том, существует ли множество эвакуационных путей.

Также приведите пример с теми же G, X и S, для которых на (a) дается положительный ответ, а на (b) — отрицательный.

15. Предположим, вы и ваша знакомая Аланис проживаете в студенческой коммуне с n - 2 другими людьми. За следующие n дней каждый жилец квартиры должен приготовить ужин ровно один раз, так что ежедневно кто-то занимается приготовлением пищи.

Конечно, у каждого жильца имеются свои планы на некоторые дни (экзамены, концерты и т. д.), поэтому решить, кто должен готовить в тот или иной вечер, будет непросто. Для конкретности обозначим жильцов {р_р ..., p_n}, а дни {d₁, ..., d_n}; для человека р_i существует множество дней S_i ⊂ {d₁, ..., d_n}, в которые они не могут заниматься приготовлением ужина.

Действительным расписанием называется такое распределение жильцов коммуны по дням, чтобы каждый жилец готовил ровно в один день, ежедневно кто-то готовил, и если жилец р. готовит в день d_j, то d_j ∉ S_i.

(a) Опишите такой двудольный граф G, в котором идеальное паросочетание существует в том и только том случае, если существует действительное расписание приготовления обедов.

(b) Ваша знакомая Аланис берется за составление действительного расписания. После значительных усилий она строит то, что по ее мнению является действительным расписанием, и уходит на лекции. К сожалению, заглянув в составленное ей расписание, вы замечаете серьезную проблему. n - 2 жильцов распределены в разные дни, в которые они свободны; здесь проблем нет. Но внезапно выясняется, что для двух других людей р_i и р_j, и двух дней d_k и d_l, оба человека были назначены на день d_k, а в день d_l никто не готовит.

Вы хотите исправить ошибку Аланис — но так, чтобы расписание не пришлось строить заново. Покажите, что при наличии такого “почти правильного” расписания можно за время O(n²) решить, существует ли действительное расписание для текущих исходных данных. (А если расписание существует, выведите его.)

16. На заре существования Всемирной паутины часто говорили, что большая часть огромного потенциала таких компаний, как Yahoo!, кроется в “зрачках пользователя” — то есть в том простом факте, что миллионы людей ежегодно просматривают их страницы. Кроме того, убеждая пользователей сообщать личные данные при регистрации, такой сайт, как Yahoo!, может выводить целенаправленную рекламу при каждом посещении — возможность, недоступная для телевизионных сетей или журналов. Скажем, если пользователь сообщает Yahoo!, что он — 20-летний студент Корнелльского университета, то сайт выводит баннер с рекламой квартир в Итаке (штат Нью-Йорк); если же пользователь является 50-летним финансовым брокером из Гринвича (штат Коннектикут), сайт выводит рекламу автосалона по продаже “Линкольнов”. Но чтобы решить, какую рекламу показывать тем или иным пользователям, необходимо провести достаточно серьезные вычисления. Предположим, менеджеры популярного сайта выявили k разных демографических группG₁, G₂, ..., G_k. (Группы могут перекрываться; например, группа G₁ может состоять из всех жителей штата Нью-Йорк, а группа G₂ — из обладателей ученой степени по информатике.) Сайт заключил контракты с m разными рекламодателями на показ определенного количества копий рекламы на сайте. Контракт с i-м рекламодателем формулируется примерно так:

• Имеется подмножество X_i ⊆ {G₁, ..., G_k} демографических групп; рекламодатель i хочет, чтобы его реклама выводилась только у пользователей, принадлежащих хотя бы к одной из демографических групп множества X_i.

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

Рассмотрим задачу планирования хорошей рекламной политики — способа показа одной рекламы для одного пользователя сайта. Предположим, в некоторую минуту с сайтом работают nпользователей. Так как у нас имеется регистрационная информация о каждом пользователем, мы знаем, что пользователь j (для j = 1, 2, ..., n) принадлежит подмножеству U_j ⊆ {G₁, ..., G_k} демографических групп. Задача формулируется так: существует ли способ вывода одной рекламы для каждого пользователя, чтобы выполнить контракты сайта с m рекламодателями за данную минуту (то есть для всех i = 1, 2, ..., m можно ли показать по крайней мере r_i из n пользователей, каждый из которых принадлежит по крайней мере одной демографической группе из X_i, рекламу, предоставленную рекламодателем i?)

Предложите эффективный алгоритм, который решает, возможно ли это, и если возможно — выбирает рекламу, выводимую для каждого пользователя.

17. Администраторы сети обратились к вам за помощью в диагностике. Сеть спроектирована для передачи трафика из источника s в приемник t, поэтому для ее моделирования можно использовать направленный граф G = (V, E), в котором пропускная способность каждого ребра равна 1, а каждый узел лежит по крайней мере на одном пути от s до t.

Когда в сети все работает нормально, максимальный поток s-t в G имеет величину k. Однако хакерская атака уничтожила некоторые ребра, и среди оставшихся ребер не осталось пути из s в t. По причинам, в которые мы не будем углубляться, администраторы полагают, что уничтожено только k ребер — минимальное количество, необходимое для отделения s от i (то есть размер минимального разреза s-t); будем считать, что их оценка верна.

На узле s работает контрольная программа. Если передать ей команду ping(v) (для некоторого узла v), программа сообщает, доступен ли в настоящее время путь из s в v. (Таким образом, вызов ping(t) сообщит, что путь в настоящее время недоступен; с другой стороны, вызов ping(s) всегда сообщает о наличии пути от s до s.) Проверять все ребра в сети было бы непрактично, поэтому администраторы хотя определить размер сбоя при помощи этой программы и разумного применения команды ping.

А теперь задача: предоставьте алгоритм, который выдает серию команд ping к разным узлам сети, а затем выводит полное множество узлов, в настоящий момент недоступных из s. Конечно, можно опросить каждый узел в сети, но вам хотелось бы ограничиться меньшим количеством проверок (предполагается, что разрушены только k ребер). При выдаче серии команд ваш алгоритм может выбирать следующий проверяемый узел на основании результатов предшествующих операций ping.

Предложите алгоритм, который решает эту задачу с использованием всего O(k log n) проверок.

18. Рассмотрим задачу о двудольном паросочетании для двудольного графа G = (V, E). Как обычно, мы говорим, что множество V разбито на множества X и Y, один конец каждого ребра принадлежит X, а другой принадлежит Y.

Если M — паросочетание в G, говорят, что M покрывает узел у, если у является концом одного из ребер в M.

(а) Рассмотрим следующую задачу: имеется граф G и паросочетание M в G. Для заданного числа k требуется решить, существует ли в G паросочетание M', для которого:

(i) M' содержит на k больше ребер, чем M, и

(ii) Каждый узел у ∈ Y, покрываемый M, также покрывается M'.

Эта задача называется задачей расширения покрытия с входными значениями G, M и k, а M' называется решением экземпляра задачи.

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

Примечание: возможно, часть (b) поможет вам в поиске решения.

Пример. Рассмотрим граф на рис. 7.29; допустим, M — паросочетание, состоящее из ребра (x₁, у₂). Приведенный выше вопрос задается для k = 1.

Рис. 7.29. Экземпляр расширения покрытия

В этом случае ответ на задачу расширения покрытия будет положительным. В качестве M' можно выбрать (например) паросочетание из двух ребер (x₁, у₂) и (x₂, у₄); M' содержит на одно ребро больше, чем M, и узел у₂ также покрывается M'.

(b) Приведите экземпляр задачи расширения покрытия, заданный параметрами G, M и k, для следующей ситуации.

У экземпляра есть решение, но в любом решении M ребра M не образуют подмножество ребер M'.

(c) Пусть G — двудольный граф, а M — произвольное паросочетание в G. Рассмотрим следующие две характеристики.

• К₁ — размер наибольшего паросочетания M', для которого каждый узел у, покрываемый M, также покрывается M'.

• К₂ — размер наибольшего паросочетания M" в G.

Очевидно, К₁ ≤ К₂, так как К₂ определяется по всем возможным паросочетаниям в G.

Докажите, что К₁ = К₂; а именно, что максимальное паросочетание может быть получено даже в том случае, если ограничиться покрытием всех узлов, покрываемых исходным паросочетанием M.

19. Местная больница, которой вы уже помогали по разным вопросам планирования, обратилась с новой задачей. Для каждого из следующих n дней было определено количество необходимых врачей; таким образом, в день i должны присутствовать ровно p_i врачей.

Всего в больнице работает k врачей, каждому из которых предложено составить список дней, в которые он желает работать. Таким образом, врач j определяет множество L_j дней для своей работы.

Ваша система должна учесть все списки и попытаться вернуть для каждого врача j список L'_j, обладающий следующими свойствами:

(A) L'_j является подмножеством L_j, то есть врач j работает только в те дни, которые он считает приемлемыми.

(B) По всему множеству списков L'₁, ..., L'_k в день i присутствуют ровно р_i врачей (для i = 1, 2, ..., n).

(a) Опишите алгоритм с полиномиальным временем выполнения, реализующий эту систему. А конкретно предложите алгоритм с полиномиальным временем, который получает числа p₁, p₂, ..., p_n, и списки L₁, ..., L_k, и делает одно из двух:

• Возвращает списки L'₁, L'₂, ..., L'_k, удовлетворяющие свойствам (A) и (B); или

• Сообщает (обоснованно) о том, что множество списков L'₁, ..., L'_k, удовлетворяющее свойствам (A) и (B), не существует.

(b) Руководство больницы обнаружило, что списки, полученные от врачей, слишком ограничены, и система слишком часто сообщает об отсутствии допустимого множества списков L'₁, L'₂, ..., L'_k(сообщает правильно, но не вовремя).

По этой причине требования немного ослабляются. Добавляется новый параметр c > 0; система должна попытаться вернуть для каждого врачаj список L'_j, обладающий следующими свойствами.

(A*) L'_j содержит не более c дней, не входящих в список L_j.

(B) (То же) По всему множеству списков L'₁, ..., L'_k в день i присутствуют ровно p_i врачей (для i = 1, 2, ..., n).

Опишите алгоритм с полиномиальным временем выполнения, реализующий измененную систему. Алгоритм получает числа p₁, p₂, ..., p_n, списки L₁, ..., L_k и параметр c > 0, и делает одно из двух:

• Возвращает списки L'₁, L'₂, ..., L'_k, удовлетворяющие свойствам (A*) и (B*); или

• Сообщает (обоснованно) о том, что множество списков L'₁, ..., L'_k, удовлетворяющее свойствам (A*) и (B*), не существует.

20. Ваши знакомые участвуют в крупномасштабном эксперименте по изучению атмосферы. Они хотят получить измерения по множеству S из n разных атмосферных характеристик (например, концентрации озона в разных местах); они располагают m зондами, которые запускаются для проведения измерений. Каждый зонд может провести не более двух измерений.

К сожалению, не все зонды способны измерять все условия, поэтому для каждого зонда i = 1, ..., m имеется множество S. характеристик, которые могут измеряться этим зондом. Наконец, чтобы результаты были более надежными, они планируют провести каждое измерение минимум с k разных зондов. (Обратите внимание: один зонд не может измерять одну характеристику дважды.) Теперь нужно рассчитать, какие характеристики должны измеряться тем или иным зондом.

Пример. Допустим, k = 2, существуют n = 4 условий c₁, c₂, c₃, c₄, и имеются m = 4 зонда для измерения характеристик; при этом действуют ограничения S₁ = S₂ = {c₁, c₂, c₃}, и S₃ = S₄ = {c₁, c₃, c₄}. Один из возможных способов гарантировать, что каждая характеристика будет измерена не менее k = 2 раз, выглядит так:

• зонд 1 измеряет условия c₁, c₂,

• зонд 2 измеряет условия c₂, c₃,

• зонд 3 измеряет условия c₃, c₄,

• зонд 4 измеряет условия c₁, c₄.

(a) Предложите алгоритм с полиномиальным временем, который получает входные данные экземпляра задачи (n характеристик, множества S_i для каждого из m зондов, параметр k) и решает, возможно ли измерить каждую характеристику с k разных зондов при том, что каждый зонд может измерять не более двух характеристик.

(b) Вы показываете своим знакомым решение, вычисленное алгоритмом из пункта (a) — но к вашему изумлению, слышите: “Не годится — одна из характеристик измеряется только зондами одного поставщика”. Но до этого о поставщиках вы ничего не слышали; кажется, в задаче появился дополнительный нюанс, о котором забыли упомянут.

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

Допустим, зонд 1 выпущен первым поставщиком, зонды 2 и 3 — вторым, а зонд 4 — третьим. Тогда предыдущее решение уже не работает, так как оба измерения с₃ выполнены зондами второго поставщика. С другой стороны, мы можем использовать зонды 1 и 2 для измерения характеристик c₁, c₂, а зонды 3 и 4 — для измерения характеристик c₃, c₄.

Объясните, как преобразовать алгоритм с полиномиальным временем из части (a) в новый алгоритм, который решает, существует ли решение с выполнением всех требований из (a), а также нового требования о поставщиках.

21. Вы помогаете организовать занятия в колледже, который решил выдать всем студентам беспроводные планшетные компьютеры на семестр. Таким образом, имеется набор из nбеспроводных планшетов; также имеется набор из n беспроводных точек доступа, к которым планшеты могут подключаться при нахождении в зоне действия.

В настоящее время планшеты хаотично распределены по всему городку; планшет l находится в зоне действия множества S' точек доступа. Будем считать, что каждый планшет находится в зоне действия по крайней мере одной точки доступа (так что множества S' не пусты); также предполагается, что в зоне действия каждой точки доступа p находится по крайней мере один планшет. Для нормальной работы программ беспроводной связи необходимо постараться связать планшеты с точками доступа так, чтобы каждый планшет и каждая точка доступа были задействованы минимум в одном подключении. Тестовым множеством T будет называться совокупность упорядоченных пар вида (l, p) для планшета l и точки доступа p, обладающих следующими свойствами:

(i) Если (l, p) ∈ T, то l находится в зоне действияp (то есть p ∈ S_l)

(ii) Каждый планшет входит минимум в одну упорядоченную пару в T.

(iii) Каждая точка доступа входит минимум в одну упорядоченную пару в T. Итак, проверяя все подключения, определяемые парами из T, мы можем убедиться в том, что программное обеспечение на каждом планшете и каждой точке доступа работает правильно.

Задача: для заданных множеств S_l для каждого планшета (какие планшеты находятся в зоне действия тех или иных точек доступа) и числа k решите, существует ли тестовое множество с размером, не превышающим k.

Пример. Допустим, n = 3; планшет 1 находится в зоне действия точек доступа 1 и 2; планшет 2 находится в зоне действия точки доступа 2; планшет 3 находится в зоне действия точек доступа 2 и 3. В этом случае множество пар

(планшет 1, точка доступа 1), (планшет 2, точка доступа 2),

(планшет 3, точка доступа 3)

образует тестовое множество с размером 3.

(a) Приведите пример экземпляра задачи, для которого не существует тестовое множество с размером n. (Вспомните: предполагается, что каждый планшет находится в зоне действия минимум одной точки доступа и в зоне действия каждой точки доступаp находится минимум один планшет.)

(b) Предложите алгоритм с полиномиальным временем, который получает экземпляр задачи (включая параметр к) и решает, существует ли тестовый размер с размером, не превышающим к.

22. Пусть M — матрица n x n, каждый элемент которой равен 0 или 1; m_ij — элемент матрицы, находящийся на пересечении строки i и столбца j. Диагональным элементом называется элемент вида m_ii для некоторого i.

Перестановкой строк i и j матрицы M называется операция, при которой меняются местами значения m_ik и m_jk для k = 1, 2, ..., n. Перестановка двух столбцов определяется аналогично.

Матрица M называется перестраиваемой, если возможно выполнить перестановки некоторых пар строк и некоторых пар столбцов (в произвольной последовательности) так, чтобы после всех перестановок все диагональные элементы M были равны 1.

(a) Приведите пример патрицы M, которая не является перестраиваемой, но в каждой строке и каждом столбце которой по крайней мере один элемент равен 1.

(b) Предложите алгоритм с полиномиальным временем, определяющий, является ли матрица M с элементами 0-1 перестраиваемой.

23. Имеется потоковая сеть G с источником s и приемником t; вы хотите как-то выразить следующие интуитивные понятия: некоторые узлы явно находятся на “стороне источника” основных “узких мест”; другие узлы явно находятся на “стороне стока” основных “узких мест”, а третьи располагаются посредине. Однако в G может быть много минимальных разрезов, поэтому необходимо проявить осторожность в выборе точной формулировки.

Один из способов разбиения узлов G на три категории выглядит так:

• Узел v называется верховым, если для всех минимальных разрезов s-t (A, B) выполняется v ∈ A — то есть v лежит на стороне источника каждого минимального разреза.

• Узел v называется низовым, если для всех минимальных разрезов s-t (A, B) выполняется v ∈ B — то есть v лежит на стороне стока каждого минимального разреза.

• Узел v называется срединным, если он не является ни верховым, ни низовым; существует как минимум один минимальный разрез s-t (A, B), для которого v ∈ A, и как минимум один минимальный разрез s-t (A', B'), для которого v ∈ B'.

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

24. Пусть G = (V, E) — направленный граф с источником s ∈ V, и стоком t ∈ V и неотрицательными пропускными способностями ребер {c_e}. Предложите алгоритм с полиномиальным временем, который определяет, существует ли в G уникальный минимальный разрез s-t (то есть разрез s-t, пропускная способность строго меньше пропускной способности любого другого разреза s-t).

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

Но год подошел к концу, и пришло время свести счеты. В квартире живут n людей; для каждой упорядоченной пары (i, j) существует накопленная за год сумма a_ij ≥ 0, которую жилец iзадолжал j. Требуется, чтобы для любых двух людей i и j по крайней мере одна из величин а_ij или а_ji была равна 0. Сделать это несложно: если выясняется, что i должен j положительную сумму х, а j должен i положительную сумму у < х, то мы вычитаем у из обоих сторон и объявляем a_ij = х - у при а_ji = 0. В контексте этих величин дисбаланс жильца i определяется как сумма величин, которую i должны все остальные, за вычетом суммы величин, которые i должен всем остальным. (Дисбаланс может быть положительным, отрицательным или нулевым.)

Чтобы обнулить все дисбалансы и расстаться в хороших отношениях, некоторые жильцы выписывают чеки другим жильцам; другими словами, для некоторых упорядоченных пар (i, j) iвыписывает чек j на сумму b_ij > 0. Множество чеков будет называться расчетом, если для каждого жильца i общая сумма чеков, полученных i, за вычетом общей суммы чеков, выписанных i, равна дисбалансу i. Наконец, все жильцы чувствуют, что для i было бы неправильно выписывать чек j, если i на самом деле не задолжал j, поэтому расчет называется корректным, если при выписывании i чека j выполняется условие a_ij > 0. Покажите, что для любого множества a_ij всегда существует корректный расчет, при котором выписываются не более n-1 чека; для этого приведите алгоритм с полиномиальным временем для вычисления такого расчета.

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

Известны позиции нескольких базовых станций n, заданных точками b₁, ..., b_n на плоскости. Также известны позиции n сотовых телефонов, заданных точками р₁, ..., p_n. Наконец, задан еще один параметр — зона действия Δ > 0. Множество сотовых телефонов будет называться полностью связным, если каждый телефон можно связать с базовой станцией с выполнением следующих условий:

• Все телефоны подключены к разным базовым станциям, и

• Если телефон в точке р_i подключен к базовой станции в точке b_j, то расстояние по прямой между точками р_i и b_j не превышает Δ.

Предположим, владелец сотового телефона в точке р₁ отправляется в поездку, перемещаясь на z единиц расстояния на восток. При перемещении сотового телефона придется обновлять его подключение к базовой станции (возможно, несколько раз), чтобы множество телефонов оставалось полностью связным. Предложите алгоритм с полиномиальным временем, который будет принимать решение о том, возможно ли сохранять полную связность множества телефонов во время перемещения одного сотового телефона (предполагается, что все остальные телефоны при этом остаются неподвижными). Если это возможно, выведите последовательность подключений телефонов к базовым станциям, достаточную для сохранения полной связности; если это невозможно, выведите точку на пути перемещающегося телефона, в которой сохранение полной связности становится невозможным. Алгоритм должен выполняться за время O(n³), если это возможно.

Пример. Допустим, телефоны находятся в точках р₁ = (0, 0) и р₂ = (2, 1); базовые станции расположены в точках b₁ = (1, 1) и b₂ = (3,1); и Δ = 2. Телефон из точки р₁ перемещается на восток на расстояние 4 единицы, завершая свое движение в точке (4, 0). В этом случае можно сохранить полную связность множества телефонов во время перемещения: сначала р₁ подключается к b₁, а р₂ к b₂, а затем во время перемещения р₁ переподключается к b₂, а р₂ к b₁ (например, при прохождении р₁ точки (2, 0)).

27. Ваши знакомые, работающие на Западном побережье, решают скооперироваться для совместных поездок на работу. К сожалению, сидеть за рулем никто не любит, поэтому схема кооперации должна быть справедливой, чтобы никому из участников не пришлось слишком часто вести машину. Простая круговая схема не подходит, потому что никто не ездит на работу ежедневно, и подмножество людей, пользующихся машиной, изменяется от одного дня к другому.

Рассмотрим один из способов определения “справедливости”. Допустим, люди обозначаются S = {р₁, ..., p_k}. Общим обязательством p_j по множеству дней является ожидаемое количество раз, в течение которых p_j пришлось бы вести машину, если бы водитель выбирался случайным образом среди тех, кто едет на работу каждый день. А конкретнее, предположим, что план совместных поездок рассчитан на d дней, и в i-й день на работу едет подмножество людей S_i ⊆ S. Тогда приведенное выше определение обязательства Δj для р_j может быть записано в виде В идеале хотелось бы потребовать, что p_j ведет машину не более Δj раз; к сожалению, Δj может не быть целым числом. Планом совместных поездок назовем выбор водителя на каждый день — то есть последовательность а справедливым планом назовем план, в котором каждый участник р_j выбирается водителем не более чем для [Δ_j] дней.

(а) Докажите, что для произвольной последовательности множеств S₁, ..., S_d существует справедливое расписание совместных поездок.

(b) Предложите алгоритм для вычисления справедливого плана совместных поездок с временем выполнения, полиномиальным по k и d.

28. Группа студентов решила добавить новые функции в компьютерную систему подготовки учебных курсов для отработки аспектов планирования, в настоящее время не поддерживаемых программой. Работа начинается с модуля, который помогает планировать учебное время в начале семестра. Прототип работает по следующим правилам: прежде всего расписание остается постоянным, поэтому задачу планирования достаточно решить для одной недели. Администратор вводит набор неперекрывающихся одночасовых интервалов I₁, I₂, ..., I_k, в которые занятия могут проводиться ассистентами; итоговое расписание представляет собой подмножество (как правило, неполное) этих интервалов. Затем каждый ассистент вводит свое расписание на неделю с временем, в которое он будет свободен для проведения занятий.

Наконец, администратор указывает параметры a, b и с: каждому ассистенту было бы желательно выделить от а до b учебных часов в неделю, а количество учебных часов в неделю составляет ровно с.

Итак, задача в том, как назначить каждому ассистенту некоторые из учебных часов, чтобы каждый ассистент был доступен в каждый из его учебных часов, и при этом было обеспечено правильное количество учебных часов. (В каждый час должен присутствовать только один ассистент.)

Пример. Допустим, имеются пять временных интервалов:

I₁ = Понедельник 15-16; I₂ = Вторник 13-14; I₃ = Среда 10-11; I₄ = Среда 15-16; I₅ = Четверг 10-11.

Есть два ассистента; первый может работать в любое время в понедельник и среду во второй половине дня, а второй — в любое время во вторник, среду и четверг. (В общем случае правила доступности ассистентов могут быть более сложными, но мы не будем усложнять пример.) Наконец, каждому ассистенту должно быть выделено от a = 1 до b = 2 учебных часов, а общее количество учебных часов за неделю должно быть равно с = 3.

В одном из возможных решений первому ассистенту выделяются учебные часы из интервала I₁, а второму — часы из интервалов I₂ и I₅.

(a) Предложите алгоритм с полиномимальным временем, который получает входные данные экземпляра этой задачи (интервалы, свободное время ассистентов и параметры a, b и с) и делает одно из двух:

• Стоит действительное расписание с указанием того, какому ассистенту выделяются те или иные интервалы, или

• Сообщает (обоснованно) о том, что требуемый способ распределения учебных часов не существует.

(b) Функция планирования учебных часов становится очень популярной, и администрация начинает хотеть большего. В частности, она замечает, что было бы неплохо повысить количество учебных часов в дни сдачи домашних работ.

Администрация хочет иметь возможность задать новый параметр — “плотность” учебных часов для каждого дня недели: число d_i означает, что в заданный день недели i должно быть назначено не менее d_i учебных часов. Допустим, в предыдущем примере добавляется ограничение, согласно которому в среду и четверг должно быть проведено по крайней мере по одному учебному часу. В этом случае приведенное выше решение не работает; но существует возможное решение, в котором первому ассистенту выделяются учебные часы в интервале I₁, а второму — часы в интервалах I₃ и I₅. (Другое решение — первому ассистенту выделяются часы в интервалах I₁ и I₄, а второму — в интервале I₅.)

Предложите алгоритм с полиномиальным временем, который строит расписание для более сложного набора ограничений. Алгоритм должен либо строить расписание, либо сообщать (обоснованно) о том, что оно не существует.

29. Ваши знакомые открыли небольшую компанию — в настоящее время они заняли под офис родительский гараж в Санта-Кларе. Сейчас компания занимается портированием своего программного обеспечения со старой на новую, более мощную платформу; сейчас она столкнулась со следующей проблемой. Имеется набор из n приложений {1, 2, ..., n}, работающих в старой системе; некоторые из этих приложений нужно портировать в новую систему. Ожидается, что портирование приложения i в новую систему принесет чистую (денежную) прибыль b_i ≥ 0. Приложения взаимодействуют друг с другом; если только одно из двух активно взаимодействующих приложений i и j было перенесено на новую платформу, компания несет потери x_ij ≥ 0.

Если бы все было настолько просто, ваши знакомые портировали бы все п приложений с получением общей прибыли К сожалению, возникает одна проблема...

Из-за мелких, но принципиальных несовместимостей между двумя платформами приложение 1 невозможно портировать; оно неизбежно остается в старой системе. С другой стороны, портирование части других приложений может оказаться экономически оправданным — с учетом всех прибылей и затрат на взаимодействие между приложениями в разных системах.

Итак, какие же приложения следует портировать на новую платформу (если они есть, конечно)? Предложите алгоритм с полиномиальным временем для нахождения множества S ⊆ {2, 3, ..., n}, для которого сумма прибылей от портирования приложений S на новую платформу с вычетом расходов будет максимальной.

30. Рассмотрим модификацию следующей задачи. В новой ситуации портироваться может любое приложение, но некоторые прибыли b_i при портировании на новую платформу оказываются отрицательными: если b_i < 0, то приложение i предпочтительно (на величину, определяемую i) оставить на старой платформе. Предоставьте алгоритм с полиномиальным временем для нахождения множества S ⊆ {1, 2, ..., n}, для которого сумма прибылей от портирования приложений S на новую платформу с вычетом расходов будет максимальной.

31. Ваши друзья проходят практику в маленькой, но перспективной компании Web-Exodus. Дежурная шутка среди работников этой компании: мощные серверы занимают в компьютерной меньше места, чем пустые коробки от компьютерного оборудования, хранящиеся на тот случай, если что-то придется возвращать поставщику для технического обслуживания.

Несколько дней назад поступила партия мониторов в больших коробках; мониторы разные, поэтому и коробки имеют разные размеры. Работники компании с утра пытаются придумать, как бы их разместить для хранения. Разумеется, для экономии места часть коробок можно хранить внутри других коробок.

Предположим, каждая коробка i представляет собой прямоугольный параллелепипед с длинами сторон (i₁, i₂, i₃); каждая длина стороны лежит строго в диапазоне от 0,5 метра до 1 метра. С геометрической точки зрения размещение одной коробки внутри другой означает, что меньшую коробку можно повернуть так, чтобы она помещалась внутри большей коробки по каждому измерению. Формально можно сказать, что коробка i с размерами (i₁, i₂, i₃) помещается внутри коробки j с размерами (j₁, j₂, j₃), если существует перестановка а, b, c измерений {1, 2, 3}, при которой i_a < j₁, i_b < j₂ и i_c < j₃. Конечно, вложение рекурсивно: если i находится внутри j, а j находится внутри k, то из всех трех коробок видна только коробка k. Мы будем называть вложением для множества из n коробок последовательность операций, при которой коробка i размещается внутри коробки j; а если внутри i уже лежат другие коробки, они также оказываются внутри j. (Также обратите внимание на следующее: так как каждая из сторон i имеет длину более 0,5 метра, а каждая из сторон j имеет длину меньше 1 метра, коробка I занимает более половины размера по каждому измерению j, и после того, как коробка i окажется внутри j, ничего больше в j положить уже не удастся.) Коробка к во вложении называется видимой, если в результате последовательности операций она не вкладывается в другую коробку.

А теперь задача, с которой столкнулись в фирме Web-Exodus: так как место занимают только видимые коробки, как выбрать вложение, минимизирующее количество видимых коробок?

Предложите алгоритм с полиномиальным временем для решения этой задачи.

Пример. Имеются три коробки с размерами (0,6, 0,6, 0,6), (0,75, 0,75, 0,75) и (0,9, 0,7, 0,7). Первую коробку можно положить как во вторую, так и в третью; но в любом вложении как вторая, так и третья коротка будут видимы. Следовательно, минимально возможное количество видимых коробок равно 2, а прийти к нему можно только одним способом — положив первую коробку во вторую.

32. Для заданного графа G = (V, Е) и натурального числа к можно определить отношение для пар вершин G следующим образом: если x, y ∈ V, мы говорим, что если в Gсуществуют k путей из х в у, взаимно непересекающихся по ребрам. Можно ли утверждать, что для всех G и всех k ≥ 0 отношение транзитивно? Иначе говоря, если и то всегда ли Приведите доказательство или контрпример.

33. Имеется направленный граф G = (V, E); предположим, для каждого узла v количество ребер, входящих в v, равно количеству ребер, выходящих из v. Другими словами, для всех v

Пусть x, y — два узла G, и существуют k путей из x в у, взаимно непересекающихся по ребрам. В такой ситуации можно ли утверждать, что существуют k путей из у в х, взаимно непересекающихся по ребрам? Приведите доказательство или контрпример с объяснением.

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

Обратите внимание: речь идет об (а) относительно недорогих устройствах, которые (b) сбрасываются с самолета в (c) аварийную зону; с учетом всей комбинации факторов необходимо предусмотреть возможность обработки отказов на разумном количестве узлов.

Если одно из устройств v обнаруживает опасность отказа, оно передает представление своего текущего состояния на другое устройство в сети. Каждое устройство обладает ограниченной дальностью передачи — допустим, оно может взаимодействовать с другими устройствами, находящимися от него на расстоянии не более d метров. Кроме того, состояние не должно передаваться на устройство, на котором уже произошел сбой, поэтому следует предусмотреть некоторую избыточность: устройство v должно располагать множеством к других устройств, с которыми оно может связаться (каждое из которых находится на расстоянии не более d метров). Назовем его резервным множеством для устройства v.

(a) Имеется множество из n беспроводных устройств, позиции которых представлены парами координат (x, y). Разработайте алгоритм, который определяет, возможно ли выбрать резервное множество для каждого устройства (то есть к других устройств, каждое из которых удалено не более чем на d метров) с тем дополнительным свойством, что для некоторого параметра b никакое устройство не входит в резервное множества более чем b других устройств. Алгоритм должен выводить сами резервные множества, если их удастся найти.

(b) Представление о том, что для каждой пары устройств v и w существует четкая дихотомия между понятиями “в зоне действия” и “вне зоны действия” — всего лишь упрощенная абстракция. В более точном представлении существует функция снижениям мощности f(∙), которая для пары устройств на расстоянии δ определяет мощность сигнала f(δ) на беспроводном подключении между этими устройствами. (Предполагается, что f(δ) убывает с возрастанием δ).

Это представление хотелось бы встроить в концепцию резервных множеств: среди k устройств резервного множества v должно быть как минимум одно, с которым возможна связь с очень высокой мощностью сигнала; по крайней мере одно устройство, доступное с умеренно высокой мощностью сигнала, и т. д. А конкретнее, имеются такие значения p₁ ≥ p₂ ≥ ... ≥ p_k, что если резервное множество v состоит из устройств на расстояниях d₁ ≤ d₂ ≤ ... ≤ d_k, должно выполняться условие f(d_j) ≥ p_j для всех j.

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

35. Вы разрабатываете интерактивную программу сегментации изображений, которая работает следующим образом: в исходном состоянии используется конфигурация, описанная в разделе 7.10, с n пикселами, множеством соседних пар, параметрами {a_i}, {b_i} и {p_ij}. Относительно этого экземпляра делаются два предположения. Во-первых, каждый из параметров {a_i}, {b_i} и {p_ij} является неотрицательным целым числом в диапазоне от 0 до d для некоторого числа d. Во-вторых, предполагается, что соседские отношения между пикселами обладают тем свойством, что каждый пиксел является соседом не более чем четырех других пикселов (в полученном графе из каждого узла выходит не более четырех ребер).

Сначала выполняется исходная сегментация (A₀, B₀), максимизирующая величину q(A₀, B₀). В результате исходной сегментации некоторые пикселы могут быть отнесены к фону, хотя пользователь знает, что они должны принадлежать переднему плану. Увидев эту сегментацию на экране, пользователь может щелкнуть мышью на конкретном пикселе v₁, переводя его на передний план. Но программа не ограничивается простым переносом пиксела: вместо этого она должна вычислять сегментацию (A₁, B₁), максимизирующую величину q(A₁, B₁) с учетом того, что v₁ принадлежит переднему плану. (Как это может пригодиться на практике? Допустим, при сегментации фотографии группы людей кто-то держит сумку, которая была ошибочно отнесена к фону. Если щелкнуть на одном пикселе, принадлежащем сумке, и пересчитать оптимальную сегментацию с учетом нового условия, вся сумка станет частью переднего плана).

Система должна дать возможность пользователю провести серию таких щелчков v₁, v₂, ..., v_t; после щелчка v_i система проводит сегментацию (A_i, B_i), максимизирующую величину q(A_i, B_i) в соответствии с условием, что v₁, v₂, ..., v_i находятся на переднем плане.

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

(Примечание: Упражнение с решением 1 из этой главы служит полезным примитивом для этого упражнения. Кроме того, симметричная операция перевода пиксела в фон выполняется аналогично, но здесь вам это делать не нужно.)

36. Рассмотрим еще одну разновидность задачи сегментации изображений из раздела 7.10. Мы разработаем решение задачи разметки изображения, в которой каждый пиксел помечается приблизительной оценкой расстояния от него до камеры (вместо простой разметки “фон/передний план”, использованной в тексте). Допустимые значения меток для каждого пиксела равны 0, 1, 2, ..., M для некоторого целого M.

Пусть G = (V, E) — граф, узлы которого соответствуют пикселам, а ребра обозначают соседние пары пикселов. Разметкой пикселов называется разбиение V на множества A₀, A₁, ..., A_M, где A_k— множество пикселов, помечаемых расстоянием k для k = 0, ..., M. Мы займемся поиском разметки с минимальной стоимостью; стоимость определяется двумя факторами. По аналогии с задачей сегментации “передний план/фон”, имеется стоимость назначения: для каждого пиксела i и метки k стоимость a._k определяет стоимость назначения метки k пикселу i. Затем, если двум соседним пикселам (i, j) ∈ E назначаются разные метки, также действует штраф за разделение. В разделе 7.10 использовался штраф за разделение p_ij; в текущей задаче штраф за разделение также зависит от того, на какое расстояние удаляются пикселы: он пропорционален разности значений двух меток. Таким образом, общая стоимость q' разметки определяется следующим образом:

Целью этой задачи является разработка алгоритма с полиномиальным временем, находящего оптимальную разметку для заданного графа G и параметров штрафов a_i,k и p_ij. Алгоритм будет основан на построении потока в сети; чтобы упростить вашу задачу, мы приведем часть этой схемы.

У потоковой сети имеется источник s и сток t. Кроме того, для каждого пиксела i ∈ V в потоковую сеть включаются узлы v_i,k для k = 1, ..., M, как показано на рис. 7.30 (для M = 5).

Рис. 7.30. Множество узлов, соответствующих одному пикселу i в упражнении 36 (с источником s и стоком t)

Для удобства записи узлы v_i,0 и v_i,M+1 соответствуют s и t соответственно для всех i ∈ V.

Теперь добавим ребра (v_i,k, v_i,k+1) с пропускной способностью a_i,k для k = 0, ..., M; а также ребра (v_i,k+1, v_i,k) в противоположном направлении с очень большой пропускной способностью L. Этот набор узлов и ребер будет называться цепью, связанной с пикселом i.

Обратите внимание: если сделать эту “очень большую” пропускную способность L достаточно большой, то не будет такого минимального разреза (A, B), для которого ребро с пропускной способностью L выходит из множества A. (Насколько большой должна быть эта пропускная способность, чтобы это произошло?) Однако для любого минимального разреза (A, B) и каждого пиксела i в цепи, связанной с i, будет ровно одно ребро с малой пропускной способностью, выходящее из множества A. (Убедитесь в том, что если бы нашлось два таких ребра, то ребро с большой пропускной способностью также должно выходить из множества A.)

И наконец, вопрос: используйте узлы и ребра, определенные выше, для построения потоковой сети, позволяющей эффективно вычислить разметку с минимальной стоимостью по минимальному разрезу s-t. Также докажите, что ваше построение обладает желаемым свойством, и покажите, как восстановить разметку минимальной стоимости по разрезу.

37. В стандартной задаче о минимальном разрезе s-t предполагается, что все пропускные способности неотрицательны; с произвольными сочетаниями положительных и отрицательных пропускных способностей вычислительная сложность задачи заметно усложняется. Однако, как вы сейчас убедитесь, требование неотрицательности можно немного смягчить — и при этом задача по-прежнему будет решаться за полиномиальное время.

Имеется направленный граф G = (V, E) с источником s ∈ V, стоком t ∈ V и пропускными способностями ребер {c_e}. Предположим, для каждого ребра е, у которого ни s, ни t не являются конечной точкой, выполняется условие с_е ≥ 0. Таким образом, c_e может быть отрицательным для ребер е, у которых по крайней мере одним концом является s или t. Предложите алгоритм с полиномиальным временем выполнения для нахождения разреза s-t минимальной величины в таком графе. (Несмотря на новое требования неотрицательности, величина разреза s-t (A, B) по-прежнему определяется как сумма пропускных способностей всех ребер е, для которых начальный узел е принадлежит A, а конечный узел принадлежит B.)

38. Вы работаете с большой базой данных работников. В контексте задачи база данных представляется в виде двумерной таблицы T, состоящей из m строк (множество R) и n столбцов (множество С); строки соответствуют конкретным работникам, а столбцы — разным атрибутам.

Возьмем простой пример: таблица содержит четыре столбца (имя, телефон, дата приема, имя руководителя), и в ней хранятся данные пяти работников.

name	phone number	start date	manager's name
Alanis	3-4563	6/13/95	Chelsea
Chelsea	3-2341	1/20/93	Lou
Elrond	3-2345	12/19/01	Chelsea
Hal	3-9000	1/12/97	Chelsea
Raj	3-3453	7/1/96	Chelsea

Для заданного подмножества S столбцов можно построить новую, уменьшенную таблицу, которая содержит только столбцы из S. Назовем эту новую таблицу проекциейT на S, и обозначим ее T[S]. Например, если S = {name, start date}, то проекцией T[S] будет таблица, состоящая только из первого и третьего столбцов. Другая полезная операция, часто встречающаяся при работе с таблицами, — перестановка столбцов. Для заданной перестановки р новая таблица того же размера, что и T, строится простым переупорядочением столбцов в соответствии с р. Новая таблица называется перестановкой T относительно р и обозначается T_p. Имеются к разных подмножеств столбцов S₁, S₂, ..., S_k; вы собираетесь много работать с ними и поэтому хотите иметь их в удобном легкодоступном формате. Можно сохранить к проекций T[S₁], T[S₂], ..., T[S_k], но они займут слишком много места. Рассматривая возможные альтернативы, вы узнаете, что явное проецирование на каждое подмножество не обязательно, потому что используемая СУБД позволяет особенно эффективно работать со столбцами, если (в некотором порядке) элементы подмножества образуют префикс семейства столбцов в порядке “слева направо”. Например, в нашем примере подмножества {name, phone number} и {name, start date, phone number,} образуют префиксы (первые два и первые три столбца слева соответственно); и это позволяет обрабатывать в этой таблице их намного эффективнее, чем подмножество {name, start date}, не образующее префикс. (Еще раз: для заданного подмножества S. не определен конкретный порядок, и нас интересует, существует ли некоторый порядок, при котором оно образует префикс.)

А теперь вопрос: для заданного параметра l < k возможно ли найти l перестановок столбцов р₁, р₂, ..., р_l, чтобы для каждого из заданных подмножеств S_i (для i = 1, 2, ..., k) столбцы Sобразовали префикс по крайней мере для одной из перестановок столбцов таблицы T_р1, T_р2, ..., T_рl? Такое множество перестановок будет называться действительным решением задачи; если действительное решение существует, это означает, что вам достаточно хранить всего l перестановок таблиц вместо всех k проекций. Предложите алгоритм с полиномиальным временем для решения этой задачи; для экземпляров, для которых существует действительное решение, ваш алгоритм должен возвращать действительное множество из l перестановок.

Пример. Для приведенной выше таблицы заданы подмножества

и l = 2. В этом случае действительное решение существует и достигается двумя перестановками

В этом случае S₁ образует префикс для перестановочной таблицы T_р1, a S₂ и S₃ образуют префиксы для перестановочной таблицы T_р2.

39. Вы консультируете фирму, занимающуюся сбором статистики о параметрах окружающей среды. Фирма собирает статистику и публикует собранные данные в книге. Статистика относится к населению разных регионов и сохраняется в миллионах. Пример такой статистики приведен в следующей таблице.

Страна	A	B	C	Итого
Взрослые мужчины	11,998	9,083	2,919	24,000
Взрослые женщины	12,983	10,872	3,145	27,000
Дети	1,019	2,045	0,936	4,000
Итого	26,000	22,000	7,000	55,000

Для простоты будем считать, что суммы по строкам и столбцам являются целыми числами. Задача округления результатов переписи заключается в округлении всех данных до целых чисел без изменения сумм столбцов и строк. Каждое дробное число может округляться либо в большую, либо в меньшую сторону. Например, хорошее округление данных таблицы может выглядеть так:

Страна	A	B	C	Итого
Взрослые мужчины	11,000	10,000	3,000	24,000
Взрослые женщины	13,000	10,000	4,000	27,000
Дети	2,000	2,000	0,000	4,000
Итого	26,000	22,000	7,000	55,000

(a) Сначала рассмотрите частный случай, когда все данные лежат в диапазоне от 0 до 1. В этом случае имеется матрица дробных чисел от 0 до 1, а задача заключается в округлении каждой дроби до 0 или 1 без изменения сумм строк и столбцов. Для проверки возможности такого округления используйте метод вычисления потока.

(b) Рассмотрите задачу округления результатов переписи в том виде, в котором она определена выше: суммы строк и столбцов являются целыми числами, каждое дробное число α требуется округлить до │α│ или │α│. Для проверки возможности такого округления используйте метод вычисления потока.

(c) Докажите, что округление, которые мы ищем в (a) и (b), существует всегда.

40. В во многих вычислительных задачах можно поставить вопрос о “стабильности” или “надежности” ответа. Подобные вопросы можно задать и о комбинаторных задачах; это один из способов формулировки задачи о минимальном остовном дереве.

Имеется граф G = (V, E) со стоимостью с_е каждого ребра е. Стоимости рассматриваются как величины, которые измерялись экспериментально, и могут содержать возможные ошибки. Следовательно, минимальное остовное дерево, вычисленное для G, может не совпадать с “настоящим” минимальным остовным деревом.

Для заданных параметров е > 0 и k > 0, а также конкретного ребра е' = (u, v), хотелось бы выдвинуть утверждение следующего вида.

(*) Даже если стоимость каждого ребра изменится не более чем на е (с увеличением или уменьшением), а стоимости k ребер, отличных от е', дополнительно заменятся разными произвольными значениями, ребро е' все равно не будет принадлежать никакому минимальному остовному дереву G. Такое свойство предоставляет своего рода гарантию того, что вхождение е' в минимальное остовное дерево маловероятно, даже если предположить значительные ошибки измерений.

Предложите алгоритм с полиномиальным временем, который получает G, е', е и k, и решает, выполняется ли свойство (*) для е'.

41. Допустим, вы управляете группой процессоров и планируете выполнение серии заданий. Задания обладают следующими характеристиками: у каждого задания имеется время поступления a_j, когда оно становится доступным для обработки; длина l_j, которая показывает, какое время потребуется для его выполнения; и предельное время d_j, к которому оно должно быть завершено. Будем считать, что 0 ≤ l_j ≤ d_j – a_j. Каждое задание может выполняться на любых процессорах, но только на одном в любой момент времени; задание может быть приостановлено, а потом продолжено с точки приостановки (возможно, по прошествии некоторого времени) на другом процессоре.

Кроме того, группа процессоров не является полностью статичной: общий пул состоит из к возможных процессоров, но для каждого процессора i существует интервал времени [t_i, t'_i], во время которого он является доступным; во все остальное время процессор недоступен.

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

Пример. Имеются два задания J₁ и J₂. Задание J₁ поступает во время 0, должно быть завершено ко времени 4, и имеет длину 3. Задание J₂ поступает во время 1, должно быть завершено к времени 3 и имеет длину 2. Также доступны два процессора P₁ и P₂. Процессор P₁ свободен в интервале времени от 0 до 4; процессор Р₂ доступен в интервале от 2 до 3. В данном случае существует расписание, позволяющее вовремя выполнить оба задания.

• Во время 0 задание J₁ запускается на процессоре Р₁.

• Во время 1 задание J₁ приостанавливается, и на Р₁ запускается задание J₂.

• Во время 2 выполнение J₁ продолжается на процессоре Р₂. (J₂ продолжает выполняться на P₁.)

• Во время 3 задание J₂ завершается к своему предельному времени. Процессор Р₂ становится недоступным, поэтому задание J₁ перемещается обратно на Р₁ для выполнения завершающего интервала обработки.

• Во время 4 задание J₁ завершается на процессоре Р₁.

Обратите внимание: решения, в котором бы не использовались приостановка и перемещение заданий, не существует.

42. Предложите алгоритм с полиномиальным временем выполнения для следующей минимизирующей аналогии задачи максимального потока: Имеется направленный граф G = (V, Е) с источником s ∈ V, стоком t ∈ V и числами (пропускными способностями) l(v, w) для каждого ребра (v, w) ∈ Е. Мы определяем поток f; как обычно, величина потока требует, чтобы все ребра, кроме s и t, удовлетворяли ограничению сохранения потока. Однако заданные числа определяют нижние границы потока через ребро — то есть они требуют, чтобы f(v, w) ≥ l(v, w) для каждого ребра (v, w) ∈ E, а верхняя граница для величины потока по ребрам отсутствует.

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

(b) Докажите аналогию теоремы о максимальном потоке и минимальном разрезе для этой задачи (то есть равен ли минимальный поток максимальному разрезу?)

43. Вы пытаетесь решить задачу циркуляции, но она не является полностью корректной. В задаче установлены уровни потребления, но отсутствуют ограничения пропускной способности для ребер. Или, говоря более формально, существуют граф G = (F, Е) и уровни потребления d для каждого узла v (удовлетворяющие условию требуется решить, существует ли поток f, для которого f(e) ≥ 0 и fⁱⁿ(v) – f^out(v) = d_v для всех узлов v ∈ V. Обратите внимание: эта задача может быть решена при помощи алгоритма циркуляции из раздела 7.7, с присваиванием c_e = +∞ для всех ребер е ∈ E (или присваиванием с_е чрезвычайно большого числа для каждого ребра — допустим, больше суммы всех положительных уровней потребления d_v в графе).

Требуется исправить граф так, чтобы задача стала корректной, поэтому было бы очень полезно узнать, почему задача некорректна в ее текущей формулировке. При ближайшем рассмотрении вы видите, что существует такое подмножество U узлов, что не существует ребра, входящего в U, но при этом Вы быстро понимаете, что из существования такого множества немедленно следует невозможность существования потока: множество U имеет положительное общее потребление, поэтому ему необходим входящий поток, но в U не входят ребра. Пытаясь понять, насколько эта задача далека от разрешимости, вы задаетесь вопросом, насколько большим может быть потребление множества без входящих ребер.

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

44. Имеется направленная сеть G = (V, E) с корневым узлом r и множеством терминальных узлов T ⊆ V. Нам хотелось бы отсоединить от r как можно больше терминальных узлов, но с разрывом относительно небольшого количества ребер. Этот компромисс будет достигаться следующим образом. Для множества ребер F ⊆ Eq(F) обозначает количество узлов v ∈ T, для которых не существует пути r-v в подграфе (V, E—F). Предложите алгоритм с полиномиальным временем для нахождения множества F ребер, максимизирующего величину q(F) - |F|. (Обратите внимание: множество F может быть пустым).

45. Рассмотрим следующее определение. Имеется множество из n стран, участвующих во взаимной торговле. Для каждой страны имеется значение s. ее бюджетного профицита; это число может быть как положительным, так и отрицательным (отрицательное число указывает на дефицит бюджета). Для каждой пары стран i,j известна общая величина е_ij всего экспорта из i в j; это число всегда неотрицательно. Подмножество стран S называется самостоятельным, если сумма бюджетных профицитов стран S за вычетом общей величины всего экспорта из стран S в страны, в S не входящие, не отрицательна.

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

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

А теперь предположим, что мы ищем по графу G “тесно связанную” группу людей. Один из способов формализации этого понятия выглядит так: для подмножества S узлов e(S) обозначает количество ребер в S — то есть количество ребер, оба конца которых принадлежат S. Определим величину сцепления S как e(S)/|S|. Естественной целью поиска становится множество Sлюдей, для которых достигается максимальное сцепление.

(a) Предложите алгоритм с полиномиальным временем, который получает рациональное число а и определяет, существует ли множество S со сцеплением не ниже α.

(b) Предложите алгоритм с полиномиальным временем, который находит множество S узлов с максимальным сцеплением.

47. Цель этой задачи — изучение разновидностей алгоритма проталкивания предпотока, ускоряющих практическое время выполнения без вреда для сложности в худшем случае. Вспомните, что алгоритм поддерживает свой инвариант: h(v) ≤ h(w) + 1 для всех ребер (v, w) в остаточном графе текущего предпотока. Мы доказали, что если fявляется потоком (а не предпотоком) с этим инвариантом, то этот поток максимален. Высоты возрастали монотонно, а анализ времени выполнения был основан на ограничении возможного количества изменений высот у ребер. Практический опыт показывает,ч то алгоритм почти всегда работает намного быстрее, чем предполагает худший случай, а реальным “узким местом” алгоритма является изменение меток узлов (а не ненасыщающие проталкивания, которые ведут к худшему случаю в теоретическом анализе). Целью приведенной ниже задачи является снижение количества изменений меток посредством увеличения высоты на величину, большую 1. Допустим, имеется граф G с n узлами, m ребрами, пропускными способностями с, источником s и стоком t.

(a) Алгоритм проталкивания предпотока, описанный в разделе 7.4, в начале своей работы назначает поток, равный пропускной способности с_е всех ребер е, выходящих из источника; назначает поток 0 по всем остальным ребрам; присваивает h(s) = n, и h(v) = 0 для всех остальных узлов v ∈ V. Предложите процедуру O(m) для инициализации высот узлов, которая была бы лучше процедуры из раздела 7.4. Ваш метод должен назначать каждому узлу v высоту, максимально возможную для исходного потока.

(b) В этой части мы добавим в алгоритм проталкивания предпотока новый шаг — интервальное изменение меток, в ходе которого метки многих узлов будут увеличиваться более чем на 1. Рассмотрим предпоток f и высоты h, удовлетворяющие инварианту. Пропуском в системе высот называется такое целое число 0 < h < n, что не существует узла с высотой, равной h. Обозначим A множество узлов v с высотами n > h(v) > h. Изменением меток пропусков называется процесс изменения высот всех узлов в A так, чтобы они были равны n. Докажите, что алгоритм проталкивания предпотока с интервальным изменением меток является действительным алгоритмом максимального потока. Заметьте, что единственный новый факт, который нужно доказать — что интервальное изменение меток сохраняет приведенный выше инвариант: h(v) ≤ h(w) + 1 для всех ребер (v, w) в остаточном графе.

(c) В разделе 7.4 мы доказали, что h(v) ≤ 2n - 1 на протяжении алгоритма. В этой модификации выполняется условие h(v) ≤ n. Идея заключается в том, что мы “замораживаем” все узлы при достижении высоты n; другими словами, узлы на высоте n перестают считаться активными, и поэтому не используются для операций push и relabel. В этом случае в конце алгоритма мы имеем функцию предпотока и высоты, которая удовлетворяет приведенному выше инварианту, так что весь избыточный поток находится на высоте n. Пусть B — множество узлов v, для которых существует путь от v к t в остаточном графе текущего предпотока, а A = V — B. Докажите, что в конце алгоритма (A, B) является разрезом s-t с минимальной пропускной способностью.

(d) Алгоритм в части (c) вычисляет минимальный разрез s-t, но не находит максимальный поток (так как завершается на предпотоке, содержащем избыточные потоки). Предложите алгоритм, который получает предпоток f в конце алгоритма из части (c), и преобразует его в максимальный поток за время, не превышающее O(mn). (Подсказка: рассмотрите узлы с избыточным потоком, и попробуйте отправить избыточный поток обратно к s, используя только те ребра, по которым поток поступил.)

48. В разделе 7.4 мы рассмотрели алгоритм проталкивания предпотока, а также обсудили одно конкретное правило выбора вершин. Сейчас будет рассмотрено другое правило выбора. Мы также рассмотрим варианты алгоритма с ранним завершением (и найдем разрез, близкий к минимально возможному).

(a) Пусть f — любой предпоток. Так как f не обязательно является действительным потоком, может оказаться, что величина f^out(s) намного выше величины максимального потока в G. Покажите, что fⁱⁿ(t) является нижней границей для величины максимального потока.

(b) Рассмотрим предпоток f и совместимую разметку h. Вспомните, что множества A = {v : существует путь s-v в остаточном графе G_f} и B = V — A определяют разрез s-t для любого предпотока f, имеющего совместимую разметку h. Покажите, что пропускная способность разреза (А, В) равна

Объединение (а) и (b) позволяет алгоритму завершиться на ранней стадии и вернуть (A, B) как разрез с “приближенно-минимальной” пропускной способностью в предположении, что значение c(A, B) – fⁱⁿ(t) достаточно мало. Далее мы рассмотрим реализацию, которая стремится сократить это значение, пытаясь протолкнуть поток из узлов с большим количеством избыточного потока.

(c) Версия алгоритма проталкивания предпотока с масштабированием поддерживает параметр масштабирования Δ. Изначально Δ присваивается большая степень 2. На каждом шаге алгоритм выбирает узел, у которого избыточный поток не менее Δ, при минимально возможной высоте. Если узлов (кроме t) с избыточным потоком не менее Δ не осталось, алгоритм делит Δ на 2 и продолжает. Обратите внимание: этот алгоритм является действительной реализацией обобщенного алгоритма проталкивания предпотока. Алгоритм выполняется по фазам. Одна фаза продолжается до тех пор, пока значение Δ остается неизменным. В начале алгоритма Δ имеет максимальную пропускную способность, а при его завершении Δ = 1. Следовательно, в ходе выполнения количество фаз масштабирования не превышает O(log C). Покажите, как реализовать эту разновидность алгоритма так, чтобы время выполнения было ограничено O(mn + n log C + K), если алгоритм использует K ненасыщающих операций push.

(d) Покажите, что количество ненасыщающих операций push в предыдущем алгоритме не превышает O(n² log C). Вспомните, что количество фаз масштабирования имеет границу O(log C). Чтобы определить границу количества ненасыщающих операций push в одной фазе масштабирования, рассмотрите потенциальную функцию Как ненасыщающая операция pushвлияет на ф? Какие операции могут привести к увеличению ф?

49. Рассмотрим задачу о распределении: имеется множество из n станций, способных выполнять некую работу, и множество из к заявок на обслуживание (например, станции — вышки сотовой связи, а запросы — сотовые телефоны). Каждый запрос может обслуживаться заданным множеством станций. Задача в таком виде может быть представлена двудольным графом G: одна сторона для станций, другая для клиентов, и клиент x соединяется со станцией у ребром (x, y), если клиент x может обслуживаться станцией у. Будем считать, что каждая станция способна обслуживать не более одного клиента. Используя метод вычисления максимального потока, можно решить, возможно или нет обслужить всех клиентов, или же получить распределение подмножества клиентов по станциям, максимизирующее количество обслуженных клиентов.

В этой задаче рассматривается разновидность задачи с дополнительным усложнением: клиенты предлагают разные суммы денег за обслуживание. Пусть U — множество клиентов, а клиент х ∈U готов заплатить v_x ≥ 0. Требуется найти подмножество X ⊂ U, максимизирующее — такое, что существует распределение клиентов из X между станциями.

Рассмотрим следующий жадный метод: клиенты обрабатываются в порядке убывания “ценности” (с произвольной разбивкой “ничьих”). При рассмотрении клиента x алгоритм либо “обещает” обслуживание х, либо отвергает x по следующему жадному правилу: х добавляется в множество X в том и только в том случае, если существует распределение Х U {x} ПО станциям; в противном случае х отвергается. Помните, что отвергнутые клиенты не будут рассматриваться позднее. (Если уж приходится отвергнуть высокооплачиваемого клиента, по крайней мере ему можно сказать об этом сразу.) При этом распределение принятых клиентов по обслуживающим станциям не осуществляется по жадному принципу: распределение фиксируется только после фиксации множества принятых клиентов. Приведет ли этот жадный подход к оптимальному множеству клиентов? Докажите, что это так, или приведите контрпример.

50. Рассмотрим следующую задачу планирования. Имеются m машин, каждая из которых может обрабатывать задания. Требуется распределить задания между машинами (каждое задание должно быть назначено ровно одной машине) и упорядочить задания на машинах так, чтобы минимизировать функцию стоимости. Машины работают с разной скоростью, но потребности в вычислительных ресурсах у всех заданий одинаковы. В более формальном выражении с каждой машиной i связывается параметр l_i, и выполнение каждого задания потребует времени l_i, если оно будет назначено на машину i.

Количество заданий равно п; все задания требуют одинаковых затрат вычислительных ресурсов, но имеют разные уровни срочности. Для каждого задания j определена функция стоимости c_j(t), которая определяет стоимость выполнения задания j за время t. Предполагается, что стоимости неотрицательны и монотонны по t.

Расписание представляет собой распределение заданий по машинам, и для каждой машины оно определяет порядок выполнения заданий. Задание, назначенное на машину i первым, завершается за время l_i, второе задание — за время l_i и т. д. Пусть для расписания S время завершения задания j в этом расписании обозначается t_S(j). Стоимость такого расписания равна Предложите алгоритм с полиномиальным временем для нахождения расписания с минимальной стоимостью.

51. Вашим друзьям надоела игра “Шесть шагов до Кевина Бэйкона”⁴ (в конце концов, разве это не обычный поиск в ширину?), и они решили изобрести нечто более содержательное с алгоритмической точки зрения. Вот как работает их система.

Все начинается с множества X из n актрис, множества Y из n актеров, и двух игроков Р₀ и P₁. Игрок Р₀ называет актрису x₁ ∈ X; игрок P₁ называет актераy₁, снимавшегося в одном фильме с х₁; игрок Р₀ называет актрису х₂, снимавшуюся в одном фильме с y₁, и т. д. Таким образом, Р₀ и Р₁ совместно строят последовательность х₁, y₁, х₂, y₂, ..., в которой каждый актер/актриса снимается в одном фильме со своим непосредственным предшественником. Игрок P_i (i = 0,1) проигрывает, если в свой ход он не может назвать ни один элемент своего множества, не называвшийся ранее.

Допустим, имеется конкретная пара таких множеств X и Y, с полной информацией: кто, с кем, в каких фильмах снимался. Стратегией для игрока P_i в нашей задаче называется алгоритм, который получает текущую последовательность x₁, y₁, x₂, y₂, ... и генерирует действительный следующий ход для P_i (предполагается, что сейчас ход P_i). Предложите алгоритм с полиномиальным временем, который решает, какой из двух игроков может обеспечить себе победу в конкретном экземпляре игры.

Примечания и дополнительная литература

Концепция сетевых потоков впервые была сформулирована в целостном виде в работе Форда и Фалкерсона (Ford, Fulkerson, 1962). Сейчас сетевые потоки стали самостоятельной областью исследований, по которой можно легко прочитать отдельный учебный курс; например, дополнительную информацию можно найти в обзоре Голдберга, Тардоса и Тарьяна (Goldberg, Tardos, Tarjan, 1990) и книге Ахуджа, Маньянти и Орлина (Ahuja, Magnanti, Orlin, 1993).

Шрайвер (Schrijver, 2002) предоставляет интересную историческую информацию о начальной стадии работы Форда и Фалкерсона над задачей потока. Те из нас, кому всегда казалось, что в задаче минимального разреза присутствует некий деструктивный оттенок, найдут в этой работе подтверждение своей позиции: в ней цитируется недавно рассекреченный отчет ВВС США, из которого следует, что изначально задача нахождения минимального разреза формулировалась для железнодорожной сети Советского Союза, а целью была дезорганизация перевозок.

Как упоминается в тексте, задачи о двудольном паросочетании и непересекающихся путях были сформулированы за несколько десятилетий до задачи о максимальном потоке; только разработка теории сетевых потоков поставила все эти задачи на общую методологическую основу. У теории паросочетаний в двудольных графах было много независимых первооткрывателей; вероятно, чаще других упоминаются П. Холл (Hall, 1935) и Кёниг (Konig, 1916). Задача нахождения путей, непересекающихся по ребрам, от источника к стоку, эквивалентна задаче о максимальном потоке с пропускными способностями, равных 1; этот частный случай был разрешен (фактически в эквивалентной форме) Менгером (Menger, 1927).

Алгоритм проталкивания предпотока был разработан Голдбергом (Goldberg, 1986), а его эффективная реализация разработана Голдбергом и Тарьяном (Goldberg, Tarjan, 1986). Высокопроизводительный код для этого и других алгоритмов сетевого потока можно найти на сайте Эндрю Голдберга.

Алгоритм сегментации изображений с использованием минимальных разрезов был разработан Грейгом, Портеусом и Сехолтом (Greig, Porteous, Seheult, 1989), а применение минимальных разрезов стало играть активную роль в области обработки изображений (например, см. Векслер (Veksler, 1999), Колмогоров и Забих (Kolmogorov, Zahir, 2004)); расширения этого подхода обсуждаются в главе 12. Уэйн (Wayne, 2001) приводит дополнительную информацию о выбывании бейсбольных команд, а также приписывает популяризацию этой задачи в 1960-х годах Алану Хоффману. Другие практические применения сетевых потоков и разрезов рассматриваются в книге Ахуджа, Маньянти и Орлина (Ahuja, Magnati, Orlin, 1993).

Задача нахождения идеального паросочетания с минимальной стоимостью является частным случаем задачи о потоке с минимальной стоимостью, выходящей за рамки материала. Существует несколько эквивалентных формулировок задачи о потоке с минимальной стоимостью; в одной из формулировок дается потоковая сеть с пропускными способностями с_e и стоимостями C_e ребер; стоимость потока f равна сумме стоимостей ребер, взвешенной по величине передаваемого по ним потока, а целью является построение максимального потока с минимальной общей стоимостью. Задача нахождения потока с минимальной стоимостью решается за полиномиальное время, и тоже имеет множество практических применений; алгоритмы для этой задачи обсуждаются в книгах Кука и др. (Cook et al., 1998) и Ахуджа, Маньянти и Орлина (Ahuja, Magnati, Orlin, 1993).

Поток в сети моделирует задачи маршрутизации, которые могут быть сведены к задаче построения разных путей от одного источника к одном стоку, существует более общий (и более общий) класс задач маршрутизации, в котором пути могут одновременно строиться между разными парами отправителей и получателей. Отношения между этими классами задач весьма нетривиальны; эта проблема, а также алгоритмы для более сложных видов задач маршрутизации обсуждаются в главе 11.

Примечания к упражнениям

Упражнение 8 создано на основе задачи, о которой мы узнали от Боба Блэнда; упражнение 16 основано на обсуждении с Уди Манбером; упражнение 26 основано на обсуждении с Джорданом Эренрихом; упражнение 35 основано на обсуждении с Юрием Бойковвым, Ольгой Векслер и Рамином Забихом; упражнение 36 основано на результатах Хироси Исикавы и Дэви Гейгера, а также Бойкова, Векслер и Забиха; упражнение 38 основано на задаче, от которой нам рассказал Эл Демерс; упражнение 46 основано на результатах Пикара и Ратлиффа.

---

¹ Наше понятие потока моделирует трафик, проходящий в сети с постоянной скоростью: величина потока для ребра e обозначается одной переменной f(е). Мы не будем моделировать пульсирующий трафик, при котором поток изменяется со временем.

² В интересном очерке, написанном в 1981 году, Менгер излагает свою версию истории о том, как он объяснял свою теорему Кёнигу, одному из независимых первооткрывателей теоремы Холла. Казалось бы, Кёниг, много размышлявший над подобными задачами, должен был немедленно понять, почему обобщение его теоремы Менгером было истинным — и возможно, даже посчитать его очевидным. Но в действительности все было наоборот: Кёниг не поверил, что теорема истинна, и провел целую ночь в поисках контрпримера. На следующий день, выбившись из сил, он обратился к Менгеру за доказательством.

³ Австрийский ученый Карл Ландштейнер получил Нобелевскую премию в 1930 году за открытие групп крови A, B, AB и O.

⁴ См. https://ru.wikipedia/wiki/Шесть_шагов_до_Кевина_Бэйкона. — Примеч. пер.