Матроид

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

В комбинаторике , разделе математики , матроид / ˈ m eɪ t r ɔɪ d / представляет собой структуру , которая абстрагирует и обобщает понятие линейной независимости в векторных пространствах . Существует много эквивалентных способов аксиоматического определения матроида , наиболее значимые из которых заключаются в терминах: независимых множеств ; базисов или цепей ; ранговых функций ; операторов замыкания ; и замкнутых множеств или плоскостей . На языке частично упорядоченных множеств конечный простой матроид эквивалентен геометрической решетке .

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

Определение

Существует много эквивалентных способов определения (конечного) матроида. ^[a]

Независимые наборы

С точки зрения независимости, конечный матроид — это пара , где — конечное множество (называемое базовым множеством ), а — семейство подмножеств (называемых независимыми множествами ) со следующими свойствами: ^[3] ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {I}})\ ,}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {I}}}$ ${\displaystyle E}$

• (I1) Пустое множество независимо, т.е. ${\displaystyle \emptyset \in {\mathcal {I}}~.}$

• (I2) Каждое подмножество независимого множества независимо, т.е. для каждого если то Это иногда называют наследственным свойством или свойством замкнутости вниз . ${\displaystyle A'\subseteq A\subseteq E\ ,}$ ${\displaystyle A\in {\mathcal {I}}}$ ${\displaystyle A'\in {\mathcal {I}}~.}$

• (I3) Если и — два независимых множества (т. е. каждое множество независимо) и имеет больше элементов, чем , то существует такое, что в Это иногда называют свойством дополнения или свойством обмена независимыми множествами . ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B\ ,}$ ${\displaystyle x\in A\setminus B}$ ${\displaystyle B\cup \{x\}}$ ${\displaystyle {\mathcal {I}}~.}$

Первые два свойства определяют комбинаторную структуру, известную как система независимости (или абстрактный симплициальный комплекс ). Фактически, предполагая (I2), свойство (I1) эквивалентно тому факту, что по крайней мере одно подмножество является независимым, т.е. . ${\displaystyle E}$ ${\displaystyle {\mathcal {I}}\neq \emptyset }$

Базы и схемы

Подмножество основного множества , которое не является независимым, называется зависимым . Максимальное независимое множество – то есть независимое множество, которое становится зависимым при добавлении любого элемента – называется базисом для матроида. Схема в матроиде – это минимальное зависимое подмножество – то есть зависимое множество, все собственные подмножества которого независимы. Термин возникает, потому что схемы графических матроидов являются циклами в соответствующих графах. ^[3] ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle M}$ ${\displaystyle E}$

Зависимые множества, базы или схемы матроида характеризуют матроид полностью: множество независимо тогда и только тогда, когда оно не зависимо, тогда и только тогда, когда оно является подмножеством базиса, и тогда и только тогда, когда оно не содержит схему. Коллекции зависимых множеств, баз и схем имеют простые свойства, которые могут быть приняты в качестве аксиом для матроида. Например, можно определить матроид как пару , где — конечное множество, как и прежде, а — коллекция подмножеств называемых баз , со следующими свойствами: ^[3] ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {B}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle E,}$

• (B1) непусто. ${\displaystyle {\mathcal {B}}}$

• (B2) Если и являются различными членами и , то существует элемент такой, что ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle a\in A\smallsetminus B\ ,}$ ${\displaystyle b\in B\smallsetminus A}$ ${\displaystyle (A\smallsetminus \{a\})\cup \{b\}\in {\mathcal {B}}~.}$

Это свойство (B2) называется свойством обмена базиса . Из этого свойства следует, что ни один член не может быть собственным подмножеством любого другого. ${\displaystyle {\mathcal {B}}}$

Ранговые функции

Это основной результат теории матроидов, непосредственно аналогичный аналогичной теореме о базисах в линейной алгебре , что любые два базиса матроида имеют одинаковое количество элементов. Это число называется рангом Если является матроидом на и является подмножеством , то матроид на можно определить, рассматривая подмножество как независимое тогда и только тогда, когда оно независимо в Это позволяет нам говорить о подматроидах и о ранге любого подмножества Ранг подмножества задается функцией ранга матроида, которая обладает следующими свойствами: ^[3] ${\displaystyle M}$ ${\displaystyle M~.}$ ${\displaystyle M}$ ${\displaystyle E\ ,}$ ${\displaystyle A}$ ${\displaystyle E}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle M~.}$ ${\displaystyle E~.}$ ${\displaystyle A}$ ${\displaystyle r(A)}$

• (R1) Значение ранговой функции всегда является неотрицательным целым числом .

• (R2) Для любого подмножества мы имеем ${\displaystyle A\subset E}$ ${\displaystyle r(A)\leq |A|~.}$

• (R3) Для любых двух подмножеств имеем: То есть ранг является субмодулярной функцией . ${\displaystyle A,B\subset E}$ ${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)~.}$

• (R4) Для любого множества и элемента имеем: Из первого неравенства следует, что в более общем случае, если то То есть ранг является монотонной функцией . ${\displaystyle A}$ ${\displaystyle x\ ,}$ ${\displaystyle r(A)\leq r(A\cup \{x\})\leq r(A)+1~.}$ ${\displaystyle A\subseteq B\subseteq E\ ,}$ ${\displaystyle r(A)\leq r(B)\leq r(E)~.}$

Эти свойства можно использовать в качестве одного из альтернативных определений конечного матроида: если удовлетворяет этим свойствам, то независимые множества матроида над можно определить как подмножества с На языке частично упорядоченных множеств такая структура матроида эквивалентна геометрической решетке , элементами которой являются подмножества, частично упорядоченные по включению. ${\displaystyle (E,r)}$ ${\displaystyle E}$ ${\displaystyle A}$ ${\displaystyle E}$ ${\displaystyle r(A)=|A|~.}$ ${\displaystyle A\subset M\ ,}$

Разность называется нулевым подмножеством Это минимальное количество элементов, которые необходимо удалить из для получения независимого множества. Нулевое множество в называется нулевым Разность иногда называют корангом подмножества . ${\displaystyle |A|-r(A)}$ ${\displaystyle A~.}$ ${\displaystyle A}$ ${\displaystyle E}$ ${\displaystyle M}$ ${\displaystyle M~.}$ ${\displaystyle r(E)-r(A)}$ ${\displaystyle A}$

Операторы закрытия

Пусть будет матроидом на конечном множестве с ранговой функцией, как указано выше. Замыкание или охват подмножества — это множество ${\displaystyle M}$ ${\displaystyle E\ }$ ${\displaystyle r}$ ${\displaystyle \operatorname {cl} (A)}$ ${\displaystyle A}$ ${\displaystyle E}$

