MAXimal

добавлено: 2 Mar 2009 17:45
редактировано: 31 Dec 2011 1:57

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

Дан ориентированный ациклический граф G. Требуется покрыть его наименьшим числом путей, т.е. найти наименьшее по мощности множество непересекающихся по вершинам простых путей, таких, что каждая вершина принадлежит какому-либо пути.

Сведение к двудольному графу

Пусть дан граф G с n вершинами. Построим соответствующий ему двудольный граф H стандартным образом, т.е.: в каждой доле графа H будет по n вершин, обозначим их через a_i и b_i соответственно. Тогда для каждого ребра (i, j) исходного графа G проведём соответствующее ребро (a_i, b_j).

Каждому ребру G соответствует одно ребро H, и наоборот. Если мы рассмотрим в G любой путь P = (v_1, v_2, \ldots, v_k), то ему ставится в соответствие набор рёбер (a_{v_1}, b_{v_2}), (a_{v_2}, b_{v_3}), ..., (a_{v_{k-1}}, b_{v_k}) .

Более просто для понимания будет, если мы добавим "обратные" рёбра, т.е. образуем граф \overline H из графа H добавлением рёбер вида (b_i, a_i), i=1 \ldots N. Тогда пути P = (v_1, v_2, \ldots, v_k) в графе \overline H будет соответствовать путь \overline Q = (a_{v_1}, b_{v_2}, a_{v_2}, b_{v_3}, ..., a_{v_{k-1}}, b_{v_k}).

Обратно, рассмотрим любой путь \overline Q в графе \overline H, начинающийся в первой доле и заканчивающийся во второй доле. Очевидно, \overline Q снова будет иметь вид \overline Q = (a_{v_1}, b_{v_2}, a_{v_2}, b_{v_3}, ..., a_{v_{k-1}}, b_{v_k}), и ему можно поставить в соответствие в графе G путь P = (v_1, v_2, \ldots, v_k). Однако здесь есть одна тонкость: v_1 могло совпадать с v_k, поэтому путь P получился бы циклом. Однако по условию граф G ациклический, поэтому это вообще невозможно (это единственное место, где используется ацикличность графа G; тем не менее, на циклические графы описываемый здесь метод вообще нельзя обобщить).

Итак, всякому простому пути в графе \overline H, начинающемуся в первой доле и заканчивающемуся во второй, можно поставить в соответствие простой путь в графе G, и наоборот. Но заметим, что такой путь в графе \overline H — это паросочетание в графе H. Таким образом, любому пути из G можно поставить в соответствие паросочетание в графе H, и наоборот. Более того, непересекающимся путям в G соответствуют непересекающиеся паросочетания в H.

Последний шаг. Заметим, что чем больше путей есть в нашем наборе, тем меньше все эти пути содержат рёбер. А именно, если есть p непересекающихся путей, покрывающих все n вершин графа, то они вместе содержат r = n - p рёбер. Итак, чтобы минимизировать число путей, мы должны максимизировать число рёбер в них.

Итак, мы свели задачу к нахождению максимального паросочетания в двудольном графе H. После нахождения этого паросочетания (см. Алгоритм Куна) мы должны преобразовать его в набор путей в G (это делается тривиальным алгоритмом, неоднозначностей здесь не возникает). Некоторые вершины могут остаться ненасыщенными паросочетанием, в таком случае в ответ надо добавить пути нулевой длины из каждой из этих вершин.

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

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