Cdtrjyty

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

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

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

1. 
   ∅∈I{displaystyle varnothing in I}.


2. Если A∈I{displaystyle Ain I} и B⊂A{displaystyle Bsubset A}, то B∈I{displaystyle Bin I}.


3. Если A,B∈I{displaystyle A,Bin I} и мощность A больше мощности B, то существует x∈A∖B{displaystyle xin Asetminus B} такой, что B∪{x}∈I{displaystyle Bcup {x}in I}.

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

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

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

1. Ни один цикл не является подмножеством другого


2. Если x∈C1∩C2{displaystyle xin C_{1}cap C_{2}}, то C1∪C2∖{x}{displaystyle C_{1}cup C_{2}setminus {x}} содержит цикл

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

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

1. Для любого x из P : H(x)≥x{displaystyle H(x)geq x}.


2. Для любых x, y из P : x≤y⇒H(x)≤H(y){displaystyle xleq yRightarrow H(x)leq H(y)}.


3. Для любого x из P : H(H(x))=H(x){displaystyle H{big (}H(x){big )}=H(x)}.

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

1. Замыкание правильно (аксиома правильного замыкания), если (p∉A,p∈H(A∪{q}))⇒q∈H(A∪{p}){displaystyle (pnot in A,pin H(Acup {q}))Rightarrow qin H(Acup {p})}
   


2. для любого A⊂S{displaystyle Asubset S} существует такое B⊂A{displaystyle Bsubset A}, что
   
   
   
   1. |B|<+∞{displaystyle |B|<+infty }
   
   
   2. H(B)=H(A){displaystyle Hleft(Bright)=Hleft(Aright)}
   
   
   
   

Пара (S,A→H(A)){displaystyle (S,Ato H(A))}, где A→H(A){displaystyle Ato H(A)} — правильное замыкание на (2S,≤){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-element circuit). Диаграмма показывает 3-ранговый матроид, называемый матроидом Фано, пример, который появился в 1935 в статье Уитни (Whitney).

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

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

Теоремы |

• Все базы матроида имеют одинаковую мощность.


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


• Цикл не может быть подмножеством другого цикла.


• Если C1{displaystyle C_{1}} и C2{displaystyle C_{2}} — циклы, то для любого x∈C1∩C2:C1∪C2∖{x}{displaystyle xin C_{1}cap C_{2}:C_{1}cup C_{2}setminus {x}} содержит цикл.


• Если B{displaystyle B} — база и x∉B{displaystyle xnotin B}, то B∪{x}{displaystyle Bcup {x}} содержит ровно один цикл.

Применение |

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


• Матроиды в комбинаторной оптимизации

Литература |

• Асанов М. О. и др. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ «Регулярная и хаотическая динамика», 2001. — С. 288.


• 
  Ф. Харари. Теория графов. — Москва: УРСС, 2003. — С. 300. ISBN 5-354-00301-6
  


• Новиков Ф. А. Дискретная математика для программистов. — 3-е. — СПб.: Питер, 2008. — С. 101—105. — 384 с. — ISBN 978-5-91180-759-7.

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

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