${\displaystyle \operatorname {cl} (A)={\Bigl \{}\ x\in E\mid r(A)=r{\bigl (}A\cup \{x\}{\bigr )}{\Bigr \}}~.}$

Это определяет оператор замыкания , где обозначает множество мощности , со следующими свойствами: ${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\mapsto {\mathcal {P}}(E)}$ ${\displaystyle {\mathcal {P}}}$

• (C1) Для всех подмножеств ${\displaystyle X}$ ${\displaystyle E\ ,}$ ${\displaystyle X\subseteq \operatorname {cl} (X)~.}$

• (C2) Для всех подмножеств ${\displaystyle X}$ ${\displaystyle E\ ,}$ ${\displaystyle \operatorname {cl} (X)=\operatorname {cl} \left(\operatorname {cl} \left(X\right)\right)~.}$

• (C3 ) Для всех подмножеств и с ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle E}$ ${\displaystyle X\subseteq Y\ ,}$ ${\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)~.}$

• (C4) Для всех элементов и из и всех подмножеств если то ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle E}$ ${\displaystyle Y}$ ${\displaystyle E\ ,}$ ${\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\smallsetminus \operatorname {cl} (Y)}$ ${\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\smallsetminus \operatorname {cl} (Y)~.}$

Первые три из этих свойств являются определяющими свойствами оператора замыкания. Четвертое иногда называют свойством обмена Маклейна – Штейница . Эти свойства можно рассматривать как еще одно определение матроида: каждая функция, которая подчиняется этим свойствам, определяет матроид. ^[3] ${\displaystyle \operatorname {cl} :{\mathcal {P}}(E)\to {\mathcal {P}}(E)}$

Квартиры

Множество, замыкание которого равно самому себе, называется замкнутым , или плоским или подпространством матроида. ^[4] Множество замкнуто, если оно максимально для своего ранга, что означает, что добавление любого другого элемента к множеству увеличит ранг. Замкнутые множества матроида характеризуются свойством покрывающего разбиения:

• (F1) Все множество точек замкнуто. ${\displaystyle E}$

• (F2) Если и — плоскости, то — плоскость. ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\cap T}$

• (F3) Если — плоскость, то каждый элемент из находится ровно в одной из плоскостей , которые покрывают (то есть, которая, собственно, содержит , но между и нет плоской плоскости ). ${\displaystyle S}$ ${\displaystyle E\smallsetminus S}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle T}$ ${\displaystyle S\ ,}$ ${\displaystyle U}$ ${\displaystyle S}$ ${\displaystyle T}$

Класс всех плоских поверхностей, частично упорядоченных включением множеств, образует решетку матроидов . Наоборот, каждая решетка матроидов образует матроид над своим множеством атомов при следующем операторе замыкания: для множества атомов с объединением ${\displaystyle {\mathcal {L}}(M)}$ ${\displaystyle L}$ ${\displaystyle E}$ ${\displaystyle S}$ ${\displaystyle \bigvee S\ ,}$

${\displaystyle \operatorname {cl} (S)=\{x\in E\mid x\leq \bigvee S\}~.}$

Квартиры этого матроида соответствуют один к одному элементам решетки; квартира, соответствующая элементу решетки, является множеством ${\displaystyle y}$

${\displaystyle \{x\in E\mid x\leq y\}~.}$

Таким образом, решетка плоскостей этого матроида естественно изоморфна . ${\displaystyle L}$

Гиперплоскости

В матроиде ранга плоскость ранга называется гиперплоскостью . (Гиперплоскости также называются коатомами или коточками .) Это максимальные собственные плоскости; то есть, единственное надмножество гиперплоскости, которое также является плоскостью, — это множество всех элементов матроида. Эквивалентное определение состоит в том, что коатом — это подмножество E , которое не охватывает M , но такое, что добавление к нему любого другого элемента делает охватывающее множество. ^[5] ${\displaystyle r\ ,}$ ${\displaystyle r-1}$ ${\displaystyle E}$

Семейство гиперплоскостей матроида обладает следующими свойствами, которые можно рассматривать как еще одну аксиоматизацию матроидов: ^[5] ${\displaystyle {\mathcal {H}}}$

• (H1) Не существует различных множеств и в То есть гиперплоскости образуют семейство Шпернера . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle X\subseteq Y~.}$

• (H2) Для каждого и отличного от существует с ${\displaystyle x\in E}$ ${\displaystyle Y,Z\in {\mathcal {H}}}$ ${\displaystyle x\notin Y\cup Z\ ,}$ ${\displaystyle X\in {\mathcal {H}}}$ ${\displaystyle (Y\cap Z)\cup \{x\}\subseteq X~.}$

Графоиды

Минти (1966) определил графоид как тройку , в которой и являются классами непустых подмножеств, таких что ${\displaystyle (L,C,D)}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle L}$

• (G1) ни один элемент (называемый «схемой») не содержит другой, ${\displaystyle C}$

• (G2) ни один элемент (называемый «сосхемой») не содержит другой, ${\displaystyle D}$

• (G3) ни один из множеств не пересекается с множеством в ровно одном элементе, и ${\displaystyle C}$ ${\displaystyle D}$

• (G4) всякий раз, когда представляется как непересекающееся объединение подмножеств с (одноэлементным множеством), то либо существует такое, что , либо существует такое, что ${\displaystyle L}$ ${\displaystyle R,G,B}$ ${\displaystyle G=\{g\}}$ ${\displaystyle X\in C}$ ${\displaystyle g\in X\subseteq R\cup G}$ ${\displaystyle Y\in D}$ ${\displaystyle g\in Y\subseteq B\cup G~.}$

Он доказал, что существует матроид, для которого есть класс схем, а есть класс косхем. Наоборот, если и есть классы схем и косхем матроида с базовым множеством, то есть графоид. Таким образом, графоиды дают самодвойственную криптоморфную аксиоматизацию матроидов. ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle C}$ ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle E\ ,}$ ${\displaystyle (E,C,D)}$

Примеры

Свободный матроид

Пусть будет конечным множеством. Множество всех подмножеств определяет независимые множества матроида. Оно называется свободным матроидом над . ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle E}$

Равномерные матроиды

