Matroid

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

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

Определение [ править ]

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

Независимые наборы [ править ]

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

(I1) пустое множество не зависит, то есть . В качестве альтернативы, по меньшей мере , одно подмножество является независимым, т.е. .${\ displaystyle \ emptyset \ in {\ mathcal {I}}}$${\ displaystyle E}$${\ Displaystyle {\ mathcal {I}} \ neq \ emptyset}$

(I2) Каждое подмножество независимого набора является независимым, т. Е. Для каждого , если, то . Иногда это называют наследственным свойством или свойством , закрытым вниз .${\ Displaystyle A '\ substeq A \ substeq E}$${\ displaystyle A \ in {\ mathcal {I}}}$${\ displaystyle A '\ in {\ mathcal {I}}}$

(I3) Если и являются двумя независимыми наборами (т. Е. Каждый набор является независимым) и имеет больше элементов, чем , то существует такое, что находится в . Иногда это называется свойством увеличения или свойством обмена независимыми наборами .${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle x \ in A \ backslash B}$${\ Displaystyle В \ чашка \ {х \}}$${\ displaystyle {\ mathcal {I}}}$

Первые два свойства определяют комбинаторную структуру, известную как система независимости (или абстрактный симплициальный комплекс ).

Базы и схемы [ править ]

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

Зависимые множества, основы или схемы матроида полностью характеризуют матроид: набор является независимым тогда и только тогда, когда он не зависит, тогда и только тогда, когда он является подмножеством базиса, и тогда и только тогда, когда он не содержать схемы. Наборы зависимых множеств, баз и схем имеют простые свойства, которые могут быть приняты как аксиомы для матроида. Например, можно определить матроид как пару , где - конечное множество, как и раньше, и набор подмножеств , называемых «базами», со следующими свойствами: ^[4]${\ 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 \ setminus B}$${\ displaystyle b \ in B \ setminus A}$${\ displaystyle (A \ setminus \ {a \}) \ cup \ {b \} \ in {\ mathcal {B}}}$

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

Функции ранжирования [ править ]

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

• Значение функции ранга всегда является неотрицательным целым числом .
• Для любого подмножества у нас есть .${\ Displaystyle A \ подмножество E}$${\ Displaystyle г (А) \ leq | А |}$
• Для любых двух подмножеств , мы имеем: . То есть ранг - это субмодулярная функция .${\ displaystyle A, B \ subset E}$${\displaystyle r(A\cup B)+r(A\cap B)\leq r(A)+r(B)}$
• Для любого множества и элемента , мы имеем: . Из первого неравенства в более общем виде следует, что если , то . То есть ранг - это монотонная функция .${\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)\to {\mathcal {P}}(E)}$${\displaystyle {\mathcal {P}}}$

• Для всех подмножеств из , .${\displaystyle X}$${\displaystyle E}$${\displaystyle X\subseteq \operatorname {cl} (X)}$
• Для всех подмножеств из , .${\displaystyle X}$${\displaystyle E}$${\displaystyle \operatorname {cl} (X)=\operatorname {cl} (\operatorname {cl} (X))}$
• Для всех подмножеств и из с , .${\displaystyle X}$${\displaystyle Y}$${\displaystyle E}$${\displaystyle X\subseteq Y}$${\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)}$
• Для всех элементов , а также из и всех подмножеств из , если потом .${\displaystyle a}$${\displaystyle b}$${\displaystyle E}$${\displaystyle Y}$${\displaystyle E}$${\displaystyle a\in \operatorname {cl} (Y\cup \{b\})\setminus \operatorname {cl} (Y)}$${\displaystyle b\in \operatorname {cl} (Y\cup \{a\})\setminus \operatorname {cl} (Y)}$

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

Квартиры [ править ]

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

