Решение задачи на теорему Форда-Фалкерсона

Для решения этой задачи воспользуемся теоремой Форда-Фалкерсона, которая гласит, что величина максимального потока в сети равна пропускной способности минимального разреза. 1. Анализ структуры сети: — Исток (левая вершина) имеет три выходящие дуги с пропускными способностями \(4\), \(4\) и \(3\). Суммарная пропускная способность на выходе из истока: \(4 + 4 + 3 = 11\). — Сток (правая нижняя вершина) имеет входящие дуги. Посмотрим на дуги, ведущие непосредственно в область стока. 2. Поиск минимального разреза: Разрез — это множество дуг, удаление которых разделяет исток и сток. Мы ищем разрез с минимальной суммарной пропускной способностью. Проверим различные сечения: — Разрез у самого истока: \(4 + 4 + 3 = 11\). — Разрез у самого стока: в нижнюю правую вершину (сток) входят дуги с весами \(5\) и \(3\) (от нижней средней вершины). Однако, если посмотреть на "узкое горлышко" всей сети: — Рассмотрим дуги, идущие от центральной части к правой: Верхняя дуга (дуга-петля сверху) имеет вес \(2\). Нижняя дуга, ведущая к стоку, имеет вес \(5\). Но они зависят от промежуточных узлов. 3. Расчет максимального потока (равного мин. разрезу): — По нижней ветке: из истока выходит \(3\), идет в нижнюю вершину, оттуда \(3\) идет дальше. Поток \(3\). — По верхней ветке: из истока выходит \(4\), идет в верхнюю вершину. Из нее \(1\) идет в центр и \(3\) идет вправо. — По центральной ветке: из истока выходит \(4\), плюс \(1\) сверху. Итого в центре \(5\). Из центра \(4\) идет вверх и \(1\) вниз. Заметим "узкое место" в правой части графа. Если мы проведем разрез, отделяющий правую часть: — Дуга с весом \(3\) (сверху вправо). — Дуга с весом \(2\) (самая верхняя обводная). — Дуга с весом \(1\) (из центра вниз к стоку). Сумма: \(3 + 2 + 1 = 6\). Проверим еще один вариант разреза: Если отсечь только финальные дуги, входящие в сток, их сумма может быть больше. Но если мы перекроем пути в середине, например, дуги весом \(3\) (верхняя правая) и \(3\) (нижняя правая), то поток не пройдет. Наименьшая сумма пропускных способностей дуг, полностью блокирующая проход от истока к стоку, в данной схеме составляет \(6\). Ответ: d. 6