Матроиды

Матроиды

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

Если вы не специалист по абстрактной алгебре, рекомендуется подсматривать примеры матроидов в конце статьи.

Определение

Матроидом называется пара \((X, I)\), где \(X\) — множество элементов, называемое носителем матроида, а \(I\) — некоторое множество подмножеств \(X\), называемое семейством независимых множеств. В матроиде должны выполняться следующие свойства:

Матроид называется взвешенным, если на нем есть аддитивная весовая функция: \(w(A) = \sum w(a_i)\).

Алгоритм Радо-Эдмондса

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

X.sort()
s = []
for x in X:
    if good(s + [x]):
        s += [x]

Здесь под good имеется в виду \(s \cup x \in I\).

Корректность этого алгоритма для произвольного матроида следует из следующего утверждения:

Теорема Радо-Эдмондса. Пусть \(A \in I\) — множество минимального веса среди всех независимых подмножеств \(X\) мощности \(k\). Возьмем \(x: A \cup x \in I,\;x \notin A,\;w(x)\) — минимальна. Тогда \(A \cup x\) — множество минимального веса среди независимых подмножеств \(X\) мощности \(k + 1\).

Доказательство:

Рассмотрим \(B\) — множество минимального веса среди независимых подмножеств \(X\) мощности \(k + 1\).

Из свойств матроида: \(\exists y \in B \setminus A : A \cup y \in I\).

Тогда верны два неравенства:

\[ \begin{cases} w(A \cup y) = w(A) + w(y) \geq w(B) \implies w(A) \geq w(B) - w(y) \\ w(B \setminus y) = w(B) - w(y) \geq w(A) \implies w(A) \leq w(B) - w(y) \end{cases} \]

Величина \(w(A)\) с двух сторон ограничивает величину \(w(B) - w(y)\). Значит, они равны. Cледовательно, \(w(A \cup y) = w(A) + w(y) = w(B)\).

Получаем, что если объединить множество \(A\) с \(x\) — минимальным из таких, что \(A \cup x \in I\), — то получим множество минимального веса среди независимых подмножеств \(X\) мощности \(k + 1\).

Иными словами, если у нас есть оптимальное \(k\)-элементарное независимое множество, то мы можем индуктивно построить оптимальное \((k+1)\)-элементарное множество, добавив к нему минимальный элемент, оставляющий построенное множество независимым.

Примеры

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

Минимальный остов

Рассмотрим неориентированный граф \(G = (V, E)\). Пусть \(I\) — множество лесов графа (ациклических подмножеств \(E\)). Тогда \(M = (E, I)\) является матроидом:

Применив к этому матроиду теорему Радо-Эдмондса, мы получаем обоснование алгоритма Крускала для нахождения минимального остова.

Расписания

Пусть у нас есть \(n\) заданий, на выполнение каждого требуется \(1\) час. Награда за выполнение \(i\)-го задания не позже \(d_i\)-того часа равна \(w_i\). В один час разрешено сделать только одно задание. Цель — максимизировать сумму наград.

Назовём правильными те наборы заданий, для которых существует порядок, при котором можно их всех успеть сделать до их дедлайнов. Проверять фиксированый набор можно так: отсортировать по дедлайнам (\(d_i\)) и проверить, что \(d_i \geq i\) для всех \(i\).

Тогда \(M =\) (множество всех заданий, множество правильных наборов заданий) является матроидом:

Значит, можно отсортировать задания по убыванию их стоимости и пытаться в таком порядке добавлять в ответ, проверяя правильность какой-нибудь структурой данных.

Паросочетания

Рассмотрим двудольный граф \(G = (L, R, E)\). Пусть \(I\) — множество наборов вершин левой доли, которых можно покрыть каким-нибудь паросочетанием. Тогда \(M = (L, I)\) является матроидом:

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

Линейно независимые вектора

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

Рассмотрим какое-то множество векторов \(V\). Пусть \(I\) — множество всех его линейно независимых подмножеств. Тогда \(M = (V, I)\) является матроидом:

Пример задачи: набрать базис максимального веса, если каждый вектор сколько-то стоит.

Примечание: \(Z_2\) — это тоже пространство, и там тоже можно ввести линейную независимость. Это значит, что то же самое распространяется на задачи в духе «набрать максимальное множество чисел, из которых ксором нельзя получить ноль».