Матроиды

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

Матроидом называется пара $(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)$.

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

In [ ]:
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$.

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

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

(TODO) (Школьники не обязаны знать линал.)

Такие штуки будем называть базисами.

  • Ноль есть в любом базисе.
  • Подмножество базиса — базис.
  • ??? Пусть нельзя выбрать новый вектор. Получается, что все вектора $B$ лежат в $A$. Значит, размерность $B$ уж точно не больше.