Пусть будет конечным множеством и натуральным числом . Можно определить матроид на , взяв каждый элемент подмножества из в качестве базиса. Это известно как равномерный матроид ранга Равномерный матроид с рангом и с элементами обозначается Все равномерные матроиды ранга не менее 2 являются простыми (см. § Дополнительные термины). Равномерный матроид ранга 2 на точках называется точечной линией . Матроид равномерен тогда и только тогда, когда он не имеет контуров размера меньше единицы плюс ранг матроида. Прямые суммы равномерных матроидов называются матроидами разбиения . ${\displaystyle E}$ ${\displaystyle k}$ ${\displaystyle E}$ ${\displaystyle k}$ ${\displaystyle E}$ ${\displaystyle k~.}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle U_{k,n}~.}$ ${\displaystyle n}$ ${\displaystyle n}$ 

В однородном матроиде каждый элемент является петлей (элементом, который не принадлежит ни одному независимому множеству), а в однородном матроиде каждый элемент является колупом (элементом, который принадлежит всем базам). Прямая сумма матроидов этих двух типов является матроидом разбиения, в котором каждый элемент является петлей или колупом; он называется дискретным матроидом . Эквивалентное определение дискретного матроида — это матроид, в котором каждое собственное непустое подмножество основного множества является сепаратором. ${\displaystyle U_{0,n}\ ,}$ ${\displaystyle U_{n,n}\ ,}$ ${\displaystyle E}$

Матроиды из линейной алгебры

Матроид Фано, полученный из плоскости Фано . Он GF(2) -линейный, но не вещественно-линейный.

Матроид Вамоса , не линейный ни над каким полем

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

Если — любое конечное подмножество векторного пространства , то мы можем определить матроид на , взяв независимые множества в качестве линейно независимых подмножеств ${\displaystyle E}$ ${\displaystyle V\ ,}$ ${\displaystyle M}$ ${\displaystyle E}$ ${\displaystyle M}$ ${\displaystyle E~.}$

Справедливость аксиом независимого множества для этого матроида следует из леммы Штейница об обмене .

Если — матроид, который можно определить таким образом, мы говорим, что множество представляет ${\displaystyle M}$ ${\displaystyle E}$ ${\displaystyle M~.}$

Матроиды такого типа называются векторными матроидами .

Важным примером матроида, определенного таким образом, является матроид Фано, матроид ранга три, полученный из плоскости Фано , конечной геометрии с семью точками (семь элементов матроида) и семью линиями (собственные нетривиальные плоскости матроида). Это линейный матроид, элементы которого могут быть описаны как семь ненулевых точек в трехмерном векторном пространстве над конечным полем GF(2) . Однако невозможно предоставить аналогичное представление для матроида Фано, используя действительные числа вместо GF(2).

Матрица с записями в поле порождает матроид на своем наборе столбцов. Зависимые наборы столбцов в матроиде — это те, которые линейно зависимы как векторы. ${\displaystyle A}$ ${\displaystyle M}$

Этот матроид называется столбчатым матроидом и считается представляющим . ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle M}$

Например, матроид Фано может быть представлен таким образом как матрица 3 × 7 (0,1) . Столбчатые матроиды — это просто векторные матроиды под другим названием, но часто есть причины отдать предпочтение матричному представлению. ^[b]

Матроид, эквивалентный векторному матроиду, хотя он может быть представлен по-разному, называется представимым или линейным . Если эквивалентно векторному матроиду над полем , то мы говорим, что представимо над ; в частности, является вещественно представимым, если оно представимо над вещественными числами. Например, хотя графический матроид (см. ниже) представлен в виде графа, он также представим векторами над любым полем. ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$ ${\displaystyle F}$ ${\displaystyle M}$

Основная проблема в теории матроидов — характеризовать матроиды, которые могут быть представлены над заданным полем ; гипотеза Роты описывает возможную характеризацию для каждого конечного поля . Основными результатами на данный момент являются характеризации бинарных матроидов (представимых над GF(2)) по Тутте (1950-е годы), тернарных матроидов (представимых над полем из 3 элементов) по Риду и Биксби, и отдельно по Сеймуру (1970-е годы), и кватернарных матроидов (представимых над полем из 4 элементов) по Джилену, Джерардсу и Капуру (2000). Доказательство гипотезы Роты было объявлено, но не опубликовано, в 2014 году Джиленом, Джерардсом и Уиттлом. ^[6] ${\displaystyle F}$

Регулярный матроид — это матроид, который представим над всеми возможными полями. Матроид Вамоса — это простейший пример матроида, который не представим ни над каким полем.

Матроиды из теории графов

Вторым первоисточником теории матроидов является теория графов .

Каждый конечный граф (или мультиграф ) порождает матроид следующим образом: возьмем в качестве множества всех ребер в и считаем множество ребер независимым тогда и только тогда, когда оно является лесом ; то есть если оно не содержит простого цикла . Тогда называется циклическим матроидом . Матроиды, полученные таким образом, являются графическими матроидами . Не каждый матроид является графическим, но все матроиды на трех элементах являются графическими. ^[7] Каждый графический матроид является регулярным. ${\displaystyle G}$ ${\displaystyle M(G)}$ ${\displaystyle E}$ ${\displaystyle G}$ ${\displaystyle M(G)}$

Впоследствии были обнаружены и другие матроиды на графах:

• Бициклический матроид графа определяется путем называния набора ребер независимым, если каждое связное подмножество содержит не более одного цикла.

• В любом ориентированном или неориентированном графе пусть и будут двумя выделенными множествами вершин. В множестве определите подмножество как независимое, если существуют пути из вершин в , не пересекающиеся по вершинам . Это определяет матроид на , называемый гаммоидом : ^[8] строгий гаммоид — это тот, для которого множество является всем множеством вершин . ^[9] ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle U}$ ${\displaystyle |U|}$ ${\displaystyle F}$ ${\displaystyle U}$ ${\displaystyle E}$ ${\displaystyle E}$ ${\displaystyle G}$

• В двудольном графе можно сформировать матроид, в котором элементы являются вершинами на одной стороне двудольного графа, а независимые подмножества являются множествами конечных точек паросочетаний графа. Это называется трансверсальным матроидом , ^{[10] [11]} и является частным случаем гаммоида. ^[8] Трансверсальные матроиды являются двойственными матроидами к строгим гаммоидам. ^[9] ${\displaystyle G=(U,V,E)}$ ${\displaystyle U}$

• Графические матроиды были обобщены до матроидов из знаковых графов , графов усиления и смещенных графов . Граф с выделенным линейным классом циклов, известный как «смещенный граф», имеет два матроида, известные как каркасный матроид и подъемный матроид смещенного графа. ${\displaystyle G}$ ${\displaystyle B}$ ${\displaystyle (G,B)\ ,}$

