Абстрактная теория зависимости: роль матроидов в дискретной математике

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

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

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

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

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

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

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

Базовое множество E задано векторами a, b, c, d, e, f. Множества с нулевым вектором f и множества, содержащие векторы d и e, линейно зависимы.

Быть тело ,​в а - векторное пространство и конечное подмножество . Быть как набор подмножеств определено, что в линейно независимый относительно являются. Тогда пара матроид, называемый векторным матроидом.

Например, будьте -Векторное пространство и в качестве базового количества даны столбцы следующей матрицы:

Соответствующие векторы-столбцы обозначаются следующим образом:

В результате получается базовая величина и количество

наборов векторов, каждый из которых имеет линейно независимые векторы.

Напротив, векторы находятся в векторном пространстве. линейно зависима, если выполняется одно из следующих условий:

• Это одноэлементный набор, содержащий ровно нулевой вектор. В приведенном выше примере это будет вектор .
• Два или более вектора скалярно кратны друг другу. В примере это множества с векторами иеи все множества, содержащие вектор содержать.

Соответственно, нулевой столбец и скалярные кратные или их индексы в матроиде являются зависимыми.

Для матроида это базы как максимальные по включению элементы определенный. Для векторного матроида Это и есть основы векторного пространства . В настоящем примере применяется следующее:

.

Быть неориентированный мультиграф ( т.е. возможно несколько ребер и петель) с набором узловви количество кромокЭ . Графический матроид содержит в качестве независимых множеств циклические подграфыГ.

График является примером с набором узлов и набор кромок задано, где ребра определяются следующими мультимножествами : .

В этом примере круговые подграфы соответствуют независимым наборам .

Базыбграфического матроида соответствуют остовным лесам графа (или остовным деревьям для связных графов). Таким образом, к данному примеру применимо следующее:

.

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

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

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

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

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

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

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

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

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

Примеры

1. Универсальный матроид U_{n k}. Об этом говорит сайт https://intellect.icu . Множество X имеет мощность n, независимыми множествами являются подмножества мощностью не больше k. Базы — подмножества мощностью k.
2. Матроид циклов графа. Множество X — множество ребер графа, независимые множества — ациклические подмножества этих ребер, циклы — простые циклы графа. Базами являются остовные леса графа. Матроид называется графическим, если он является матроидом циклов некоторого графа.
3. Матроид подмножеств множества ребер графа, таких что удаление подмножества оставляет граф связным.
4. Матроид коциклов графа. Множество X — множество ребер, коциклы — минимальные множества, удаление которых приводит к потере связности графа. Матроид называется кографическим, если он является матроидом коциклов некоторого графа.
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).

Теоремы

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

Применение

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

Математик Хасслер Уитни , введший термин «матроид».

Матроиды были представлены и развиты несколькими авторами в 1930-х годах. Целью было аксиоматизировать известные понятия и термины из линейной алгебры , такие как линейная зависимость и независимость , базис и произведение , и перенести их в более общие структурные классы. Это позволило уточнить некоторые понятия в различных областях комбинаторики и сделало чисто комбинаторные вопросы доступными для алгебраических идей и методов. И последнее, но не менее важное: многие соображения теории графов удалось таким образом интегрировать в теорию матроидов.

Как правило, начало теории матроидов приписывают американскому математику Хасслеру Уитни. В 1935 году он исследовал материнских матроидов. , где элементыСявляются строками данной матрицы, и набор строк является независимым, если строки линейно независимы в обычном смысле. Чуть позже Бартель Леендерт ван дер Варден также использовал понятие абстрактной зависимости в своей книге «Современная алгебра». Независимо друг от друга японский математик Такео Накасава в период с 1935 по 1938 год написал четыре статьи, которые делают его сооснователем теории матроида, хотя на долгое время о них забыли.

Кроме того, появились отдельные статьи Гаррета Биркгофа (1935), Сондерса Мак Лейна (1936) и Роберта П. Дилворта (1941–1944) по теоретико-связным и геометрическим аспектам теории матроидов. Рихард Радо работал над комбинаторными приложениями матроидов (1942) и бесконечных матроидов (1949). ^{[ 12 ]} Важным стимулом для дальнейшего развития теории матроидов стало поочередное заимствование идей из разных областей и их влияние в других, таких как параллелизм между свойствами размерности в векторных пространствах и ранга в графах . В 1958 и 1959 годах Уильям Томас Тутт опубликовал фундаментальные статьи по матроидам и графам. С тех пор интерес к матроидам и их применениям в комбинаторике неуклонно возрастал, не в последнюю очередь в области комбинаторной оптимизации . Джек Эдмондс и Делберт Рэй Фулкерсон (1965) и Леонид Мирский и Хейзел Перфект (1967) независимо открыли новый класс матроидов, так называемые поперечные матроиды. По словам Уэлша, матроиды оказали на данный момент наибольший эффект в трансверсальной теории (измеряется с точки зрения достигнутых новых результатов и более простых доказательств, найденных для уже известных результатов).

