Матроид

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

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

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

Определение

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

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

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

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

• (I2) Каждое подмножество независимого множества является независимым, т. е. для каждого if then Это иногда называют наследственным свойством или свойством, замкнутым вниз . ${\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\smallsetminus 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}}~.}$

Это свойство (В2) называется свойством базисного обмена . Из этого свойства следует, что ни один член не может быть собственным подмножеством другого. ${\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\ ,}$

Разница называется нульностью подмножества. Это минимальное количество элементов, из которых необходимо удалить , чтобы получить независимое множество. Нулевое значение in называется нулевым значением. Разницу иногда называют корангом подмножества . ${\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) Для всех элементов и из и всех подмножеств if then ${\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) ни одно множество in и множество in не пересекаются ровно по одному элементу, и ${\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) . Матроиды столбцов — это просто векторные матроиды под другим названием, но часто есть причины отдать предпочтение матричному представлению. ^[б]

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

Основная проблема теории матроидов состоит в том, чтобы охарактеризовать матроиды, которые могут быть представлены в данном поле ; Гипотеза Роты описывает возможную характеристику любого конечного поля . Основными результатами на данный момент являются характеристики бинарных матроидов (представимых в GF(2)) благодаря Тутте (1950-е годы), троичных матроидов (представимых в трехэлементном поле) благодаря Риду и Биксби и отдельно Сеймуру (1970-е). и четвертичных матроидов (представимых в поле из 4 элементов) согласно Гилену, Джерардсу и Капуру (2000) . Это очень открытая территория. ^{[ нужно обновить? ]} ${\displaystyle F}$ harvp error: no target: CITEREFGeelenGerardsKapoor2000 (help)

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

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

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

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

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

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

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

• В двудольном графе можно сформировать матроид, в котором элементами являются вершины на одной стороне двудольного графа, а независимыми подмножествами являются множества конечных точек паросочетаний графа. Это называется трансверсальным матроидом , ^{[9] [10]} и является частным случаем гаммоида. ^[7] Трансверсальные матроиды являются матроидами, двойственными строгим гамоидам. ^[8] ${\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}$

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

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

Основные конструкции

Есть несколько стандартных способов сделать новых матроидов из старых.

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

Если это конечный матроид, мы можем определить ортогональный или двойственный матроид , взяв тот же основной набор и назвав его базисом в том и только том случае, если его дополнение является базисом в. Нетрудно проверить, что это матроид и что двойственный к is ^[13] ${\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)~.}$

Согласно матроидной версии теоремы Куратовского , двойственный графический матроид является графическим матроидом тогда и только тогда, когда является матроидом плоского графа . В этом случае двойственный векторный матроид является матроидом двойственного графа из ^[14]. Двойственный векторному матроиду, представимый в определенном поле, также представим и над. Двойственный трансверсальному матроиду является строгим гамоидом, и наоборот. ${\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 являются в точности результатом последовательности удалений: порядок не имеет значения. ^{[15] [16]}

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

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

Суммы и союзы

Пусть 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 .

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

• Элемент, образующий одноэлементную схему М , называется петлей . Эквивалентно, элемент является циклом, если он не принадлежит ни одному базису. ^{[6] [21]}

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

Цикл и колоп взаимно двойственны. ^[21]

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

Программное обеспечение Матроид

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

Обе системы математического программного обеспечения с открытым исходным кодом SAGE и Macaulay2 содержат пакеты maroid.

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

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

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

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

${\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 матроида. ^[30]

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

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

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

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

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

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

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

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

Бета-инвариант неотрицательен и равен нулю тогда и только тогда, когда он отключен, пуст или представляет собой цикл. В противном случае оно зависит только от решетки квартир. Если не имеет петель и колец, то ^[32] ${\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)}~.}$

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

${\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)~.}$

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

Существует дальнейшее определение рекурсии путем удаления и сокращения. ^[35] Тождество удаления-сокращения

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

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

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

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

Полином Тутте графа — это полином Тутте его матроида цикла. ${\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-х годов теоретики матроидов обратились к более общему понятию, которое разделяло бы различные аспекты конечных матроидов и обобщало бы их двойственность. В ответ на этот вызов были определены многие понятия бесконечных матроидов, но вопрос оставался открытым. Один из подходов, рассмотренных Д. А. Хиггсом, стал известен как B-матроиды и изучался Хиггсом, Оксли и другими в 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))

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

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

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

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

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

