Применения максимального потока

Минимальный разрез

Вычисляем максимальный поток.

Далее запускаем из истока dfs, который идёт только по рёбрам с ненулевой остаточной пропускной способностью.

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

Максимальное паросочетание в двудольном графе

Строим сеть: (исток), (количество вершин первой доли), (количество вершин второй доли), (сток).

Соединяем исток со всеми вершинами первой доли рёбрами пропускной способности 1.

Соединяем вершины первой доли с вершинами второй доли рёбрами пропускной способности 1, если соответствующее ребро было в исходном графе.

Соединяем все вершины второй доли со стоком рёбрами пропускной способности 1.

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

Количество рёберно-непересекающихся путей между a и b

Считаем, что рёбра исходного графа имеют пропускную способность 1.

Вычисляем максимальный поток из a в b, его величина равна ответу.

Количество вершинно-непересекающихся путей между a и b

Ставим в соответствие каждой вершине исходного графа две вершины («входную» и «выходную»), соединённые ребром пропускной способности 1.

Если в исходном графе было ребро (x → y), до добавляем ребро (выход_x → вход_y) пропускной способности 1.

Вычисляем максимальный поток из выход_a в вход_b, его величина равна ответу.

Есть ли путь из a в b и из b в c, не проходящий по одному ребру дважды

Считаем, что рёбра исходного графа имеют пропускную способность 1.

Соединяем a и c со стоком рёбрами пропускной способности 1, вычисляем максимальный поток между b и стоком, проверяем, что его величина равна 2.

Можно ли замостить заданную клетчатую фигуру костями домино 1 × 2

Мысленно раскрашиваем клетки фигуры в шахматном порядке. Строим сеть: (исток), (количество белых клеток), (количество чёрных клеток), (сток).

Соединяем исток со всеми белыми клетками рёбрами пропускной способности 1.

Соединяем белые клетки с соседними чёрными клетками рёбрами пропускной способности 1.

Соединяем все чёрные клетки со стоком рёбрами пропускной способности 1.

Вычисляем максимальный поток, проверяем, что его величина равна количеству клеток, делённому пополам.

Ссылки

• Erickson J. — Applications of Flows and Cuts
• neerc.ifmo.ru — Примеры сведения к задачам поиска потока