Матроид

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

Аксиоматическое определение

Матроид — пара ${\displaystyle (X,I)}$, где ${\displaystyle X}$ — конечное множество, называемое носителем матроида, а ${\displaystyle I}$ — некоторое множество подмножеств ${\displaystyle X}$, называемое семейством независимых множеств , то есть ${\displaystyle I\subset }$ ${\displaystyle 2^{X}}$. При этом должны выполняться следующие условия:

1. Пустое множество является независимым множеством, т.е. ${\displaystyle \varnothing \in I}$.
2. Все подмножества независимого множества также независимые множества, т.е. если ${\displaystyle A\in I}$ и ${\displaystyle B\subset A}$, то ${\displaystyle B\in I}$.
3. Если ${\displaystyle A,B\in I}$ и мощность A больше мощности B, то существует ${\displaystyle x\in A\setminus B}$ такой, что ${\displaystyle B\cup \{x\}\in I}$.

Базами матроида называются максимальные по включению независимые множества. Подмножества ${\displaystyle X}$, не принадлежащие ${\displaystyle I}$, называются зависимыми множествами. Минимальные по включению зависимые множества называются циклами матроида. Это понятие используется в альтернативном определении матроида.

Определение в терминах циклов

Матроид — пара ${\displaystyle (X,C)}$, где ${\displaystyle X}$ — носитель матроида, а ${\displaystyle C}$ — семейство непустых подмножеств ${\displaystyle X}$, называемое множеством циклов матроида, для которых выполняются следующие условия:^[1]

1. Ни один цикл не является подмножеством другого.
2. Если ${\displaystyle x\in C_{1}\cap C_{2}}$, то ${\displaystyle C_{1}\cup C_{2}\setminus \{x\}}$ содержит цикл.

Определение в терминах правильного замыкания

Пусть ${\displaystyle (P,\leq )}$ — частично упорядоченное множество. ${\displaystyle H:P\to P}$ — замыкание в ${\displaystyle (P,\leq )}$, если

1. Для любого x из P : ${\displaystyle H(x)\geq x}$.
2. Для любых x, y из P : ${\displaystyle x\leq y\Rightarrow H(x)\leq H(y)}$.
3. Для любого x из P : ${\displaystyle H{\big (}H(x){\big )}=H(x)}$.

Рассмотрим ${\displaystyle (P,\leq )=(2^{S},\leq )}$ случай, когда частично упорядоченное множество — булева алгебра. Пусть ${\displaystyle A\to H(A)}$ — замыкание ${\displaystyle A\subset S}$.

1. Замыкание правильно (аксиома правильного замыкания), если ${\displaystyle (p\not \in A,p\in H(A\cup \{q\}))\Rightarrow q\in H(A\cup \{p\})}$
2. для любого ${\displaystyle A\subset S}$ существует такое ${\displaystyle B\subset A}$, что
   1. ${\displaystyle |B|<+\infty }$
   2. ${\displaystyle H\left(B\right)=H\left(A\right)}$

Пара ${\displaystyle (S,A\to H(A))}$, где ${\displaystyle A\to H(A)}$ — правильное замыкание на ${\displaystyle (2^{S},\leq )}$, называется матроидом.

Примеры

1. Универсальный матроид U_{n k}. Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.
2. Матроид циклов графа. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер, циклы — простые циклы графа. Базами являются остовные леса графа. Матроид называется графическим, если он является матроидом циклов некоторого графа.^[2]
3. Матроид подмножеств множества ребер графа, таких что удаление подмножества оставляет граф связным.
4. Матроид коциклов графа. Множество X — множество ребер, коциклы — минимальные множества, удаление которых приводит к потере связности графа. Матроид называется кографическим, если он является матроидом коциклов некоторого графа.^[2]
5. Матричный матроид. Семейство всех линейно независимых подмножеств любого конечного множества векторов произвольного непустого векторного пространства является матроидом.