• Весь набор точек закрыт.${\displaystyle E}$
• Если и являются квартирами, то квартира.${\displaystyle S}$${\displaystyle T}$${\displaystyle S\cap T}$
• Если это квартира, то каждый элемент находится ровно в одной из квартир, которые покрывают (это означает, что он правильно содержит, но нет квартиры между и ).${\displaystyle S}$${\displaystyle E\setminus 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 , но такое, что добавление к нему любого другого элемента создает охватывающий набор. ^[6]${\displaystyle r}$${\displaystyle r-1}$${\displaystyle E}$

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

• Не существует внятных наборов и в с . То есть гиперплоскости образуют семейство Спернеров .${\displaystyle X}$${\displaystyle Y}$${\displaystyle {\mathcal {H}}}$${\displaystyle X\subseteq Y}$
• Для каждого и отличного с существует с .${\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}$

• ни один элемент (называемый "схемой") не содержит другого,${\displaystyle C}$
• ни один элемент из (называемого «кокосхемой») не содержит другого,${\displaystyle D}$
• не установленные и установленные в пересекаются ровно в одном элементе, и${\displaystyle C}$${\displaystyle D}$
• всякий раз, когда он представлен как непересекающееся объединение подмножеств с (одноэлементным набором), то либо существует такое, что, либо существует такое, что${\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}$

Матроиды из линейной алгебры [ править ]

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

• Если - любое конечное подмножество векторного пространства , то мы можем определить матроид на , взяв независимые множества в качестве линейно независимых подмножеств . Справедливость аксиом независимого множества для этого матроида следует из леммы об обмене Стейница . Если это матроид, который можно определить таким образом, мы говорим, что набор представляет . Такие матроиды называются векторными матроидами . Важным примером определяемого таким образом матроида является матроид Фано, матроид третьего ранга, полученный из плоскости Фано , конечная геометрия${\displaystyle E}$ ${\displaystyle V}$${\displaystyle M}$${\displaystyle E}$${\displaystyle M}$${\displaystyle E}$${\displaystyle M}$${\displaystyle E}$ ${\displaystyle M}$с семью точками (семь элементов матроида) и семью линиями (собственно нетривиальные плоскости матроида). Это линейный матроид, элементы которого можно описать как семь ненулевых точек в трехмерном векторном пространстве над конечным полем GF (2) . Однако невозможно обеспечить аналогичное представление матроида Фано с использованием вещественных чисел вместо GF (2).
• Матрица с элементами в поле приводит к матроиду на его наборе столбцов. Зависимые наборы столбцов в матроиде являются линейно зависимыми как векторы. Это Матроид называется колонна матроидом из , и , как говорят, представляют . Например, матроид Фано может быть представлен таким образом как 3 × 7 (0,1) -матрица${\displaystyle A}$${\displaystyle M}$${\displaystyle A}$${\displaystyle A}$ ${\displaystyle M}$. Матроиды столбцов - это просто векторные матроиды под другим именем, но часто есть причины в пользу матричного представления. (Существует одна технической разница: столбец матроид может иметь различные элементы , которые являются таким же вектором, а вектор матроид , как определенно выше , не может Обычно эта разница незначительна и может быть проигнорирована, но позволяя. Быть мультимножеством векторов один приносит два определения в полное согласие.)${\displaystyle E}$

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

Регулярный матроидом является матроидом , что представимо над всеми возможными полями. Матроидом Vámos является простейшим примером матроиду , который не представима над любым полем.

Матроиды из теории графов [ править ]

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

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

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

• Двоякокруговой матроид графа определяется путем вызова множества ребер независимого , если каждое связное подмножество содержит не более одного цикла.
• В любом ориентированном или неориентированном графе пусть и - два выделенных набора вершин. В наборе определите подмножество, которое будет независимым, если | | вершинно-непересекающиеся пути из на . Это определяет матроид на называется gammoid : ^[8] строгое gammoid один , для которых множество представляет все множество вершин . ^[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]} , и это особый случай gammoid. ^[8] Трансверсальные матроиды - это матроиды, двойственные к строгим гаммоидам. ^[9]${\displaystyle G=(U,V,E)}$${\displaystyle U}$
• Графические матроиды были обобщены на матроиды из подписанных графиков , графиков усиления и смещенных графиков . Граф с выделенным классом линейного циклов, известным как «смещенным граф» , имеет два матроид, известные как кадр матроида и подъем матроид из смещенного графа. Если каждый цикл принадлежит выделенному классу, эти матроиды совпадают с матроидом цикла . Если цикл не выделяется, матроид каркаса является двукруглым матроидом${\displaystyle G}$${\displaystyle B}$${\displaystyle (G,B)}$${\displaystyle G}$${\displaystyle G}$. Знаковый граф, чьи ребра помечены знаками, и граф усиления, который представляет собой граф, чьи ребра помечены ориентируемым образом от группы, каждый порождает смещенный граф и, следовательно, имеет матроиды каркаса и подъема.
• На графиках Laman образуют основы двумерный жесткости матроиды , матроида , определенную в теории структурной жесткости .
• Позвольте быть связным графом и быть его множеством ребер. Пусть совокупность подмножеств из таких , что по - прежнему связаны. Тогда , чей элемент множество и в своем классе независимых множеств, является матроид называется связь матроид из . Функция ранга - это цикломатическое число подграфа, индуцированного на подмножестве ребер , которое равно количеству ребер вне максимального леса этого подграфа, а также количеству независимых циклов в нем.${\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}$

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