В текущий период (примерно с 2000 года) проект «Matroid Minors Project» Гилена , Джерардса, Уиттла и других ^[e] добился существенных успехов в теории структуры матроидов. Многие другие также внесли свой вклад в ту часть теории матроидов, которая (в первое и второе десятилетия XXI века) процветает.

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

Среди математиков, пионеров изучения матроидов,

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

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

Ричард Радо

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

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

WT Тутте

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

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

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

Джек Эдмондс

Джим Гилен

Юджин Лоулер

Ласло Ловаш

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

П. Д. Сеймур

Доминик Уэлш

Сноски

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

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

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

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

• Антиматроид
• Матроид Кокстера
• Гридоид
• Ориентированный матроид
• Полиматроид
• Предгеометрия (теория моделей)

Цитаты

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

Рекомендации

• Брюн, Хеннинг; Дистель, Рейнхард; Криселл, Матиас; Пендавинг, Руди; Воллан, Пол (2013). «Аксиомы бесконечных матроидов». Достижения в математике . 239 : 18–46. arXiv : 1003.3919 . дои : 10.1016/j.aim.2013.01.011 . МР  3045140. S2CID  10436077.

• Брайант, Виктор; Идеально, Хейзел (1980). Теория независимости в комбинаторике . Лондон, Великобритания и Нью-Йорк, штат Нью-Йорк: Чепмен и Холл. ISBN 978-0-412-22430-0.

• Брылавски, Томас Х. (1972). «Разложение комбинаторной геометрии». Труды Американского математического общества . 171 : 235–282. дои : 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 (переработанная ред.). Ауссуа, Франция: Берлин, Гейдельберг: Springer (опубликовано в 2003 г.). стр. 11–26. CiteSeerX  10.1.1.454.4060 . дои : 10.1007/3-540-36478-1_2. ISBN 978-3-540-36478-8.

• Гилен, Джим ; Джерардс, AMH; Уиттл, Джефф (2007). «К теории матроидно-минорной структуры». В Гриммете, Джеффри; и другие. (ред.). Комбинаторика, сложность и случайность: дань уважения Доминику Уэлшу . Оксфордская серия лекций по математике и ее приложениям. Том. 34. Оксфорд, Великобритания: Издательство Оксфордского университета. стр. 72–82.

• Джерардс, AMH (1989). «Краткое доказательство характеристики Тутте полностью унимодулярных матриц». Линейная алгебра и ее приложения . 114–115: 207–212. дои : 10.1016/0024-3795(89)90461-8 .

• Кан, Джефф; Кунг, Джозеф PS (1982). «Разновидности комбинаторных геометрий». Труды Американского математического общества . 271 (2): 485–499. дои : 10.2307/1998894 . JSTOR  1998894.

• Кинган, Роберт; Кинган, Сандра (2005). «Программный комплекс для матроидов». Графики и открытия . Серия DIMACS по дискретной математике и теоретической информатике. стр. 287–296.

• Кашьяп, Навин; Солянин, Эмина; Фонтобель, Паскаль (2009). Приложения теории матроидов и комбинаторной оптимизации к теории информации и кодирования (PDF) (Отчет) . Проверено 4 октября 2014 г. - через www.birs.ca.

• Кунг, Джозеф PS, изд. (1986). Справочник по теории матроидов. Бостон, Массачусетс: Биркхойзер. дои : 10.1007/978-1-4684-9199-9. ISBN 978-0-8176-3173-4. MR  0890330 - через Интернет-архив (archive.org).

• Маклейн, Сондерс (1936). «Некоторые интерпретации абстрактной линейной зависимости с точки зрения проективной геометрии». Американский журнал математики . 58 (1): 236–240. дои : 10.2307/2371070. JSTOR  2371070.

• Минти, Джордж Дж. (1966). «Об аксиоматических основах теорий направленных линейных графов, электрических сетей и сетевого программирования». Журнал математики и механики . 15 : 485–520. МР  0188102.

• Нил, Дэвид Л.; Нойдауэр, Нэнси А. (2009). «Матроиды, которых вы знали» (PDF) . Журнал «Математика» . 82 (1): 26–41. дои : 10.4169/193009809x469020 . Проверено 4 октября 2014 г. - через Математическая ассоциация Америки (maa.org).

• Нисимура, Хирокадзу; Курода, Сусуму, ред. (2009). Затерянный математик Такео Накасава: забытый отец теории матроидов . Базель, Швейцария: Birkhäuser Verlag. дои : 10.1007/978-3-7643-8573-6. ISBN 978-3-7643-8572-9. МР  2516551. Збл  1163.01001.

