Матроиды

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

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

#Определение

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

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

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

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

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

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

Величина $w(A)$ с двух сторон ограничивает величину $w(B) - w(y)$. Значит, они равны. Следовательно, $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$ — это тоже пространство, и там тоже можно ввести линейную независимость. Это значит, что то же самое распространяется на задачи в духе «набрать максимальное множество чисел, из которых ксором нельзя получить ноль».