Третий исходный источник теории матроидов - теория поля .

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

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

Основные конструкции [ править ]

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

Двойственность [ править ]

Если M является конечным матроидом, мы можем определить ортогональный или двойной матроид M *, взяв тот же базовый набор и вызов набора на основе в М * тогда и только тогда , когда его дополнение является базисом в М . Это не трудно проверить , что M * является матроидом и двойственными М * являются М . ^[14]

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

• Набор независим в М * тогда и только тогда , когда его дополнение пролетов М .
• Набор является схемой М * тогда и только тогда , когда его дополнением является coatom в М .
• Ранговая функция двойника равна .${\displaystyle r^{*}(S)=|S|-r(M)+r\left(E\setminus S\right)}$

Согласно матроидной версии теоремы Куратовски , двойник графического матроида M является графическим матроидом тогда и только тогда, когда M - матроид плоского графа . В этом случае двойственного М является матроидом из двойственного графа из G . ^[15] Сопряженный вектор матроид представимы над определенным полем Р является также представим над F . Двойник трансверсального матроида - это строгий гаммоид и наоборот.

Пример

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

Несовершеннолетние [ править ]

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

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

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

Суммы и союзы [ править ]

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

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

Дополнительная терминология [ править ]

Пусть М будет матроидом с основным набором элементами Е .

• E можно назвать наземный набор из M . Его элементы можно назвать точки из М .
• Подмножество Е охватывает М , если его замыкание Е . Набор называется охватить замкнутое множество K , если его замыкание K .
• Распорка из матроиды является размером наималейшей цепи или зависимого набора.
• Элемент, образующий одноэлементную схему M , называется петлей . Эквивалентно, элемент является циклом, если он не принадлежит ни одной основе. ^{[7] [22]}
• Элемент , который не принадлежит ни цепи называется coloop или перешейка . Эквивалентно элемент является кольцом, если он принадлежит каждой основе. Петля и петля взаимно двойственны. ^[22]
• Если два элемента множества { F, G } является схема М , то е и г являются параллельными в М . ^[7]
• Матроид называется простым, если в нем нет схем, состоящих из 1 или 2 элементов. То есть в нем нет ни петель, ни параллельных элементов. Также используется термин комбинаторная геометрия . ^[7] Простой матроид , полученные из других матроидов M , удалив все петлю и удаляя один элемент из каждой схемы 2-элемента , пока нет 2-элементных схем остаются называются упрощением из М . ^[23] Матроид является таким же простым, если его двойственный матроид прост. ^[24]
• Объединение схем иногда называют цикл из М . Таким образом, цикл является дополнением к плоскости двойственного матроида. (Это использование противоречит общепринятому значению «цикл» в теории графов.)
• Сепаратор из М представляет собой подмножество S из Й таких , что . Собственно или нетривиальный сепаратор представляет собой сепаратор , который не является ни Е , ни пустое множество. ^[25] неприводимым сепаратор представляет собой сепаратор , который не содержит никакого другого непустого сепаратора. Неприводимыми разделители разбивают землю множество E .${\displaystyle r(S)+r(E-S)=r(M)}$
• Матроид, который не может быть записан как прямая сумма двух непустых матроидов или, что то же самое, не имеет подходящих разделителей, называется связным или неприводимым . Матроид связан тогда и только тогда, когда его дуал связан. ^[26]
• Максимальный неприводимый подматроид из М называется компонентом из М . Компонент - это ограничение M на неприводимый разделитель, и наоборот, ограничение M на неприводимый разделитель является компонентом. Разделитель - это объединение компонентов. ^[25]
• Матроид M называется каркасным матроидом, если он или матроид, который его содержит, имеет такую ​​основу, что все точки M содержатся в линиях, соединяющих пары базисных элементов. ^[27]
• Матроид называется матроидом для мощения, если все его цепи имеют размер, по крайней мере, равный его рангу. ^[28]
• Матроидом многогранник является выпуклой оболочкой из индикаторных векторов фундаментов .${\displaystyle P_{M}}$${\displaystyle M}$