Если каждый цикл принадлежит выделенному классу, эти матроиды совпадают с матроидом цикла . Если ни один цикл не выделен, каркасный матроид является бициклическим матроидом знакового графа, ребра которого помечены знаками, и графа усиления, который является графом, ребра которого помечены ориентируемо из группы, каждый из которых порождает смещенный граф и, следовательно, имеет каркасный и подъемный матроиды. ${\displaystyle G}$ ${\displaystyle G~.}$

• Графы Ламана образуют основу двумерного матроида жесткости , матроида, определенного в теории структурной жесткости .

• Пусть будет связным графом и будет его множеством ребер. Пусть будет набором подмножеств такого , что все еще связно. Тогда множество элементов которого есть и с его классом независимых множеств, является матроидом, называемым матроидом связей ${\displaystyle G}$ ${\displaystyle E}$ ${\displaystyle I}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle G-F}$ ${\displaystyle M^{*}(G)\ ,}$ ${\displaystyle E}$ ${\displaystyle I}$ ${\displaystyle G~.}$

Ранговая функция — это цикломатическое число подграфа, индуцированное на подмножестве ребер , которое равно числу ребер вне максимального леса этого подграфа, а также числу независимых циклов в нем. ${\displaystyle r(F)}$ ${\displaystyle F\ ,}$

Матроиды из расширений полей

Третьим первоисточником теории матроидов является теория поля .

Расширение поля приводит к образованию матроида:

Предположим, что и являются полями с содержащими . Пусть будет любым конечным подмножеством . ${\displaystyle F}$ ${\displaystyle K}$ ${\displaystyle K}$ ${\displaystyle F}$ ${\displaystyle E}$ ${\displaystyle K}$

Определим подмножество как алгебраически независимое , если поле расширения имеет степень трансцендентности, равную ^[12] ${\displaystyle S}$ ${\displaystyle E}$ ${\displaystyle F(S)}$ ${\displaystyle |S|~.}$

Матроид, эквивалентный матроиду такого типа, называется алгебраическим матроидом . ^[13] Проблема характеристики алгебраических матроидов чрезвычайно сложна; о ней мало что известно. Матроид Вамоса представляет собой пример матроида, который не является алгебраическим.

Базовые конструкции

Существуют некоторые стандартные способы создания новых матроидов из старых.

Двойственность

Если — конечный матроид, мы можем определить ортогональный или двойственный матроид , взяв тот же базовый набор и назвав набор базисом в тогда и только тогда, когда его дополнение является базисом в Нетрудно проверить, что является матроидом, а двойственный к — ^[14] ${\displaystyle M}$ ${\displaystyle M^{*}}$ ${\displaystyle M^{*}}$ ${\displaystyle M~.}$ ${\displaystyle M^{*}}$ ${\displaystyle M^{*}}$ ${\displaystyle M~.}$

Двойственность можно описать одинаково хорошо и другими способами определения матроида. Например:

• Множество независимо тогда и только тогда, когда его дополнение охватывает ${\displaystyle M^{*}}$ ${\displaystyle M~.}$

• Множество является цепью тогда и только тогда, когда его дополнение является коатомом в ${\displaystyle M^{*}}$ ${\displaystyle M~.}$

• Ранговая функция двойственной функции равна ${\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\smallsetminus S\right)~.}$

Согласно матроидной версии теоремы Куратовского , двойственный графическому матроиду является графическим матроидом тогда и только тогда, когда является матроидом планарного графа . В этом случае двойственный является матроидом двойственного графа [ ^15] Двойственный векторному матроиду матроид , представимый над конкретным полем , также представим над Двойственный трансверсальному матроиду является строгим гаммоидом и наоборот. ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle G~.}$ ${\displaystyle F}$ ${\displaystyle F~.}$

Пример

Матроид цикла графа является двойственным матроидом его матроида связей.

Несовершеннолетние

Если M — матроид с множеством элементов E , а S — подмножество E , то ограничение M до S , записанное как M  | S , — это матроид на множестве S , независимые множества которого являются независимыми множествами M , содержащимися в S. Его контуры являются контурами M , содержащимися в S , а его ранговая функция — это функция M, ограниченная подмножествами S.

В линейной алгебре это соответствует ограничению подпространством, порожденным векторами в S. Эквивалентно , если T = M − S, это можно назвать удалением T , записанным как M \ T или M − T. Субматроиды M являются в точности результатами последовательности удалений: порядок не имеет значения. ^{[16] [17]}

