Что такое матроид: определение, примеры, жадный алгоритм

Матроид — это конечное множество $E$ вместе с семейством его подмножеств $\mathcal{I}$, удовлетворяющим трём условиям:

Множества из $\mathcal{I}$ называются независимыми.

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

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

Именно аксиома (I3), аксиома обмена, делает матроиды особенно интересными. Она утверждает: если есть два независимых множества разного размера, то меньшее всегда можно увеличить хотя бы одним элементом из большего, сохранив независимость.

Уитни ввёл матроиды в 1935 году, чтобы выделить общую структуру, скрывающуюся за линейной независимостью в матрицах и отсутствием циклов в графах. Даже название matroid исторически связано со словом matrix.

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

Определение

Формально матроид — это пара $M = (E, \mathcal{I})$, где $E$ — конечное множество, называемое носителем матроида, а $\mathcal{I} \subseteq 2^E$ — семейство его независимых множеств.

Условия (I1)–(I3) называются аксиомами независимости.

Аксиома (I1) говорит, что пустое множество независимо.

Аксиома (I2) выражает наследственность: если некоторое множество независимо, то любое его подмножество также независимо.

Именно (I3) отличает матроид от произвольной наследственной системы: если независимое множество $A$ меньше независимого множества $B$, в $B$ обязательно найдётся элемент, которым можно пополнить $A$.

(I1) и (I2) выполняются почти в любой разумной задаче: не брать ничего — допустимо, а выбросить элемент из допустимого набора никогда не вредит. Поэтому на практике вся проверка сводится к (I3).

Из этих трёх аксиом возникает практически вся основная терминология теории матроидов.

Зависимое множество — подмножество носителя, которое не является независимым.

Цикл матроида — минимальное по включению зависимое множество. Иными словами, само оно зависимо, но после удаления любого его элемента становится независимым. В графическом матроиде циклы матроида в точности соответствуют обычным циклам графа.

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

База — максимальное по включению независимое множество. Из аксиомы обмена следует, что все базы одного матроида имеют одинаковую мощность. Если бы существовали две базы $A$ и $B$ с $|A| < |B|$, аксиома (I3) позволила бы добавить к $A$ элемент из $B$, а значит, $A$ не была бы максимальной.

Ранг $r(A)$ множества $A \subseteq E$ — мощность наибольшего независимого подмножества, содержащегося в $A$. В частности, $r(E)$ называется рангом матроида и равен мощности любой его базы.

Перешеек, или копетля, — элемент, содержащийся в каждой базе. Для графического матроида таким элементам соответствуют мосты графа.

Двойственный матроид $M^*$ имеет тот же носитель $E$, а его базами служат дополнения баз исходного матроида: $B^* = E \setminus B$. Поэтому $r^*(E) = |E| - r(E)$. Двойственный к графическому матроиду называется кографическим матроидом, или матроидом разрезов.

Прямая сумма $M_1 \oplus M_2$ матроидов на непересекающихся носителях $E_1$ и $E_2$ устроена так: множество независимо тогда и только тогда, когда его часть в $E_1$ независима в $M_1$, а часть в $E_2$ — в $M_2$. Ранги при этом складываются: $r(M_1 \oplus M_2) = r(M_1) + r(M_2)$.

Удаление элемента $e$, обозначаемое $M \setminus e$ (иначе — сужение на $E \setminus \{e\}$), просто оставляет независимые множества, не содержащие $e$.

Стягивание элемента $e$, обозначаемое $M / e$, для элемента, не являющегося петлёй, задаётся так: множество $A \subseteq E \setminus \{e\}$ независимо в $M / e$, если $A \cup \{e\}$ независимо в $M$.

Удаления и стягивания можно повторять. Получающиеся таким образом матроиды называются минорами исходного матроида.

Два матроида называются изоморфными, если между их носителями существует взаимно однозначное соответствие, сохраняющее независимость.

Пример 1: графический матроид

Пусть дан граф $G = (V, E)$.