Алгоритмы [ править ]

Жадный алгоритм [ править ]

Взвешенный матроид является матроидом вместе с функцией от ее элементов к неотрицательным действительным числам . Вес подмножества элементов определяется как сумма весов элементов в подмножестве. Жадный алгоритм может быть использован , чтобы найти максимальный вес основу матроиды, исходя из пустого множества и неоднократно добавления одного элемента за один раз, на каждый шаге выбор максимального веса элемента среди элементов, добавление бы сохранить независимость расширенного набора. ^[29] Этому алгоритму не нужно ничего знать о деталях определения матроида, если он имеет доступ к матроиду через оракул независимости., подпрограмма для проверки независимости набора.

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

Понятие матроида было обобщено, чтобы учесть другие типы множеств, на которых жадный алгоритм дает оптимальные решения; см greedoid и матроиды вложения для получения дополнительной информации.

Разбиение Matroid [ править ]

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

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

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

Программное обеспечение Matroid [ править ]

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

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

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

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

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

Характеристический полином из М (который иногда называют хроматическим многочленом , ^[31] , хотя это не считается красителей), определяется как

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

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

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

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

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

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

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

Бета-инвариант [ править ]

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

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

Бета-инвариант неотрицателен и равен нулю тогда и только тогда, когда M отключен, или пуст, или цикл. В противном случае это зависит только от решетки квартир М . Если в M нет петель и колуп, то β ( M ) = β ( M ^∗ ). ^[34]

Многочлен Тутте [ править ]

Тутта многочлен из матроиды, Т _М  ( х , у ), обобщает характеристический полином для двух переменных. Это дает ему больше комбинаторных интерпретаций, а также придает ему свойство двойственности.

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

что влечет за собой ряд двойственности между свойствами M и свойствами 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)}.}$

Из этого определения легко увидеть, что характеристический многочлен с точностью до простого множителя является оценкой T _M , а именно:

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

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

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

${\displaystyle F(M)=F(M-e)+F(M/e)}$когда нет ни петли, ни колупа.${\displaystyle e}$

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

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

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

Тутта многочлен Т _G   графа является Тутта многочлен Т _{М ( G )} его матроиды цикла.

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

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

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

Следующее простейшее бесконечное обобщение - финитарные матроиды. Матроид финитен, если он обладает свойством

