matroid.md

Матроиды

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

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

Определение

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

• Пустое множество является независимым: $\varnothing \in I$

• Любое подмножество независимого множества тоже независимо:

  $$ A \subset B, B \in I \implies A \in I $$

• Если в независимом множестве $A$ меньше элементов, чем в независимом множестве $B$, то будет существовать элемент из $B$, дополняющий $A$ до независимого множества размера $|A|+1$:

  $$ A, B \in I, |A| < |B| \implies \exists x \in B \setminus A: A \cup {x} \in I $$

Матроид называется взвешенным, если на нем есть аддитивная весовая функция: $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)$ является матроидом:

• Граф без ребер является лесом.
• Если удалить из леса ребра, он останется лесом.
• Пусть есть два леса $|A| \leq |B|$. В $A$ будет $|V| - |A|$ компонент связности, в $B$ будет $|V|-|B|$ компонент связности. Так как в $B$ компонент связности меньше, то будет существовать какое-то ребро $x$, связывающее две компоненты связности из $A$. Его и возьмем: $A \cup {x}$ тоже будет лесом, так как $x$ только соединило две разные компоненты связности.

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

Расписания

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

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

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

• Пустой набор заданий всегда можно сделать.
• Если у нас стало меньше заданий, то их сделать мы тоже успеем.
• Пусть есть два правильных набора $|A| \leq |B|$. Тогда в $B$ будет существовать задание $x$ с дедлайном позже $|A|$. Все задания $A$ можно сделать не позже $|A|$-го часа, а в $(|A|+1)$-й час будем делать $x$. Значит, $A \cup x$ — тоже правильный набор.

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

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

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

• Любое паросочетание покрывает пустое множество вершин.
• Исходное паросочетание покрывает также и любое подмножество исходных вершин.
• Пусть есть два множества вершин $|A| \leq |B|$. Раскрасим ребра из паросочетания, соответствующего $A$ в красный цвет, $B$ — в синий, а ребра из обоих паросочетаний — в пурпурный. Рассмотрим граф из красных и синих ребер. Любая компонента связности в нём представляет собой либо путь, либо цикл, состоящий из чередующихся красных и синих ребер. В любом цикле будет равное число красных и синих ребер, а так как всего синих ребер больше, то должен существовать путь, начинающийся и оканчивающийся синим ребром. Поменяем в этом пути красный и синий цвета и сделаем пурпурные ребра обратно красными. Теперь в графе из красных ребер на одно ребро больше, а значит к множеству $A$ добавилась какая-то вершина из левой доли, принадлежавшая ранее $B$.

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

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

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

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

• В пустом множестве нельзя получить какой-либо вектор.
• Подмножество линейно независимого множество тоже линейно независимо: способов набрать вектора стало ещё меньше.
• Пусть есть два линейно независимых множества $A$ и $B$, и $B$ больше. Пусть в нём нельзя выбрать вектор, совместимый с $A$. Тогда получается, что все вектора $B$ можно выразить из $A$. Значит, размерность $B$ уж точно не больше — противоречие.

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

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