Возьмём его множество рёбер $E$ в качестве носителя матроида и объявим набор рёбер независимым, если он не содержит цикла. Иными словами, независимые множества — это леса.

Получаем графический, или циклический, матроид графа.

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

Если связный граф имеет $n$ вершин, то $r(E) = n - 1$. И это не отдельное свойство деревьев, случайно совпавшее с теорией матроидов. Оно является прямым следствием аксиомы обмена: все базы имеют одну мощность, а базы графического матроида — именно остовные деревья.

Кликайте по рёбрам, чтобы собрать множество: панель находит цикл, если он есть, и показывает ранг. Кнопка «жадный алгоритм» сортирует рёбра по весу и запускает алгоритм Краскала; «шаг» берёт по одному ребру и говорит, взято оно или замкнуло бы цикл.

Теперь назначим каждому ребру вес.

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

Краскал работает не благодаря специальному трюку с графами. Он является частным случаем общего жадного алгоритма на матроиде.

Пример 2: линейный матроид

Пусть носитель состоит из столбцов некоторой матрицы над полем $F$.

Назовём множество столбцов независимым тогда и только тогда, когда соответствующие векторы линейно независимы.

Получившаяся структура называется линейным матроидом. Если матроид можно получить таким образом из некоторой матрицы над полем $F$, говорят, что он представим над $F$.

Это один из исходных примеров теории матроидов.

Графический матроид представим над любым полем. Для ориентированного графа можно взять его матрицу инцидентности «вершина — ребро», где каждому ребру соответствует столбец с $+1$ у одного конца и $-1$ у другого. Над полем $\mathrm{GF}(2)$, где $1 = -1$, обе ненулевые записи равны единице.

Набор таких столбцов линейно независим тогда и только тогда, когда соответствующие рёбра не содержат цикла.

Матроид, представимый над любым полем, называется регулярным. Таким образом, графические $\subsetneq$ регулярные $\subsetneq$ представимые, и оба включения строгие.

В линейном матроиде особенно наглядны петли и циклы. Нулевой вектор является петлёй. Два ненулевых пропорциональных вектора образуют двухэлементный цикл. В двумерном пространстве любое минимально зависимое множество из трёх попарно непропорциональных векторов образует трёхэлементный цикл.

Пример 3: однородный матроид U(k,n)

Однородный, также называемый равномерным, матроид $U_{k,n}$ имеет $n$ элементов, а независимыми объявляются в точности подмножества мощности не более $k$:

Его базы — все $k$-элементные подмножества. Циклы — все $(k+1)$-элементные подмножества. Ранг равен $k$.

Например, в $U_{1,n}$ можно выбрать не более одного элемента. Любые два элемента уже образуют цикл.

В $U_{n,n}$ независимо любое подмножество. Такой матроид называется свободным.

Особенно важен $U_{2,4}$. У него четыре элемента; любые один или два элемента независимы, а любое трёхэлементное множество зависимо. Это простейший матроид, не представимый над полем $\mathrm{GF}(2)$.

Знаменитая теорема Татта утверждает: матроид представим над $\mathrm{GF}(2)$, то есть является бинарным, тогда и только тогда, когда он не содержит $U_{2,4}$ в качестве минора.

Пример 4: матроид разбиения — таможня

Представим, что вы проходите через таможню.

Все вещи разделены на категории: например, алкоголь, сигареты, электроника и сыр. Правило гласит: можно взять не более одного предмета каждой категории.

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

Почему это матроид?

Пустая сумка допустима — выполняется (I1).

Если из допустимой сумки что-нибудь убрать, она останется допустимой — выполняется (I2).

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

Соответствующий предмет можно перенести из $B$ в $A$, не нарушив правила. Следовательно, выполняется и (I3).

Получился матроид разбиения.

Вообще носитель можно разбить на блоки $E = E_1 \sqcup E_2 \sqcup \cdots \sqcup E_m$ и задать для каждого блока вместимость $k_i$. Независимы тогда множества $A$, для которых $|A \cap E_i| \le k_i$ для каждого $i$.

