Применения максимального потока
Минимальный разрез
Вычисляем максимальный поток.
Далее запускаем из истока 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.
Вычисляем максимальный поток, проверяем, что его величина равна количеству клеток, делённому пополам.