Определим множество E, как множество состоящее из {1, 2, 3, .., n} — номеров столбцов некоторой матрицы, а множество I, как множество состоящее из подмножеств E, таких, что векторы, определяемые ими, являются линейно независимыми над полем вещественных чисел R. Зададимся вопросом — какими свойствами обладает построенное множество I?

1. Множество I непусто. Даже если исходное множество E было пусто — E = ∅, то I будет состоять из одного элемента — множества, содержащего пустое. I = { {∅} }.
2. Любое подмножество любого элемента множества I также будет элементом этого множества. Это свойство понятно — если некоторый набор векторов линейно независим над полем, то линейно независимым будет также любой его поднабор.
3. Если A, B ∈ I, причем |A| = |B| + 1, тогда существует элемент x ∈ A − B , такой что B ∪ {x} ∈ I.

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

Доказательство. Пусть A, B ∈ I и |A| = |B| + 1. Пусть W будет пространством векторов, охватываемым A ∪ B . Понятно, что его размерность будет не менее |A|. Предположим, что B ∪ {x} будет линейно зависимо для всех x ∈ A − B (то есть третье свойство не будет выполняться). Тогда B образует базис в пространстве W. Из этого следует, что |A| ≤ dim W ≤ |B|. Но так как по условию A и B состоят из линейно независимых векторов и |A| > |B|, получаем противоречие. Такое множество векторов будет являться матроидом.

Дополнительные понятия

• Двойственным данному матроиду называется матроид, носитель которого совпадает с носителем данного матроида, а базы — дополнения баз данного матроида до носителя. То есть X^* = X, а множество баз двойственного матроида — это множество таких B^*, что B^* = X \ B, где B — база данного матроида.
• Циклом (или цепью) в матроиде называется такое множество A ⊂ X, что A ∉ I, и для любого B ⊂ A, если B ≠ A, то B ∈ I
• Рангом матроида называется мощность его баз. Ранг тривиального матроида равен нулю.

Матроид Фано

Матроид Фано

Матроиды с маленьким числом элементов часто изображают в виде диаграмм. Точки — это элементы основного множества, а кривые «протянуты» через каждую трёхэлементную цепь. Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано, пример, который появился в 1935 в статье Уитни.

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

Из проективной геометрии известно, что матроид Фано непредставим произвольным множеством векторов в вещественном или комплексном векторном пространстве (или в любом векторном пространстве над полем, чьи характеристики отличаются от 2).

Теоремы

• Все базы матроида имеют одинаковую мощность.
• Матроид однозначно задается носителем и базами.
• Цикл не может быть подмножеством другого цикла.
• Если ${\displaystyle C_{1}}$ и ${\displaystyle C_{2}}$ — циклы, то для любого ${\displaystyle x\in C_{1}\cap C_{2}:C_{1}\cup C_{2}\setminus \{x\}}$ содержит цикл.
• Если ${\displaystyle B}$ — база и ${\displaystyle x\notin B}$, то ${\displaystyle B\cup \{x\}}$ содержит ровно один цикл.

Применение

• Матроиды хорошо описывают класс задач, допускающих «жадное» решение. См. жадный алгоритм Радо — Эдмондса
• Матроиды в комбинаторной оптимизации

Литература

• Асанов М. О. и др. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ «Регулярная и хаотическая динамика», 2001. — С. 288.
• Ф. Харари. Теория графов. — Москва: УРСС, 2003. — С. 300. ISBN 5-354-00301-6
• Новиков Ф. А. Дискретная математика для программистов. — 3-е. — СПб.: Питер, 2008. — С. 101—105. — 384 с. — ISBN 978-5-91180-759-7.

Ссылки и примечания

https://web.archive.org/web/20080619011117/http://rain.ifmo.ru/cat/view.php/theory/unsorted/matroids-2004

1. Ф. Харари. Теория графов, с. 57.
2. Ф. Харари. Теория графов, с. 186.