Такой матроид является прямой суммой однородных матроидов $U_{k_i,|E_i|}$. В нашем таможенном примере $k_i = 1$ для всех категорий.

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

Теперь изменим всего одно правило: общий вес багажа не должен превышать 23 кг.

Пусть $A = \{$один предмет массой 20 кг$\}$, а $B = \{$два предмета по 10 кг$\}$. Тогда $|A| < |B|$. Однако ни один элемент $B$ нельзя добавить к $A$: получилось бы 30 кг.

Следовательно, аксиома обмена нарушается. Это уже не матроид, а ограничение типа рюкзака.

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

Одна сумка, два почти одинаково выглядящих правила — и совершенно разная математика.

«Не более одного предмета каждой категории» образует матроид.

«Не более 23 кг суммарно» — не образует.

Именно аксиома обмена позволяет увидеть эту разницу до запуска алгоритма.

Точки и прямые: матроид ранга 3

Матроиды можно строить не только из векторов или рёбер.

Рассмотрим конечный набор точек на плоскости и объявим множество точек независимым в смысле аффинной независимости.

Одна точка независима. Любые две различные точки независимы. Три точки независимы тогда и только тогда, когда они не лежат на одной прямой. Четыре точки на плоскости всегда аффинно зависимы.

Поэтому такой матроид имеет ранг не более 3.

Если три точки лежат на одной прямой и никакая их собственная часть не зависима, эта тройка образует цикл матроида.

Изменяя взаимное расположение точек, можно тем самым менять сам матроид: появление новой коллинеарной тройки создаёт новый цикл. Перетаскивайте точки и следите за счётчиком прямых.

Однако далеко не каждый матроид ранга 3 можно реализовать точками обычной вещественной плоскости.

Классический пример — матроид Фано. Он состоит из семи элементов с семью специальными тройками-циклами и представим линейно только над полями характеристики 2. В частности, над $\mathbb{R}$ представить его невозможно.

Аксиома обмена в действии

Теперь видно, почему (I3) занимает центральное место.

Прежде всего она немедленно доказывает, что все базы матроида имеют одинаковую мощность.

Предположим, что $A$ и $B$ — две максимальные независимые системы и $|A| < |B|$. По (I3) существует элемент $e \in B \setminus A$, для которого $A \cup \{e\}$ остаётся независимым. Но тогда $A$ не было максимальным. Противоречие.

Следовательно, жадный алгоритм не может оказаться в ситуации, когда он «застрял» в маленьком максимальном независимом множестве, хотя где-то существует более крупное.

Соберите на графе два независимых множества $A$ и $B$. Как только $|A| < |B|$, панель ищет в $B \setminus A$ ребро, которое можно добавить к $A$, не замкнув цикл, — аксиома обещает, что такое всегда найдётся.

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

Пусть существуют независимые множества $A$ и $B$, такие что $|A| < |B|$, но ни один элемент из $B \setminus A$ нельзя добавить к $A$.

Назначим каждому элементу $A$ вес $1 + \varepsilon$, каждому элементу $B \setminus A$ — вес $1$, а всем прочим элементам — вес $0$.

Жадный алгоритм сначала предпочитает элементы $A$. После того как он набрал $A$, ни один новый элемент из $B \setminus A$ добавить уже невозможно. Он получает вес $|A|(1+\varepsilon)$.

В то же время $B$ имеет вес как минимум $|B| \ge |A| + 1$. Если выбрать $0 < \varepsilon < 1/|A|$, то

Значит, $B$ лучше жадного решения. Нарушение одной аксиомы автоматически породило контрпример для greedy.

Почему алгоритм Краскала работает: жадный алгоритм и матроиды

Рассмотрим общую задачу.

Каждому элементу конечного множества назначен неотрицательный вес. Требуется выбрать независимое множество максимального суммарного веса.

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

Никакого перебора. Никакого возврата назад. Никакого динамического программирования.