${\displaystyle x\in \operatorname {cl} (Y)\Leftrightarrow (\exists Y'\subseteq Y)Y'{\text{ is finite and }}x\in \operatorname {cl} (Y').}$

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

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

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

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

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

История [ править ]

Теория матроидов была представлена Хасслером Уитни  ( 1935 ). Его также независимо открыл Такео Накасава , о работе которого забыли на долгие годы ( Nishimura & Kuroda 2009 ).

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

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

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

В 1950-х годах В. Т. Тутте стал ведущей фигурой в теории матроидов, и эту позицию он удерживал на протяжении многих лет. Его вклады были многочисленны, включая характеристику бинарных , обычных и графических матроидов исключенными несовершеннолетними ; теорема о представимости регулярного матроида; теория цепных групп и их матроидов; и инструменты, которые он использовал для доказательства многих своих результатов, «Теорема о пути» и « Теорема о гомотопии Тутте » (см., например, Tutte, 1965 ), которые настолько сложны, что более поздние теоретики приложили большие усилия, чтобы устранить необходимость использования их в доказательствах. (Прекрасным примером является короткое доказательство AMH Gerards (1989 ) характеризации Тутте обычных матроидов.)

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

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

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

К этому времени появилось много других важных участников, но не следует упускать из виду расширение Джеффа Уиттла на троичные матроиды описания Тутте бинарных матроидов, представимых над рациональными числами ( Whittle, 1995 ), что, возможно, является самым большим вкладом 1990-х годов. . В текущий период (примерно с 2000 года) проект Matroid Minors Project Джима Гилена , Джерардса , Уиттла и других, который пытается дублировать для матроидов, которые могут быть представлены в конечном поле, успех проекта Robertson – Seymour Graph Minors (см. Робертсон –Теорема Сеймура), внесла существенный прогресс в структурную теорию матроидов. Многие другие также внесли свой вклад в ту часть теории матроидов, которая (в первое и второе десятилетия 21 века) процветает.

Исследователи [ править ]

Среди математиков , пионеров в изучении матроидов, - Такео Накасава , ^[38] Сондерс Мак Лейн , Ричард Радо , У. Т. Тутте , Б.Л. ван дер Варден и Хасслер Уитни . Среди других крупных участников - Джек Эдмондс , Джим Гилен , Юджин Лоулер , Ласло Ловас , Джан-Карло Рота , PD Сеймур и Доминик Уэлш .

См. Также [ править ]

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

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

Ссылки [ править ]

• Брун, Хеннинг; Дистель, Рейнхард; Кризелл, Матиас; Пендавинг, Руди; Воллан, Пол (2013), «Аксиомы для бесконечных матроидов», Успехи в математике , 239 : 18–46, arXiv : 1003.3919 , doi : 10.1016 / j.aim.2013.01.011 , MR  3045140 , S2CID  10436077.
• Брайант, Виктор; Совершенный, Хейзел (1980), Теория независимости в комбинаторике , Лондон и Нью-Йорк: Чепмен и Холл, ISBN 978-0-412-22430-0.
• Brylawski, Томас Х. (1972), "Разложение по комбинаторной геометрии", Труды Американского математического общества , 171 : 235-282, DOI : 10,2307 / 1996381 , JSTOR  1996381.
• Крапо, Генри Х. (1969), "О Tutte Полином", Aequationes Mathematicae , 3 (3): 211-229, DOI : 10.1007 / BF01817442 , S2CID  119602825.
• Крапо, Генри Х .; Рота, Джан-Карло (1970), Об основах комбинаторной теории: комбинаторные геометрии , Кембридж, Массачусетс: MIT Press, ISBN 978-0-262-53016-3, MR  0290980.
• Гилен, Джим; Джерардс, AMH; Уиттл, Джефф (2007), «К теории структуры матроидов-минор», у Гримметта, Джеффри; и другие. (ред.), Комбинаторика, сложность и шанс: дань уважения Доминику Уэлшу , Оксфордская серия лекций по математике и ее приложениям, 34 , Oxford: Oxford University Press, стр. 72–82.
• Gerards, АМГ (1989), "Короткое доказательство характеристики TUTTE о совершенно унимодулярными матриц", Линейная алгебра и ее применения , 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.
• Кунг, Джозеф П.С., изд. (1986), Справочник по теории матроидов , Бостон: Birkhäuser, DOI : 10.1007 / 978-1-4684-9199-9 , ISBN 978-0-8176-3173-4, Руководство по ремонту  0890330.
• Mac Lane, Saunders (1936), "Некоторые интерпретации абстрактной линейной зависимости с точки зрения проективной геометрии", Американский журнал математики , 58 (1): 236-240, DOI : 10,2307 / 2371070 , JSTOR  2371070.
• Минти, Джордж Дж. (1966), «Об аксиоматических основах теорий ориентированных линейных графов, электрических сетей и сетевого программирования», Журнал математики и механики , 15 : 485–520, MR  0188102.
• Нисимура, Хирокадзу; Курода, Сусуму, ред. (2009), Пропавший математик, Такео Накасава. Забытый отец теории матроидов , Базель: Birkhäuser Verlag, doi : 10.1007 / 978-3-7643-8573-6 , ISBN 978-3-7643-8572-9, Руководство по ремонту  2516551 , Zbl  1163.01001.
• Оксли, Джеймс (1992), Теория матроидов , Оксфорд: Oxford University Press, ISBN 978-0-19-853563-8, Руководство по ремонту  1207587 , Zbl  0784.05002.
• Рекски, Андраш (1989), Теория матроидов и ее приложения в теории электрических сетей и в статике , алгоритмах и комбинаторике, 6 , Берлин и Будапешт: Springer-Verlag and Akademiai Kiado, doi : 10.1007 / 978-3-662-22143-3 , ISBN 978-3-540-15285-9, MR  1027839.
• Сапоженко, А.А. (2001) [1994], "Матроид" , Энциклопедия математики , EMS Press
• Seymour, Пол Д. (1980), "Разложение регулярных матроидов", Журнал комбинаторной теории, серии B , 28 (3): 305-359, DOI : 10,1016 / 0095-8956 (80) 90075-1 , ЛВП : 10338 .dmlcz / 101946 , Zbl  0443.05027.
• Truemper, Клаус (1992), Разложение Matroid , Бостон: Academic Press, ISBN 978-0-12-701225-4, Руководство по ремонту  1170126.
• Tutte, WT (1959), "Матроиды и графики", Труды Американского математического общества , 90 (3): 527-552, DOI : 10,2307 / 1993185 , JSTOR  1993185 , MR  0101527.
• Тутт, У. Т. (1965), «Лекции по матроидам», Журнал исследований Национального бюро стандартов, секция B , 69 : 1–47.
• Тутт, У. Т. (1971), Введение в теорию матроидов , Современные аналитические и вычислительные методы в науке и математике, 37 , Нью-Йорк: American Elsevier Publishing Company, Zbl  0231.05027.
• Vámos, Питер (1978), "Отсутствующий аксиомой теории матроидов теряется навсегда", журнал Лондонского математического общества , 18 (3): 403-408, DOI : 10.1112 / jlms / s2-18.3.403.
• ван дер Варден, Б. Л. (1937), Современная алгебра.
• Валлийский, DJA (1976), Теория матроидов , Монографии LMS, 8 , Academic Press, ISBN 978-0-12-744050-7, Zbl  0343,05002.
• Уайт, Нил, изд. (1986), Теория матроидов , Энциклопедия математики и ее приложений, 26 , Кембридж: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl  0579,00001.
• Уайт, Нил, изд. (1987), комбинаторные геометрии , Энциклопедия математики и ее приложений, 29 , Кембридж: Cambridge University Press , ISBN 978-0-521-33339-9, Zbl  0626,00007
• Уайт, Нил, изд. (1992), Приложения Matroid , Энциклопедия математики и ее приложений, 40 , Кембридж: Издательство Кембриджского университета, ISBN 978-0-521-38165-9, Zbl  0742,00052.
• Уитни, Хасслер (1935), «Об абстрактных свойствах линейной зависимости», American Journal of Mathematics , 57 (3): 509–533, doi : 10.2307 / 2371182 , hdl : 10338.dmlcz / 100694 , JSTOR  2371182 , MR  1507091. Перепечатано в Kung (1986) , pp. 55–79.
• Уиттл, Джефф (1995), «Характеристика матроидов, представимых над GF (3), и рациональные числа» (PDF) , Журнал комбинаторной теории, серия B , 65 (2): 222–261, doi : 10.1006 / jctb. 1995.1052^{[ постоянная мертвая ссылка ]} .

Внешние ссылки [ править ]

• "Matroid" , Энциклопедия математики , EMS Press , 2001 [1994]
• Кинган, Сандра: Теория матроидов . Большая библиография статей о матроидах, программного обеспечения матроидов и ссылок.
• Локк, СК: Жадные алгоритмы .
• Пагано, Стивен Р.: Матроиды и подписанные графы .
• Марк Хубенталь: Краткий обзор Matroids ( PDF ) (содержат доказательства утверждений этой статьи)
• Джеймс Оксли: Что такое матроид? (PDF)
• Нил Уайт: Приложения для Matroid