Решение задачи: Максимальный поток в сети

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