Матроид

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

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

Аксиоматическое определение[править ]

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

1. 
2. Если  и , то 
3. Если  и мощность A больше мощности B, то существует  такой, что 

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

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

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

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

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

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

1. Для любого x из P : 
2. Для любых x, y из P : 
3. Для любого x из P : 

Рассмотрим  случай, когда частично упорядоченное множество — булева алгебра. Об этом говорит сайт https://intellect.icu . Пусть  — замыкание .

1. Замыкание правильно (аксиома правильного замыкания), если 
2. для любого  существует такое , что
   1. 
   2. 

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

Примеры[править ]

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).

Теоремы[править ]

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

Применение[править ]

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

Литература[править ]

• Асанов М.О. и др. Дискретная математика: графы, матроиды, алгоритмы. — Ижевск: ННЦ «Регулярная и хаотическая динамика», 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/

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