• Оксли, Джеймс (1992). Теория матроидов . Оксфорд, Великобритания: Издательство Оксфордского университета. ISBN 978-0-19-853563-8. МР  1207587. Збл  0784.05002.

• Рецкий, Андраш (1989). Теория матроидов и ее приложения в теории электрических сетей и статике . Алгоритмы и комбинаторика. Том. 6. Берлин, Делавэр и Будапешт, Венгрия: Springer-Verlag и Akademiai Kiado. дои : 10.1007/978-3-662-22143-3. ISBN 978-3-540-15285-9. MR  1027839. S2CID  117772439 – через Интернет-архив (archive.org).

• Сапоженко, А.А. (2001) [1994], «Матроид», Математическая энциклопедия , EMS Press

• Сеймур, Пол Д. (1980). «Разложение обычных матроидов». Журнал комбинаторной теории . Серия Б. 28 (3): 305–359. дои : 10.1016/0095-8956(80)90075-1 . hdl : 10338.dmlcz/101946 . Збл  0443.05027.

• Трумпер, Клаус (1992). Разложение матроида. Бостон, Массачусетс: Академическая пресса. ISBN 978-0-12-701225-4. MR  1170126 – через emis.de.

• Тутте, WT (1959). «Матроиды и графы». Труды Американского математического общества . 90 (3): 527–552. дои : 10.2307/1993185 . JSTOR  1993185. МР  0101527.

• Тутте, WT (1965). «Лекции по матроидам». Журнал исследований Национального бюро стандартов . Раздел Б. 69 : 1–47.

• Тутте, WT (1971). Введение в теорию матроидов . Современные аналитические и вычислительные методы в науке и математике. Том. 37. Нью-Йорк, штат Нью-Йорк: Американская издательская компания Elsevier. Збл  0231.05027.

• Вамос, Питер (1978). «Недостающая аксиома теории матроидов утеряна навсегда». Журнал Лондонского математического общества . 18 (3): 403–408. дои : 10.1112/jlms/s2-18.3.403.

• ван дер Варден, БЛ (1937). Современная алгебра .

• Валлийский, DJA (1976). Теория матроидов . Монографии LMS. Том. 8. Академическая пресса. ISBN 978-0-12-744050-7. Збл  0343.05002.

• Уайт, Нил, изд. (1986). Теория матроидов . Энциклопедия математики и ее приложений. Том. 26. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 978-0-521-30937-0. Zbl  0579.00001 - через Интернет-архив (archive.org).

• Уайт, Нил, изд. (1987). Комбинаторные геометрии . Энциклопедия математики и ее приложений. Том. 29. Кембридж, Великобритания: Издательство Кембриджского университета . ISBN 978-0-521-33339-9. Zbl  0626.00007 - через Интернет-архив (archive.org).

• Уайт, Нил, изд. (1992а). Матроидные приложения . Энциклопедия математики и ее приложений. Том. 40. Кембридж, Великобритания: Издательство Кембриджского университета. ISBN 978-0-521-38165-9. Zbl  0742.00052 - через Интернет-архив (archive.org).

• Уитни, Хасслер (1935). «Об абстрактных свойствах линейной зависимости». Американский журнал математики . 57 (3): 509–533. дои : 10.2307/2371182. hdl : 10338.dmlcz/100694 . JSTOR  2371182. МР  1507091.- Перепечатано в Kung (1986), стр. 55–79.

• Уиттл, Джефф (1995). «Характеристика матроидов, представимых над GF (3) и рациональными числами». Журнал комбинаторной теории . Серия Б. 65 (2): 222–261. дои : 10.1006/jctb.1995.1052 .

• Заславский, Томас (1994). «Кадровые матроиды и смещенные графы». Евро. Дж. Комб. 15 (3): 303–307. дои : 10.1006/eujc.1994.1034 . ISSN  0195-6698. Збл  0797.05027.

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

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

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

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

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

• Хубенталь, Марк. «Краткий взгляд на матроидов» (PDF) . math.washington.edu (личный академический сайт). Сиэтл, Вашингтон: Вашингтонский университет . Архивировано из оригинала (PDF) 12 августа 2010 года.— Приводит доказательства утверждений данной статьи.

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

• Уайт, Нил, изд. (1992б). Матроидные приложения. Издательство Кембриджского университета. ISBN 978-0-5213-8165-9. ISSN  0953-4806 – через Google Книги.