Когда эта процедура гарантированно даёт оптимум?

Ответ даёт теорема Радо—Эдмондса.

Теорема Радо—Эдмондса. Пусть $\mathcal{I}$ — непустое семейство подмножеств конечного множества $E$, замкнутое относительно взятия подмножеств. Тогда жадный алгоритм находит независимое множество максимального веса для любого назначения неотрицательных весов тогда и только тогда, когда $(E, \mathcal{I})$ является матроидом.

Слева — леса, то есть матроид; справа — паросочетания, которые матроидом не являются. «Шаг» продвигает обе стороны на один элемент.

Это очень сильное утверждение.

Прямое направление говорит: если допустимые множества образуют матроид, нам не нужно отдельно доказывать корректность жадного алгоритма для каждого нового набора весов. Структура задачи уже гарантирует оптимальность.

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

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

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

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

Доказательство теоремы Радо—Эдмондса

Обратное направление мы уже фактически доказали.

Если аксиома обмена нарушается, существуют $A$ и $B$, для которых $|A| < |B|$ и ни один элемент $B \setminus A$ нельзя добавить к $A$. Весовая конструкция с $1 + \varepsilon$ на $A$ и $1$ на $B \setminus A$ заставляет greedy выбрать $A$, хотя $B$ имеет больший суммарный вес.

Остаётся доказать прямое направление.

Пусть жадный алгоритм выбрал элементы $g_1, g_2, \ldots, g_r$ в таком порядке, что $w(g_1) \ge w(g_2) \ge \cdots \ge w(g_r)$. Обозначим полученную базу через $G = \{g_1, \ldots, g_r\}$.

Пусть $O = \{o_1, \ldots, o_r\}$ — оптимальная база, элементы которой также упорядочены по невозрастанию веса: $w(o_1) \ge w(o_2) \ge \cdots \ge w(o_r)$.

Мощности совпадают. Жадный алгоритм останавливается только на максимальном независимом множестве, то есть на базе; при неотрицательных весах оптимум тоже можно считать базой — дополнение элементами нулевого веса вес не уменьшает; а по аксиоме обмена все базы равномощны.

Покажем, что для каждого $i$ выполнено $w(g_i) \ge w(o_i)$.

Предположим противное и возьмём первый индекс $i$, для которого $w(g_i) < w(o_i)$.

Рассмотрим $A = \{g_1, \ldots, g_{i-1}\}$ и $B = \{o_1, \ldots, o_i\}$.

Оба множества независимы: первое является частью жадной базы, второе — частью оптимальной базы. Кроме того, $|A| = i - 1 < i = |B|$.

По аксиоме обмена существует $o_j \in B \setminus A$ такой, что $A \cup \{o_j\}$ независимо.

Поскольку $j \le i$, имеем $w(o_j) \ge w(o_i) > w(g_i)$. Следовательно, жадный алгоритм рассмотрел $o_j$ раньше, чем $g_i$.

В тот момент уже выбранные элементы образовывали некоторое подмножество $A$. Поскольку $A \cup \{o_j\}$ независимо, по наследственности независимо и это более раннее подмножество вместе с $o_j$.

Значит, алгоритм должен был принять $o_j$. Тогда к моменту выбора $g_i$ элемент $o_j$ уже принадлежал бы $A$. Но мы выбрали $o_j \in B \setminus A$. Противоречие.

Следовательно, $w(g_i) \ge w(o_i)$ для каждого $i$, а значит, $w(G) \ge w(O)$.

Жадное решение оптимально. $\blacksquare$

Всё доказательство держится практически на одном применении аксиомы обмена.

В этом и заключается точный математический смысл фразы: матроид — это структура, на которой жадный алгоритм работает универсально.

Другие классы матроидов

Матроид трансверсалей, или трансверсальный матроид. Пусть задан двудольный граф между элементами носителя $E$ и некоторым набором «мест». Подмножество $A \subseteq E$ независимо, если его элементы можно сопоставить различным местам посредством паросочетания. Такие частичные трансверсали образуют матроид (Эдмондс и Фалкерсон, 1965).

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