Несколько важных задач комбинаторной оптимизации можно эффективно решить на каждом матроиде. В частности:

• Поиск независимого множества максимального веса во взвешенном матроиде может быть решен с помощью жадного алгоритма . Этот факт может быть даже использован для характеристики матроидов: если семейство F множеств, замкнутое относительно взятия подмножеств, обладает свойством, что независимо от того, как множества взвешены, жадный алгоритм находит множество максимального веса в семействе, то F должно быть семейством независимых множеств матроида.

• Задача разбиения матроида заключается в разбиении элементов матроида на как можно меньшее количество независимых множеств, а задача упаковки матроида заключается в нахождении как можно большего количества непересекающихся охватывающих множеств. Обе задачи могут быть решены за полиномиальное время и могут быть обобщены до задачи вычисления ранга или нахождения независимого множества в сумме матроида.

• Пересечение матроидов двух или более матроидов на одном и том же базовом множестве — это семейство множеств, которые одновременно независимы в каждом из матроидов. Задача нахождения наибольшего множества или максимально взвешенного множества в пересечении двух матроидов может быть найдена за полиномиальное время и обеспечивает решение многих других важных задач комбинаторной оптимизации. Например, максимальное соответствие в двудольных графах может быть выражено как задача пересечения двух матроидов разделов . Однако нахождение наибольшего множества в пересечении трех или более матроидов является NP-полной задачей .

Теория бесконечных матроидов намного сложнее теории конечных матроидов и образует самостоятельную тему. Долгое время одной из трудностей было то, что существовало много разумных и полезных определений, ни одно из которых, казалось, не охватывало все важные аспекты теории конечных матроидов. Например, казалось, что сложно объединить базы, контуры и дуальность в одном понятии бесконечных матроидов.

Простейшее определение бесконечного матроида — требование конечного ранга ; то есть ранг E конечен. Эта теория похожа на теорию конечных матроидов, за исключением отсутствия двойственности из-за того, что двойственный бесконечному матроиду матроид конечного ранга не имеет конечного ранга. Матроиды конечного ранга включают любые подмножества конечномерных векторных пространств и расширений полей конечной степени трансцендентности .

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

Эквивалентно, каждое зависимое множество содержит конечное зависимое множество.

Примерами являются линейная зависимость произвольных подмножеств бесконечномерных векторных пространств (но не бесконечные зависимости, как в пространствах Гильберта и Банаха ), и алгебраическая зависимость в произвольных подмножествах расширений полей возможно бесконечной степени трансцендентности. Опять же, класс финитарного матроида не является самодвойственным, поскольку двойственный к финитарному матроиду не является финитным.

Конечные бесконечные матроиды изучаются в теории моделей — разделе математической логики , тесно связанном с алгеброй .

В конце 1960-х годов теоретики матроидов запросили более общее понятие, которое разделяет различные аспекты конечных матроидов и обобщает их дуальность. Многие понятия бесконечных матроидов были определены в ответ на этот вызов, но вопрос оставался открытым. Один из подходов, рассмотренных DA Higgs, стал известен как B-матроиды и изучался Higgs, Oxley и другими в 1960-х и 1970-х годах. Согласно недавнему результату Bruhn et al. (2013) , он решает проблему: придя к одному и тому же понятию независимо, они предоставили пять эквивалентных систем аксиом — с точки зрения независимости, базисов, контуров, замыкания и ранга. Дуальность B-матроидов обобщает дуальности, которые можно наблюдать в бесконечных графах.

Аксиомы независимости следующие:

1. Пустое множество независимо.
2. Каждое подмножество независимого множества независимо.
3. Для каждого немаксимального (включенного ниже множества) независимого множества и максимальный независимый набор , есть такой что является независимым.
4. Для каждого подмножества базового пространства, каждое независимое подмножество из может быть расширена до максимального независимого подмножества .

Согласно этим аксиомам, каждый матроид имеет двойственный.

• антиматроид , Антиматроид – Математическая система упорядочений или множеств с аксиомой антиобмена
• Матроид Коксетера – Теоретико-групповое обобщение матроидов
• Greedoid – множество систем, используемых в жадной оптимизации
• Ориентированный матроид – Абстракция упорядоченной линейной алгебры
• Полиматроид – многомножественный аналог матроидов
• Прегеометрия (теория моделей) – Формулировка матроидов с использованием операторов замыкания

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

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.