E065. Покрытие путями ориентированного ациклического graphа

Источник: e-maxx.ru/algo, страница PDF 199.

Дан ориентированный ациклический graph

. it is required покрыть его наименьшим numberм путей, т.е. find наименьшее по мощности множество непересекающихся по vertexм простых путей, таких, что каждая vertex принадлежит какому-либо пути.

Сведение к двудольному graphу

Пусть дан graph

с

vertexми. Построим соответствующий ему двудольный graph

стандартным образом, т.е.:

в каждой доле graphа

будет по

вершин, обозначим их через

и

соответственно. Тогда для каждого ребра

исходного graphа

проведём соответствующее edge

.

Каждому ребру

соответствует одно edge

, и наоборот. Если мы рассмотрим в

любой

путь

, то ему ставится в соответствие набор

рёбер

. Более просто для понимания будет, если мы добавим "обратные" рёбра, т.е. образуем graph

из graphа

добавлением рёбер вида

. Тогда пути

в graphе

будет соответствовать путь

.

Обратно, рассмотрим любой путь

в graphе

, начинающийся в первой доле и заканчивающийся во второй

доле. Очевидно,

снова будет иметь вид

, и ему можно поставить

в соответствие в graphе

путь

. Однако здесь есть одна тонкость:

могло совпадать с

, поэтому путь

получился бы циклом. Однако по условию graph

ациклический, поэтому это вообще

невозможно (это единственное место, где используется ацикличность graphа

; тем не менее, на циклические

graphы описываемый здесь метод вообще нельзя обобщить).

Итак, всякому простому пути в graphе

, начинающемуся в первой доле и заканчивающемуся во второй, можно

поставить в соответствие простой путь в graphе

, и наоборот. Но заметим, что такой путь в graphе

—

это паросочетание в graphе

. Таким образом, любому пути из

можно поставить в соответствие

паросочетание в graphе

, и наоборот. Более того, непересекающимся путям в

соответствуют

непересекающиеся паросочетания в

. Последний шаг. Заметим, что чем больше путей есть в нашем наборе, тем меньше все эти пути содержат рёбер. А

именно, если есть

непересекающихся путей, покрывающих все

вершин graphа, то они вместе содержат

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

. После нахождения

этого паросочетания (см. Algorithm Куна) мы должны преобразовать его в набор путей в

(это делается

тривиальным Algorithmом, неоднозначностей здесь не возникает). Некоторые вершины могут остаться ненасыщенными паросочетанием, в таком случае в ответ надо добавить пути нулевой длины из каждой из этих вершин.

Взвешенный случай

Взвешенный случай не сильно отличается от невзвешенного, просто в graphе

на рёбрах появляются веса, и

it is required find уже паросочетание наименьшего веса. Восстанавливая ответ аналогично невзвешенному случаю, мы получим покрытие graphа наименьшим numberм путей, а при равенстве — наименьшим по стоимости.