Эта страница содержит различные исправленные упражнения о проблемах с максимальным расходом. Эти задачи используют в основном Форд-Фулкерсон алгоритм и решение минимального разреза.

Упражнение 1

Используя метод Форда-Фалкерсона, вычислите максимальный поток в следующей сети:

исправлены упражнения о проблемах с максимальным расходом

Упражнение 2

На рисунке ниже показана сеть потока, на которой показан поток st. Емкость каждого ребра отображается в виде метки рядом с ребром, а числа в полях показывают объем потока, отправляемого на каждое ребро. (Ребра без номеров в рамке не имеют передаваемого по ним потока.) Каково значение этого потока? Является ли это максимальным потоком st на этом графике? Если нет, найти максимальный поток st. Найдите минимальный разрез st. (Укажите, какие вершины принадлежат множествам разреза.)

исправлены упражнения о проблемах с максимальным расходом

Значение этого потока равно 17. Нет, это не максимальный поток. Мы можем найти максимальный поток, взглянув на остаточную сеть. В этом случае из заданного потока мы можем получить максимальный поток только с одним увеличивающим путем, szyxwt. Таким образом, максимальный поток имеет значение 19.

Мы можем найти минимальный разрез, используя остаточную сеть для окончательного максимального потока. Начиная с s, найдите все вершины, достижимые из s в остаточной сети. Это формирует один комплект в минимальном разрезе. Остальные вершины образуют другую заданную часть разреза. Таким образом, минимальным разрезом в этом случае являются два множества {s; г} и {х; ш; у; т}.

Можно проверить, что пропускная способность этого разреза (т. е. суммарная пропускная способность ребер от {s; z} до {x; w; y; t}, состоящая из направленных ребер (s; w); (s; x) ; (z; y) и (z; t) равно 19, как гарантирует теорема о максимальном потоке/минимальном разрезе.

Упражнение 3

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

Предположим, что ребро от u до v увеличивает свою пропускную способность на единицу. Из предыдущего максимального потока F просто сделайте новую итерацию алгоритма Форда-Фалкерсона с измененным графом: Граф остаточного потока увеличивает пропускную способность ребра (u; v) на единицу. Выполните поиск графа, чтобы увидеть, есть ли какой-либо путь в графе остаточного потока, по которому поток может увеличиться. Если он есть, то должен быть и поток размера один (поскольку все потоки являются целыми числами). Если на графике остаточного потока нет потока, F по-прежнему является максимальным потоком.

Предположим, что ребро от u до v уменьшает свою пропускную способность на единицу. Если предыдущий максимальный поток F не использовал полную мощность (u; v), такое изменение вообще не засчитывается. В противном случае мы обновляем поток следующим образом:

Поскольку поток, входящий в u, на одну единицу больше, чем поток, выходящий из него, а поток, входящий в v, на одну единицу меньше, чем поток, выходящий из него, мы никоим образом не должны передавать единичный поток из u в v. Таким образом, ищем в остаточном графе потока путь из u в v, по которому поток может увеличиться на единицу. Если такой путь есть, мы обновляем F потоком.

Если такого пути нет, мы должны уменьшить поток из s в u и из v в t на одну единицу. Мы делаем это, находя путь от u до s в графе остаточного потока, вдоль которого поток может увеличиться на единицу, и путь от t до v, вдоль которого поток может увеличиться на единицу. (Такие пути должны быть, потому что у нас был поток из s в t через (u; v).) Затем обновите F этими двумя потоками.

Упражнение 4

Учитывая следующий поток, как увеличить поток?

исправлены упражнения о проблемах с максимальным расходом

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

Упражнение 5

В двудольном графе вершины T1 … T6 представляют рабочих, а вершины E1 … E6 представляют рабочие места. Ребро связывает работника с должностью, если у работника есть необходимая квалификация для занятия этой должности. Как распределить рабочие места между работниками, чтобы свести к минимуму количество безработных?

исправлены упражнения о проблемах с максимальным расходом

Назначить работу человеку равнозначно «выбрать» ребро. Ti подключены к фиктивному источнику мощностью 1 (то же самое для Ei к фиктивному приемнику). Ребра двудольного графа имеют пропускную способность 1. Затем выполняется поиск максимального потока.

исправлены упражнения о проблемах с максимальным расходом

Упражнение 6

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

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

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

Существует множество статей A и множество рецензентов B. Добавьте к графу направленное ребро (α,β), если некоторая статья α в A может быть рецензирована некоторым рецензентом β в B, а именно статья посвящена теме, в которой рецензент является экспертом. Установите пропускную способность этого ребра равной 1. Добавьте вершину s (источник) и вершину t (терминал). Для каждого α в A добавьте ребро (s, α) пропускной способности mA. Для каждого β в B добавьте ребро (β , t) пропускной способности mB. Запустите алгоритм Форда-Фалкерсона, чтобы получить максимальный поток, и вычислите соответствующий разрез (A,B). Это дает набор ребер, которые соответствуют назначению статей рецензентам.

Упражнение 7

Пусть - набор машин и задач. А-машина Lя можно использовать не болеея время. Задача Ся можно использовать не более bя время. Таблица спроса и предложения представляет машины и задачи, а также возможность выполнения задачи на данной машине (пусто).

исправлены упражнения о проблемах с максимальным расходом

Создайте машины/задачи с двудольным графом, а затем создайте фиктивный источник (фиктивный приемник) с пропускной способностью дуги a.я (и бя). Затем решите задачу о потоке.

исправлены упражнения о проблемах с максимальным расходом

Делиться
ru_RURU