Матроид

Не путать с Metroid или Meteoroid .

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

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

Определение

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

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

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

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

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

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

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

Базы и схемы

Основная статья: Основа матроида

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

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

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

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

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

Функции ранга

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

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

• (R2) Для любого подмножества $A\subset E$, у нас есть $r(A)\leq |A|~.$

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

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

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

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

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

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

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

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

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

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

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

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

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

Квартиры

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

• (F1) Весь набор точек $E$ закрыт.

• (F2) Если $S$ и $T$ это квартиры, то $S\cap T$ это квартира.

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

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

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

Плоскости этого матроида однозначно соответствуют элементам решетки; плоскость, соответствующая элементу решетки $y$ это набор

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

Таким образом, решетка квартир этого матроида естественно изоморфна $L$.

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

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

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

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

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

Графоиды

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

• (G1) нет элемента $C$ (называемый «схемой») содержит еще один,

• (G2) нет элемента $D$ (называемый «косхемой») содержит еще один,

• (G3) нет настроек $C$ и установить $D$ пересекаются ровно в одном элементе, и

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

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

Примеры

Бесплатный матроид

Позволять $E$ быть конечным множеством. Набор всех подмножеств $E$ определяет независимые множества матроида. Его называют матроидом свободным $E$.

Униформа матроидов

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

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

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

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

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

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

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

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

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

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

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

Матрица ​ $A$ с записями в поле рождает матроид $M$ на своем наборе столбцов. Зависимыми наборами столбцов в матроиде являются те, которые линейно зависимы как векторы.

Этот матроид называется столбца матроидом $A$, и $A$ говорят, что представляет $M$.

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

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

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

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

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

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

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

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

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

• В любом ориентированном или неориентированном графе $G$ позволять $E$ и $F$ быть двумя различными наборами вершин. В наборе $E$, определить подмножество $U$ быть независимым, если есть $|U|$ вершинно-непересекающиеся пути из $F$ на $U$. Это определяет матроида на $E$ называется гаммоидом : называется строгим гаммоидом такой, для которого множество $E$ это все множество вершин $G$.

• В двудольном графе $G=(U,V,E)$, можно сформировать матроид, в котором элементами являются вершины с одной стороны $U$ бираздела, а независимые подмножества являются множествами концов паросочетаний графа. Это называется трансверсальным матроидом . и это частный случай гаммоида. Трансверсальные матроиды являются матроидами, двойственными строгим гамоидам.

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

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

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

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

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

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

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

Расширение поля порождает матроид:

Предполагать $F$ и $K$ поля с $K$ содержащий $F$. Позволять $E$ быть любым конечным подмножеством $K$.

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

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

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

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

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

Если $M$ является конечным матроидом, мы можем определить ортогональный или двойственный матроид $M^{*}$ взяв тот же базовый набор и назвав его базисом в $M^{*}$ тогда и только тогда, когда его дополнение является базисом в $M~.$ В этом нетрудно убедиться $M^{*}$ является матроидом и что двойственный $M^{*}$ является $M~.$

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

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

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

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

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

Пример

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

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

Основная статья: Матроид минор

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

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

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

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

Суммы и союзы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

В Maple есть пакет для работы с матроидами начиная с версии 2024.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

или напрямую как

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

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

Числа Уитни

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$F(M)=F(M-e)+F(M/e)$

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

$F(M\oplus M')=F(M)F(M')$

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

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

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

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

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

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

$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. Для каждого немаксимального (при включении множеств) независимого множества $\ I\$ и максимальное независимое множество $\ J\$, есть $\ x\in J\smallsetminus I\$ такой, что $\ I\cup \{x\}\$ является независимым.
4. Для каждого подмножества $\ X\$ базового пространства каждое независимое подмножество $\ I\$ из $\ X\$ может быть расширено до максимального независимого подмножества $\ X~.$

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Сусуму Курода

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

Ричард Радо

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

Хирокадзу Нисимура

WT Тутте

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

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

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

Джек Эдмондс

Джим Гилен

Юджин Лоулер

Ласло Ловаш

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

П. Д. Сеймур

Доминик Уэлш

См. также

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

Ссылки

• Брюн, Хеннинг; Дистель, Рейнхард; Криселл, Матиас; Пендавинг, Руди; Воллан, Пол (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; Капур, А. (2000). «Исключенные миноры для GF(4)-представимых матроидов». Журнал комбинаторной теории . Серия Б. 79 (2): 247–299. дои : 10.1006/jctb.2000.1963 . МР   1769191 .
• Гилен, Джим ; Джерардс, 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 . МР   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 Книги.