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

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

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

Далее запускаем из истока 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.

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

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

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

• e-maxx.ru — Покрытие путями ориентированного ациклического графа

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

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

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

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

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

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

Покрыть заданную клетчатую фигуру минимальным количеством костей домино 1 × 2

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

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

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

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

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

Закрасить клетки сетки так, чтобы в i-й строке было закрашено r[i], а в j-м столбце — c[j]

Строим сеть: (исток), (количество строк), (количество столбцов), (сток).

Соединяем исток со всеми вершинами второго слоя рёбрами пропускной способности r[i].

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

Соединяем все вершины третьего слоя со стоком рёбрами пропускной способности c[j].

Вычисляем максимальный поток, проверяем, что его величина равна сумме r (и сумме c). Клетки, которые нужно закрасить, соответствуют рёбрам между вторым и третьим слоями, по которым идёт поток.

(Также существует более простое жадное решение)

Покрыть закрашенные клетки сетки минимальным количеством горизонтальных и вертикальных линий

Строим сеть: (исток), (количество строк), (количество столбцов), (сток).

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

Соединяем i-ю вершину второго слоя с j-й вершиной третьего слоя рёбром пропускной способности 1, если клетку [i][j] нужно покрыть.

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

Вычисляем максимальный поток, количество линий равно его величине. Через какие строки и столбцы проводить линии, определяется минимальным вершинным покрытием.

Ссылки

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