Что такое матроид? Визуальное введение

В линейной алгебре есть независимые векторы. В теории графов — ациклические множества рёбер (леса). На первый взгляд эти идеи никак не связаны, но они подчиняются одним и тем же абстрактным правилам. Матроид и есть эта абстракция.

Определение

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

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

Графовый матроид

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

Базы, ранг и циклы

Любой матроид описывают три производных понятия:

• База — максимальное независимое множество. По аксиоме обмена все базы имеют одинаковую мощность. Для графового матроида связного графа база — это остовное дерево.
• Ранг $r(M)$ — этот общий размер. Граф на $n$ вершинах имеет ранг $n - 1$.
• Цикл (circuit) — минимальное зависимое множество. В графовом матроиде цикл — это в точности цикл в графе.

В примере выше $B = \{e_1, e_2, e_3\}$ — база, ранг равен $3$, а множества $\{e_1, e_2, e_3, e_4\}$ и $\{e_1, e_2, e_5\}$ содержат цикл.

Зачем нужны матроиды: теорема о жадном алгоритме

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

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

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