Графический матроид

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

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

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

1. $\varnothing$ ∈I
2. Если A∈I и B⊂A, то B∈I
3. Если A,B∈I и мощность A больше мощности B, то существует x∈A\B

такой, что B∪{x}∈I

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

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

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

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

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

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

1. Для любого x из P : $H(x) \ge x$
2. Для любых x, y из P : $x \le y \Rightarrow H(x) \le H(y)$
3. Для любого x из P : $H\left(H\left(x\right)\right) = H(x)$

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

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

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

Примеры

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

Определим множество 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 ∈ B − A, такой что 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-ех елементную цепь (3-element circuit). Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано, пример, который появился в 1935 в статье Уитни (Whitney).

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

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

Теоремы

• Все базы матроида имеют одинаковую мощность.
• Матроид однозначно задается носителем и базами.
• Цикл не может быть подмножеством другого цикла
• Если C₁ и C₂ — циклы, то для любого x∈C₁∪C₂ C₁∪C₂\{x} содержит цикл
• Если B — база и x∉B, то B∪{x} содержит ровно один цикл.
• Несколько теорем и определений по базам и простым циклам матроида

Применение

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

Литература

• Асанов М.О. и др. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001. — С. 288.
• Ф. Харари Теория графов. — Москва: УРСС, 2003. — С. 300. ISBN 5-354-00301-6

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

http://rain.ifmo.ru/cat/view.php/theory/unsorted/matroids-2004/

1. ↑ Ф. Харари Теория графов стр. 57
2. ↑ ^{1 2} Ф. Харари Теория графов стр. 186