Алгебраический матроид. Пусть $K \supseteq F$ — расширение полей, а $E$ — конечное множество элементов $K$. Подмножество $E$ независимо, если его элементы алгебраически независимы над $F$. Линейные матроиды являются частным случаем алгебраических, но существуют алгебраические матроиды, не имеющие линейного представления ни над каким полем.

Прямая сумма. Если матроиды определены на непересекающихся носителях, их можно объединить независимо друг от друга. Ранги складываются. Матроид, который нельзя нетривиально представить как прямую сумму, называется связным. Каждый конечный матроид единственным образом раскладывается на связные компоненты.

Объединение матроидов. Пусть $M_1, \ldots, M_k$ заданы на одном носителе. Множество называется независимым в их объединении, если его можно разбить на части так, чтобы $i$-я часть была независима в $M_i$. Теорема об объединении матроидов утверждает, что результат снова является матроидом.

Именно эта конструкция лежит за задачами вида «можно ли разбить множество рёбер на $k$ лесов?» — точный ответ на него дал Нэш-Уильямс.

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

Кографический матроид графа сам является графическим тогда и только тогда, когда граф планарен (Уитни); в этом случае он совпадает с графическим матроидом планарного двойственного графа.

Бинарный матроид — матроид, представимый над полем $\mathrm{GF}(2)$.

Регулярный матроид — матроид, представимый над любым полем; эквивалентно — вполне унимодулярной матрицей. Каждый графический и каждый кографический матроид регулярен.

Теоремы Татта дают особенно красивые характеризации через запрещённые миноры. Матроид бинарен тогда и только тогда, когда не содержит $U_{2,4}$ в качестве минора. Регулярный матроид дополнительно не должен содержать матроид Фано $F_7$ и его двойственный $F_7^*$.

Короткие ответы

Что такое матроид одним предложением?

Матроид — это конечное множество с заданным понятием независимости, удовлетворяющим наследственности и аксиоме обмена.

Зачем нужна аксиома обмена?

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

Где встречаются матроиды?

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

Что такое ранг матроида?

Это мощность любой его базы. Более локально r(A) — максимальная мощность независимого подмножества A. Для связного графа с n вершинами ранг его графического матроида равен n − 1.

Любая ли задача, где сработал greedy, является матроидом?

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

Чем матроид отличается от гридоида?

Гридоид — более общая структура. В матроиде из допустимого множества можно удалить любой набор элементов, и полученное подмножество останется допустимым. Гридоид отказывается от полной наследственности и требует лишь, чтобы из допустимого множества всегда можно было удалить какой-то элемент, поэтому теорема о жадном алгоритме для матроидов не переносится на произвольные гридоиды без дополнительных условий.

Матроид против задачи о рюкзаке?

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

Литература

• J. G. Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011. Основной современный справочник по теории матроидов; главы 1–2 покрывают всё, что на этой странице.
• G. Gordon, J. McNulty, Matroids: A Geometric Introduction, Cambridge University Press, 2012. Геометрическое введение, хорошо подходящее для первого знакомства.
• D. J. A. Welsh, Matroid Theory, Academic Press, 1976; Dover reprint, 2010. Классическая монография.
• A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, vol. B, chapters 39–40. Матроиды, жадные алгоритмы, пересечение и объединение матроидов.
• J. G. Oxley, «What is a matroid?», Cubo 5 (2003), 179–218. Обзорное введение от автора основного учебника, свободно доступно на странице автора в LSU.
• M. L. Fisher, G. L. Nemhauser, L. A. Wolsey, «An analysis of approximations for maximizing submodular set functions — II», Mathematical Programming Study 8 (1978), 73–87. Классический результат о жадной максимизации субмодулярных функций при матроидных ограничениях.

Nikolay Eremeev, Senior Data Infrastructure Engineer. Пишет о том, что строит в продакшене. CV ·hi@nikolay-eremeev.com