Двойственной операцией ограничения является свертывание. ^[18] Если T является подмножеством E , то свертывание M посредством T , записанное как M / T , является матроидом на базовом множестве E − T, ранговая функция которого равна ^[19] В линейной алгебре это соответствует рассмотрению фактор-пространства по линейному пространству, порожденному векторами в T , вместе с образами векторов в E - T. ${\displaystyle r'(A)=r(A\cup T)-r(T).}$

Матроид N , полученный из M с помощью последовательности операций ограничения и сжатия, называется минором M. [ 17 ^{] [20]} Мы говорим, что M содержит N как минор . Многие важные семейства матроидов могут быть охарактеризованы минорно-минимальными матроидами, которые не принадлежат семейству; они называются запрещенными или исключенными минорами . ^[21]

Суммы и объединения

Пусть M — матроид с базовым набором элементов E , а N — другой матроид на базовом наборе F. Прямая сумма матроидов M и N — это матроид, базовый набор которого является дизъюнктным объединением E и F , а независимые наборы — дизъюнктными объединениями независимого набора M с независимым набором N.

Объединение M и N — это матроид , базовое множество которого является объединением (а не дизъюнктным объединением) E и F , а независимые множества — это те подмножества, которые являются объединением независимого множества в M и одного в N. Обычно термин « объединение » применяется, когда E = F , но это предположение не является существенным. Если E и F не пересекаются, объединение является прямой суммой.

Дополнительные условия

Пусть M — матроид с базовым набором элементов E.

• E можно назвать базовым множеством M. Его элементы можно назвать точками M.

• Подмножество E охватывает M, если его замыкание равно E. Говорят, что множество охватывает замкнутое множество K , если его замыкание равно K.

• Обхват матроида — это размер его наименьшего контура или зависимого множества.

• Элемент, который образует одноэлементную цепь M, называется петлей . Эквивалентно, элемент является петлей, если он не принадлежит ни одному базису. ^{[7] [22]}

• Элемент, который не принадлежит ни к одному контуру, называется coloop или isthmus . Эквивалентно, элемент является coloop, если он принадлежит каждому базису.

Loop и coloops являются взаимно двойственными. ^[22]

• Если двухэлементный набор { f, g } является контуром M , то f и g параллельны в M. ^[7 ]

• Матроид называется простым , если он не имеет контуров, состоящих из 1 или 2 элементов. То есть, он не имеет петель и параллельных элементов. Также используется термин комбинаторная геометрия . ^[7] Простой матроид, полученный из другого матроида M путем удаления всех петель и удаления одного элемента из каждого контура из 2 элементов до тех пор, пока не останется контуров из 2 элементов, называется упрощением M. [ ^23] Матроид является сопростым , если его двойственный матроид является простым. [ ^24]

• Объединение контуров иногда называют циклом M. Таким образом, цикл является дополнением плоскости двойственного матроида. (Такое использование противоречит общепринятому значению термина «цикл» в теории графов. )

• Разделитель M — это подмножество S множества E , такое что . Собственный или нетривиальный разделитель — это разделитель , который не является ни E , ни пустым множеством. ^[25] Неприводимый разделитель — это непустой разделитель, который не содержит других непустых разделителей. Неприводимые разделители разбивают основное множество E . ${\displaystyle r(S)+r(E-S)=r(M)}$

• Матроид, который не может быть записан как прямая сумма двух непустых матроидов, или, что эквивалентно, не имеющий собственных разделителей, называется связным или неприводимым . Матроид связен тогда и только тогда, когда его двойственный связен. ^[26]

• Максимальный неприводимый субматроид M называется компонентом M. Компонента — это ограничение M до неприводимого сепаратора, и наоборот, ограничение M до неприводимого сепаратора — это компонент. Сепаратор — это объединение компонент. ^[25]

• Матроид M называется каркасным матроидом, если он или содержащий его матроид имеет базис такой, что все точки M содержатся в линиях, соединяющих пары базисных элементов. ^[27]

• Матроид называется мощеным матроидом, если все его контуры имеют размер, по крайней мере равный его рангу. ^[28]

• Матроидный многогранник является выпуклой оболочкой индикаторных векторов базисов . ${\displaystyle P_{M}}$ ${\displaystyle M}$

Алгоритмы

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

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

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

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

Программное обеспечение Matroid

Две автономные системы для вычислений с матроидами — это Oid Кингана и Macek Хлинени. Обе они являются пакетами с открытым исходным кодом. «Oid» — это интерактивная, расширяемая программная система для экспериментов с матроидами. «Macek» — это специализированная программная система с инструментами и процедурами для достаточно эффективных комбинаторных вычислений с представимыми матроидами.

Обе системы программного обеспечения математики с открытым исходным кодом SAGE и Macaulay2 содержат пакеты матроидов. В Maple есть пакет для работы с матроидами с версии 2024. ^[30]

Полиномиальные инварианты

Существует два особенно важных полинома, связанных с конечным матроидом M на базовом множестве E. Каждый из них является инвариантом матроида , что означает, что изоморфные матроиды имеют один и тот же полином.

Характеристический многочлен

Характеристический многочлен M – иногда называемый хроматическим многочленом ^[31], хотя он не учитывает раскраски – определяется как

${\displaystyle p_{M}(\lambda ):=\sum _{S\subseteq E}(-1)^{|S|}\lambda ^{r(E)-r(S)},}$

или эквивалентно (при условии, что пустое множество замкнуто в M ) как

${\displaystyle p_{M}(\lambda ):=\sum _{A}\mu (\emptyset ,A)\lambda ^{r(E)-r(A)}\ ,}$

где μ обозначает функцию Мёбиуса геометрической решетки матроида, а сумма берется по всем плоскостям A матроида. ^[32]

• Когда M — циклический матроид M ( G ) графа G , характеристический многочлен является небольшим преобразованием хроматического многочлена , который задается формулой χ _G  (λ) = λ ^c p _{M ( G )}  (λ), где c — число связных компонент G .

• Когда M является матроидом связей M *( G ) графа G , характеристический полином равен потоковому полиному G .

• Когда M является матроидом M ( A ) конфигурации A линейных гиперплоскостей в ℝ ⁿ (или F ⁿ , где F — любое поле), характеристический многочлен конфигурации задается формулой p _A  (λ) = λ ^{n − r ( M )} p _M  (λ).

Бета-инвариант

Бета -инвариант матроида, введенный Крапо (1967), может быть выражен в терминах характеристического полинома как оценка производной ^[33] ${\displaystyle p}$

${\displaystyle \beta (M)=(-1)^{r(M)-1}p_{M}'(1)}$

или напрямую как ^[34]

${\displaystyle \beta (M)=(-1)^{r(M)}\sum _{X\subseteq E}(-1)^{|X|}r(X)~.}$

Бета-инвариант неотрицателен и равен нулю тогда и только тогда, когда является несвязным, пустым или петлей. В противном случае он зависит только от решетки плоских поверхностей Если не имеет петель и колец, то ^[34] ${\displaystyle M}$ ${\displaystyle M~.}$ ${\displaystyle M}$ ${\displaystyle \beta (M)=\beta (M^{*})~.}$

Числа Уитни

Числа Уитни первого рода являются коэффициентами при степенях в характеристическом полиноме. В частности, число Уитни -го рода является коэффициентом при и является суммой значений функции Мёбиуса: ${\displaystyle M}$ ${\displaystyle \lambda }$ ${\displaystyle i}$ ${\displaystyle w_{i}(M)}$ ${\displaystyle \lambda ^{r(M)-i}}$

${\displaystyle w_{i}(M)=\sum \{\mu (\emptyset ,A):r(A)=i\},}$

суммируются по квартирам правого ранга. Эти числа чередуются по знаку, так что для ${\displaystyle (-1)^{i}w_{i}(M)>0}$ ${\displaystyle 0\leq i\leq r(M)~.}$

Числа Уитни второго рода — это номера квартир каждого ранга. То есть — это номер  квартир ранга. ${\displaystyle M}$ ${\displaystyle W_{i}(M)}$ ${\displaystyle i}$

Числа Уитни обоих видов обобщают числа Стирлинга первого и второго рода, которые являются числами Уитни циклического матроида полного графа и, что эквивалентно, решетки разбиений . Они были названы в честь Хасслера Уитни , (со)основателя теории матроидов, Джан-Карло Ротой . Название было распространено на аналогичные числа для конечных ранжированных частично упорядоченных множеств .

полином Тутте

Многочлен Тутте матроида обобщает характеристический многочлен на две переменные. Это дает ему больше комбинаторных интерпретаций, а также придает ему свойство двойственности ${\displaystyle T_{M}(x,y)\ ,}$

${\displaystyle T_{M^{*}}(x,y)=T_{M}(y,x)\ ,}$

что подразумевает ряд дуальностей между свойствами и свойствами Одно определение многочлена Тутта имеет вид ${\displaystyle M}$ ${\displaystyle M^{*}~.}$

${\displaystyle T_{M}(x,y)=\sum _{S\subseteq E}(x-1)^{r(M)-r(S)}\ (y-1)^{|S|-r(S)}~.}$

Это выражает полином Тутте как оценку полинома коранга-нульности или полинома, генерирующего ранг , ^[35]

${\displaystyle R_{M}(u,v)=\sum _{S\subseteq E}u^{r(M)-r(S)}v^{|S|-r(S)}~.}$

Из этого определения легко видеть, что характеристический многочлен представляет собой, с точностью до простого множителя, оценку, в частности, ${\displaystyle T_{M}\ ,}$

${\displaystyle p_{M}(\lambda )=(-1)^{r(M)}T_{M}(1-\lambda ,0)~.}$

Другое определение дается в терминах внутренней и внешней деятельности и суммы по основаниям, отражая тот факт, что есть число оснований. ^[36] Это определение, которое суммирует по меньшему количеству подмножеств, но имеет более сложные термины, было первоначальным определением Тутта. ${\displaystyle T(1,1)}$

Существует еще одно определение в терминах рекурсии путем удаления и сокращения. ^[37] Тождество удаления-сокращения:

${\displaystyle F(M)=F(M-e)+F(M/e)}$

когда не является ни циклом, ни колупом. Инвариант матроидов (т. е. функция, которая принимает одно и то же значение на изоморфных матроидах), удовлетворяющий этой рекурсии и мультипликативному условию ${\displaystyle e}$

${\displaystyle F(M\oplus M')=F(M)F(M')}$

называется инвариантом Тутте-Гротендика . ^[35] Полином Тутте является наиболее общим таким инвариантом; то есть полином Тутте является инвариантом Тутте-Гротендика, и каждый такой инвариант является оценкой полинома Тутте. ^[31]

Полином Тутте графа — это полином Тутте его циклического матроида. ${\displaystyle T_{G}}$ ${\displaystyle T_{M(G)}}$

Бесконечные матроиды

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

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

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

${\displaystyle x\in \operatorname {cl} (Y)\ \Leftrightarrow \ {\text{ there is a finite set }}Y'\subseteq Y{\text{ such that }}x\in \operatorname {cl} (Y').}$

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

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

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

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

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

1. Пустое множество независимо.
2. Каждое подмножество независимого множества независимо.
3. Для каждого немаксимального (включенного в множество) независимого множества и максимального независимого множества существует такое, что является независимым. ${\displaystyle \ I\ }$ ${\displaystyle \ J\ }$ ${\displaystyle \ x\in J\smallsetminus I\ }$ ${\displaystyle \ I\cup \{x\}\ }$
4. Для каждого подмножества базового пространства каждое независимое подмножество может быть расширено до максимального независимого подмножества ${\displaystyle \ X\ }$ ${\displaystyle \ I\ }$ ${\displaystyle \ X\ }$ ${\displaystyle \ X~.}$

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

История

Теория матроидов была введена Уитни (1935). Она также была независимо открыта Такео Накасавой , чья работа была забыта на многие годы Нисимурой и Куродой (2009).

В своей основополагающей статье Уитни предоставил две аксиомы независимости и определил любую структуру, придерживающуюся этих аксиом, как «матроиды». ^[c] Его ключевое наблюдение состояло в том, что эти аксиомы предоставляют абстракцию «независимости», которая является общей как для графов, так и для матриц. Из-за этого многие термины, используемые в теории матроидов, напоминают термины для их аналогичных понятий в линейной алгебре или теории графов .

Почти сразу после того, как Уитни впервые написал о матроидах, была написана важная статья Маклейна (1936) о связи матроидов с проективной геометрией . Год спустя ван дер Варден (1937) отметил сходство между алгебраической и линейной зависимостью в своем классическом учебнике по современной алгебре.

В 1940-х годах Ричард Радо разработал дальнейшую теорию под названием «независимые системы» с прицелом на трансверсальную теорию , в которой его название для этого предмета иногда используется до сих пор.

В 1950-х годах У. Т. Тутт стал ведущей фигурой в теории матроидов, и эту позицию он сохранял много лет. Его вклад был многочисленным, включая

• характеристика бинарных , регулярных и графических матроидов с помощью исключенных миноров

• теорема о регулярной матроидной представимости

• теория цепных групп и их матроидов

и инструменты, которые он использовал для доказательства многих своих результатов:

• «Теорема пути»

• « Теорема Тутте о гомотопии » (см., например, Тутте (1965))

которые настолько сложны, что более поздние теоретики приложили немало усилий, чтобы исключить необходимость в них в доказательствах. ^[d]

Крапо (1969) и Брилавски (1972) обобщили на матроиды «дихромат» Тутта, графический многочлен, теперь известный как многочлен Тутта (названный так Крапо). За их работой в последнее время (особенно в 2000-х) последовал поток статей, хотя и не так много, как по многочлену Тутта графа.

В 1976 году Доминик Уэлш опубликовал первую всеобъемлющую книгу по теории матроидов.

Теорема разложения Пола Сеймура для регулярных матроидов (Seymour (1980)) была самой значимой и влиятельной работой конца 1970-х и 1980-х годов. Другой фундаментальный вклад Кана и Кунга (1982) показал, почему проективные геометрии и геометрии Даулинга играют такую ​​важную роль в теории матроидов.

К 1980-м годам появилось много других важных авторов, но нельзя не упомянуть расширение Джеффом Уиттлом на тернарные матроиды характеристики Тутта для бинарных матроидов, которые представимы над рациональными числами (Уиттл, 1995), возможно, самый большой отдельный вклад 1990-х годов.

В текущий период (примерно с 2000 года) проект Matroid Minors от Geelen , Gerards, Whittle и других ^[e] дал существенные успехи в теории структуры матроидов. Многие другие также внесли свой вклад в эту часть теории матроидов, которая (в первом и втором десятилетиях 21-го века) процветает.

Исследователи

Математики, которые были пионерами в изучении матроидов, включают:

Сусуму Курода ^[38]

Сондерс Маклейн

Ричард Радо

Такео Накасава

Хирокадзу Нисимура ^[38]

WT Тутте

БЛ ван дер Варден

Хасслер Уитни

Некоторые из других основных участников:

Джек Эдмондс

Джим Джилен

Юджин Лоулер

Ласло Ловас

Джан-Карло Рота

ПД Сеймур

Доминик Уэлш

Сноски

1. Оксли (1992) — стандартный источник основных определений и результатов, касающихся матроидов; Уэлш (1976) — более старый стандартный источник.
   Список систем аксиом матроидов, которые являются эквивалентными, см. в приложении Брилавского к книге Уайта (1986), стр. 298–302.

2. Есть одно техническое различие: столбчатый матроид может иметь различные элементы, которые являются одним и тем же вектором, но векторный матроид, как определено выше, не может. Обычно это различие незначительно и может быть проигнорировано, но, позволяя быть мультимножеством векторов, можно привести два определения в полное согласие. ${\displaystyle E}$
3. Хотя это, возможно, подразумевалось, Уитни (1935) не включил аксиому, требующую, чтобы по крайней мере одно подмножество было независимым.

4. Прекрасным примером является краткое доказательство А. М. Х. Джерардса (Gerards (1989)) характеристики регулярных матроидов Татта.
5. Проект «Матроидные миноры» — это попытка повторить успех проекта Робертсона–Сеймура по графовым минорам для матроидов, представимых над конечным полем (см. теорему Робертсона–Сеймура ).

Смотрите также

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

Цитаты

1. Нил и Нойдауэр (2009)
2. Кашьяп, Солянин и Фонтобель (2009)
3. Welsh (1976, стр. 7–9), Раздел 1.2, «Системы аксиом для матроида».
4. Уэлш (1976, стр. 21–22), Раздел 1.8, «Замкнутые множества = Квартиры = Подпространства».
5. Welsh (1976, стр. 38–39), Раздел 2.2, «Гиперплоскости матроида».
6. "Решение гипотезы Рота" (PDF) . Notices of the American Mathematical Society : 736–743. 17 августа 2014 г.
7. Оксли (1992), стр. 13
8. Oxley (1992), стр. 115
9. Oxley (1992), стр. 100
10. Оксли (1992), стр. 46–48.
11. Уайт (1987), стр. 72–97.
12. Оксли (1992), стр. 215
13. Оксли (1992), стр. 216
14. Уайт (1986), стр. 32
15. Уайт (1986), стр. 105
16. Уайт (1986), стр. 131
17. White (1986), стр. 224
18. Уайт (1986), стр. 139
19. Уайт (1986), стр. 140
20. Уайт (1986), стр. 150
21. Уайт (1986), стр. 146–147.
22. White (1986), стр. 130
23. Оксли (1992), стр. 52
24. Оксли (1992), стр. 347
25. Oxley (1992), стр. 128
26. Уайт (1986), стр. 110
27. Заславский (1994)
28. Оксли (1992), стр. 26
29. Оксли (1992), стр. 64
30. "Пакеты Matroids и Hypergraphs в Maple 2024" (PDF) . MapleSoft . Получено 2024-08-19 .
31. White (1987), стр. 127
32. Уайт (1987), стр. 120
33. Уайт (1987), стр. 123
34. White (1987), стр. 124
35. White (1987), стр. 126
36. Уайт (1992b), стр. 188
37. Уайт (1986), стр. 260
38. Нисимура и Курода (2009)

Ссылки

• Брун, Хеннинг; Дистель, Рейнхард; Кризелл, Маттиас; Пендавинг, Руди; Воллан, Пол (2013). «Аксиомы для бесконечных матроидов». Успехи математики . 239 : 18–46. arXiv : 1003.3919 . doi : 10.1016/j.aim.2013.01.011 . MR  3045140. S2CID  10436077.
• Брайант, Виктор; Перфект, Хейзел (1980). Теория независимости в комбинаторике . Лондон, Великобритания и Нью-Йорк, Нью-Йорк: Chapman and Hall. ISBN 978-0-412-22430-0.
• Brylawski, Thomas H. (1972). «Разложение комбинаторных геометрий». Transactions of the American Mathematical Society . 171 : 235–282. doi : 10.2307/1996381 . JSTOR  1996381.
• Крапо, Генри Х. (1969). «Полином Тутте». Математические уравнения . 3 (3): 211–229. дои : 10.1007/BF01817442. S2CID  119602825.
• Крапо, Генри Х.; Рота , Джан-Карло (1970). Об основах комбинаторной теории: комбинаторные геометрии. Кембридж, Массачусетс: MIT Press. ISBN 978-0-262-53016-3. MR  0290980 – через Интернет-архив (archive.org).
• Эдмондс, Джек (5–9 марта 2001 г.). «Субмодулярные функции, матроиды и некоторые многогранники». В Юнгер, Михаэль; Рейнелт, Герхард; Ринальди, Джованни (ред.). Комбинаторная оптимизация — Эврика, вы уменьшаетесь!: Статьи, посвященные Джеку Эдмондсу . 5-й международный семинар. Заметки лекций по информатике. Том 2570 (ред. пересмотренных статей). Aussois, FR: Берлин, Гейдельберг: Springer (опубликовано в 2003 г.). стр. 11–26. CiteSeerX  10.1.1.454.4060 . doi :10.1007/3-540-36478-1_2. ISBN 978-3-540-36478-8.
• Geelen, JF; Gerards, AMH; Kapoor, A. (2000). «Исключенные миноры для GF(4)-представимых матроидов». Журнал комбинаторной теории . Серия B. 79 (2): 247–299. doi :10.1006/jctb.2000.1963. MR  1769191.
• Geelen, Jim ; Gerards, AMH; Whittle, Geoff (2007). «К теории матроидно-минорной структуры». В Grimmett, Geoffrey; et al. (ред.). Combinatorics, Complexity, and Chance: A tribute to Dominic Welsh . Oxford Lecture Series in Mathematics and its Applications. Vol. 34. Oxford, UK: Oxford University Press. pp. 72–82.
• Gerards, AMH (1989). "Короткое доказательство характеристики Татта полностью унимодулярных матриц". Линейная алгебра и ее приложения . 114–115: 207–212. doi : 10.1016/0024-3795(89)90461-8 .
• Кан, Джефф; Кунг, Джозеф PS (1982). «Многообразия комбинаторных геометрий». Труды Американского математического общества . 271 (2): 485–499. doi : 10.2307/1998894 . JSTOR  1998894.
• Кинген, Роберт; Кинген, Сандра (2005). «Программная система для матроидов». Графы и открытия . Серия DIMACS по дискретной математике и теоретической информатике. С. 287–296.
• Кашьяп, Навин; Солджанин, Эмина; Фонтобель, Паскаль (2009). Приложения теории матроидов и комбинаторной оптимизации к теории информации и кодирования (PDF) (Отчет) . Получено 4 октября 2014 г. – через www.birs.ca.
• Кунг, Джозеф П.С., ред. (1986). Справочник по теории матроидов. Бостон, Массачусетс: Birkhäuser. doi : 10.1007/978-1-4684-9199-9. ISBN 978-0-8176-3173-4. MR  0890330 – через Интернет-архив (archive.org).
• Маклейн, Сондерс (1936). «Некоторые интерпретации абстрактной линейной зависимости в терминах проективной геометрии». American Journal of Mathematics . 58 (1): 236–240. doi :10.2307/2371070. JSTOR  2371070.
• Минти, Джордж Дж. (1966). «Об аксиоматических основах теорий направленных линейных графов, электрических сетей и сетевого программирования». Журнал математики и механики . 15 : 485–520. MR  0188102.
• Нил, Дэвид Л.; Нойдауэр, Нэнси А. (2009). «Матроиды, которых вы знали» (PDF) . Mathematics Magazine . 82 (1): 26–41. doi :10.4169/193009809x469020 . Получено 4 октября 2014 г. – через Mathematical Association of America (maa.org).
• Нисимура, Хирокадзу; Курода, Сусуму, ред. (2009). Затерянный математик Такео Накасава: забытый отец теории матроидов . Базель, Швейцария: Birkhäuser Verlag. дои : 10.1007/978-3-7643-8573-6. ISBN 978-3-7643-8572-9. MR  2516551. Zbl  1163.01001.
• Оксли, Джеймс (1992). Теория матроидов . Оксфорд, Великобритания: Oxford University Press. ISBN 978-0-19-853563-8. MR  1207587. Zbl  0784.05002.
• Речски, Андраш (1989). Теория матроидов и ее применение в теории электрических сетей и статике . Алгоритмы и комбинаторика. Том 6. Берлин, Германия и Будапешт, Венгрия: Springer-Verlag и Akademiai Kiado. doi :10.1007/978-3-662-22143-3. ISBN 978-3-540-15285-9. MR  1027839. S2CID  117772439 – через Интернет-архив (archive.org).
• Сапоженко, А.А. (2001) [1994]. «Матроид». Энциклопедия математики . Издательство EMS .
• Сеймур, Пол Д. (1980). «Разложение регулярных матроидов». Журнал комбинаторной теории . Серия B. 28 (3): 305–359. doi : 10.1016/0095-8956(80)90075-1 . hdl : 10338.dmlcz/101946 . Zbl  0443.05027.
• Truemper, Klaus (1992). Разложение матроида. Бостон, Массачусетс: Academic Press. ISBN 978-0-12-701225-4. MR  1170126 – через emis.de.
• Tutte, WT (1959). «Матроиды и графы». Труды Американского математического общества . 90 (3): 527–552. doi : 10.2307/1993185 . JSTOR  1993185. MR  0101527.
• Tutte, WT (1965). «Лекции о матроидах». Журнал исследований Национального бюро стандартов . Раздел B. 69 : 1–47.
• Tutte, WT (1971). Введение в теорию матроидов . Современные аналитические и вычислительные методы в науке и математике. Т. 37. Нью-Йорк, Нью-Йорк: American Elsevier Publishing Company. Zbl  0231.05027.
• Вамос, Питер (1978). «Отсутствующая аксиома теории матроидов утеряна навсегда». Журнал Лондонского математического общества . 18 (3): 403–408. doi :10.1112/jlms/s2-18.3.403.
• ван дер Варден, БЛ (1937). Современная алгебра .
• Welsh, DJA (1976). Теория матроидов . Монографии LMS. Том 8. Academic Press. ISBN 978-0-12-744050-7. Збл  0343.05002.
• Уайт, Нил, ред. (1986). Теория матроидов . Энциклопедия математики и ее приложений. Том 26. Кембридж, Великобритания: Cambridge University Press. ISBN 978-0-521-30937-0. Zbl  0579.00001 - через Интернет-архив (archive.org).
• Уайт, Нил, ред. (1987). Комбинаторная геометрия . Энциклопедия математики и ее приложений. Том 29. Кембридж, Великобритания: Cambridge University Press . ISBN 978-0-521-33339-9. Zbl  0626.00007 - через Интернет-архив (archive.org).
• Уайт, Нил, ред. (1992a). Matroid Applications . Энциклопедия математики и ее приложений. Том 40. Кембридж, Великобритания: Cambridge University Press. ISBN 978-0-521-38165-9. Zbl  0742.00052 - через Интернет-архив (archive.org).
• Уитни, Хасслер (1935). «Об абстрактных свойствах линейной зависимости». American Journal of Mathematics . 57 (3): 509–533. doi :10.2307/2371182. hdl : 10338.dmlcz/100694 . JSTOR  2371182. MR  1507091.— Перепечатано в Кунге (1986), стр. 55–79
• Уиттл, Джефф (1995). "Характеристика матроидов, представимых над GF(3), и рациональных чисел". Журнал комбинаторной теории . Серия B. 65 (2): 222–261. doi : 10.1006/jctb.1995.1052 .
• Заславский, Томас (1994). «Фреймовые матроиды и смещенные графы». Eur. J. Comb. 15 (3): 303–307. doi : 10.1006/eujc.1994.1034 . ISSN  0195-6698. Zbl  0797.05027.

Внешние ссылки

• «Матроид». Энциклопедия математики . EMS Press . 2001 [1994].

• Кинган, Сандра. «Теория матроидов». userhome.brooklyn.cuny.edu (академический персональный сайт). Бруклинский колледж . Бруклин, Нью-Йорк: Городской университет Нью-Йорка .— Большая библиография статей по матроидам, программного обеспечения для матроидов и ссылок.

• Локк, С. К. "Жадные алгоритмы". math.fau.edu (академический персональный сайт). Бока-Ратон, Флорида: Флоридский Атлантический университет .

• Пагано, Стивен Р. «Матроиды и знаковые графы». math.binghamton.edu (академический персональный сайт). Бингемтон, Нью-Йорк: Университет Бингемтона .

• Hubenthal, Mark. "A short look at matroids" (PDF) . math.washington.edu (академический персональный сайт). Seattle, WA: University of Washington . Архивировано из оригинала (PDF) 12 августа 2010 г.— Приводит доказательства утверждений в этой статье.

• Оксли, Джеймс. «Что такое матроид?» (PDF) . math.lsu.edu (академический персональный сайт). Батон-Руж, Луизиана: Университет штата Луизиана .

• Уайт, Нил, ред. (1992b). Matroid Applications. Cambridge University Press. ISBN 978-0-5213-8165-9. ISSN  0953-4806 – через Google Книги.