Покрытие путями и теорема Дилворта

Задача: покрыть все вершины ориентированного ациклического графа минимальным числом путей, не пересекающихся по вершинам. Путь из одной вершины разрешён.

Сведение

Набор непересекающихся путей — это в точности выбор рёбер, при котором у каждой вершины не больше одного преемника и не больше одного предшественника. То есть паросочетание в двудольном графе, где

• левая доля — вершины в роли предшественника,
• правая доля — те же вершины в роли преемника,
• ребро $u \to v$ исходного графа даёт ребро между копиями.

Каждое выбранное ребро склеивает два пути в один. Начали с $n$ путей по одной вершине:

$$\text{путей} = n - |M|.$$

Почему получаются именно пути. Степени в выбранном наборе не больше единицы по входу и по выходу, значит компоненты — пути или циклы. Циклов нет: граф ациклический. Ацикличность здесь существенна — в графе с циклами то же построение даёт покрытие путями и циклами, а это другая задача.

Если пути могут пересекаться

Тогда сначала строится транзитивное замыкание: ребро $u \to w$ проводится всюду, где $w$ достижима из $u$. После этого задача решается как обычная.

Замыкание считается в обратном топологическом порядке битовыми масками:

for (int i = n - 1; i >= 0; i--) {
    int u = order[i];
    for (int v : outgoing[u]) {
        reach[u].set(v);
        reach[u] |= reach[v];
    }
}

Это $O(nm / 64)$ вместо $O(n^3)$ у Флойда.

Теорема Дилворта

Транзитивно замкнутый ациклический граф — это частично упорядоченное множество, пути в нём — цепи, а набор попарно несравнимых элементов — антицепь.

Теорема Дилворта. Минимальное число цепей, покрывающих множество, равно размеру максимальной антицепи.

Одна сторона простая: антицепь и покрытие цепями пересекаются не более чем по одному элементу на цепь, поэтому цепей не меньше. Обратная сторона доказывается тем же построением через паросочетание, поэтому

$$|\text{максимальная антицепь}| = n - |M|.$$

Это даёт бесплатный способ проверить себя: на маленьких тестах антицепь ищется перебором.

Где это встречается

задача	порядок
минимум машин на список заказов	«после заказа $i$ успеваем на заказ $j$»
минимум стопок из вложенных коробок	строгое вложение
минимум моек посуды между блюдами	включение множеств компонентов
разбиение последовательности на возрастающие	сравнение по индексу и значению

Общий признак: в условии есть отношение «одно можно делать сразу после другого», и спрашивают минимальное число последовательностей.