Основа матроида

Максимальное независимое множество матроида

В математике базисом матроида называется максимальное независимое множество матроида, то есть независимое множество, которое не содержится ни в каком другом независимом множестве .

Примеры

В качестве примера рассмотрим матроид над базовым множеством R ² (векторы в двумерной евклидовой плоскости) со следующими независимыми множествами:

{ {}, {(0,1)}, {(2,0)}, {(0,1), (2,0)}, {(0,3)}, {(0,3),( 2,0)} }.

Он имеет две базы, которые являются множествами {(0,1),(2,0)} , {(0,3),(2,0)}. Это единственные независимые множества, которые являются максимальными по включению.

Базис имеет специализированное название в нескольких специализированных видах матроидов: ^[1]

• В графическом матроиде , где независимые множества являются лесами, основания называются остовными лесами графа.
• В трансверсальном матроиде , где независимые множества являются конечными точками паросочетаний в данном двудольном графе , основания называются трансверсалями .
• В линейном матроиде , где независимые множества являются линейно-независимыми множествами векторов в заданном векторном пространстве, базисы просто называются базисами векторного пространства. Следовательно, понятие базиса матроида обобщает понятие базиса из линейной алгебры .
• В однородном матроиде , где независимые множества — это все множества с мощностью не более k (для некоторого целого числа k ), основания — это все множества с мощностью точно k .
• В матроиде разбиения , где элементы разбиты на категории, а независимые множества — это все множества, содержащие не более k _c элементов из каждой категории c, базами являются все множества, которые содержат ровно k _c элементов из категории c .
• В свободном матроиде , где все подмножества базового множества E независимы, единственным базисом является E.

Характеристики

Обмен

Все матроиды удовлетворяют следующим свойствам для любых двух различных баз и : ^{[2] [3]} ${\displaystyle A}$ ${\displaystyle B}$

• Свойство обмена базисом : если , то существует элемент, являющийся базисом. ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$
• Симметричное свойство обмена базисами : если , то существует элемент, такой что и являются базисами. Бруальди ^[4] показал, что это фактически эквивалентно свойству обмена базисами. ${\displaystyle a\in A\setminus B}$ ${\displaystyle b\in B\setminus A}$ ${\displaystyle (A\setminus \{a\})\cup \{b\}}$ ${\displaystyle (B\setminus \{b\})\cup \{a\}}$
• Свойство множественной симметричной замены базиса : если , то существует подмножество, такое что и являются базисами. Брилавский, Грин и Вудал показали (независимо), что это фактически эквивалентно свойству замены базиса. ${\displaystyle X\subseteq A\setminus B}$ ${\displaystyle Y\subseteq B\setminus A}$ ${\displaystyle (A\setminus X)\cup Y}$ ${\displaystyle (B\setminus Y)\cup X}$
• Биективное свойство обмена базисом : существует биекция из в , такая, что для каждого , есть базис. Бруальди ^[4] показал, что это эквивалентно свойству обмена базисом. ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle a\in A\setminus B}$ ${\displaystyle (A\setminus \{a\})\cup \{f(a)\}}$
• Свойство обмена базисом разбиения : для каждого разбиения на m частей существует разбиение на m частей, такое, что для каждого является базисом . ^[5] ${\displaystyle (A_{1},A_{2},\ldots ,A_{m})}$ ${\displaystyle A}$ ${\displaystyle (B_{1},B_{2},\ldots ,B_{m})}$ ${\displaystyle B}$ ${\displaystyle i\in [m]}$ ${\displaystyle (A\setminus A_{i})\cup B_{i}}$

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

В общем случае, в симметричном свойстве обмена базисом элемент не обязательно должен быть уникальным. Регулярные матроиды обладают свойством обмена уникальным , что означает, что для некоторых соответствующий b является уникальным. ^[6] ${\displaystyle b\in B\setminus A}$ ${\displaystyle a\in A\setminus B}$

Мощность

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

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

Гипотеза Нила Уайта

Предполагается, что все матроиды удовлетворяют следующему свойству: ^[2] Для каждого целого числа t ≥ 1 , если B и B' являются двумя t -кортежами баз с одним и тем же мультимножественным объединением, то существует последовательность симметричных обменов, которая преобразует B в B' .

Характеристика

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

(B1) Существует по крайней мере одна база -- непустая; ${\displaystyle {\mathcal {B}}}$

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

(B2) подразумевает, что, имея любые два основания A и B , мы можем преобразовать A в B последовательностью обменов одного элемента. В частности, это подразумевает, что все основания должны иметь одинаковую мощность.

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

Если — конечный матроид, мы можем определить ортогональный или двойственный матроид , назвав множество базисом в тогда и только тогда, когда его дополнение находится в . Можно проверить, что действительно является матроидом. Из определения немедленно следует, что двойственный к — это . ^{[9] : 32  [10]} ${\displaystyle (E,{\mathcal {B}})}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$ ${\displaystyle {\mathcal {B}}^{*}}$ ${\displaystyle {\mathcal {B}}}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$ ${\displaystyle (E,{\mathcal {B}}^{*})}$ ${\displaystyle (E,{\mathcal {B}})}$

Используя двойственность, можно доказать, что свойство (B2) можно заменить следующим:

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

Схемы

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

Можно определить матроид как пару , где — базовый набор, а — набор подмножеств , называемых «схемами», со следующими свойствами: ^[8] ${\displaystyle M}$ ${\displaystyle (E,{\mathcal {C}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle E}$

(C1) Пустое множество не является цепью;

(C2) Собственное подмножество цепи не является цепью;

(C3) Если C ₁ и C ₂ — различные контуры, а x — элемент их пересечения, то содержит контур. ${\displaystyle C_{1}\cup C_{2}\setminus \{x\}}$

Другое свойство схем заключается в том, что если множество является независимым, а множество является зависимым (т. е. добавление элемента делает его зависимым), то содержит уникальную схему , и она содержит . Эта схема называется фундаментальной схемой относительно . Это аналогично факту линейной алгебры, что если добавление вектора к независимому векторному множеству делает его зависимым, то существует уникальная линейная комбинация элементов , которая равна . ^[10] ${\displaystyle J}$ ${\displaystyle J\cup \{x\}}$ ${\displaystyle x}$ ${\displaystyle J\cup \{x\}}$ ${\displaystyle C(x,J)}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle J}$ ${\displaystyle x}$ ${\displaystyle J}$ ${\displaystyle J}$ ${\displaystyle x}$

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

• Матроидный многогранник — многогранник в Rn ⁽ где n — число элементов в матроиде), вершинами которого являются индикаторные векторы баз матроида.

Ссылки

1. Ардила, Федерико (2007). "Матроиды, лекция 3". youtube . Архивировано из оригинала 2020-02-14.
2. Bonin, Joseph E.; Savitsky, Thomas J. (2016-01-01). «Бесконечное семейство исключенных миноров для сильной упорядочиваемости по базе». Линейная алгебра и ее приложения . 488 : 396–429. arXiv : 1507.05521 . doi :10.1016/j.laa.2015.09.055. ISSN  0024-3795. S2CID  119161534.
   • Джозеф Э. Бонин; Томас Дж. Савицкий (апрель 2016 г.). «Исключенные миноры для (строго) базисно-упорядочиваемых матроидов» (PDF) .
3. "Лекция по матроидам 2: Базы". YouTube . 16 августа 2020 г.
4. Brualdi, Richard A. (1969-08-01). «Комментарии о базах в зависимых структурах». Бюллетень Австралийского математического общества . 1 (2): 161–167. doi : 10.1017/S000497270004140X . ISSN  1755-1633.
5. Грин, Кертис; Маньянти, Томас Л. (1975-11-01). «Некоторые абстрактные алгоритмы поворота». Журнал SIAM по прикладной математике . 29 (3): 530–539. doi :10.1137/0129045. hdl : 1721.1/5113 . ISSN  0036-1399.
6. МакГиннесс, Шон (2014-07-01). «Свойство обмена базами для регулярных матроидов». Журнал комбинаторной теории, Серия B. 107 : 42–77. doi : 10.1016 /j.jctb.2014.02.004 . ISSN  0095-8956.
7. Уэлш, DJA (1976), Теория матроидов , LMS Monographs, т. 8, Academic Press, ISBN 978-0-12-744050-7, ЗБЛ  0343.05002. Раздел 1.2, «Системы аксиом для матроида», стр. 7–9.
8. Федерико, Ардила (2012). «Матроиды: Лекция 6». Ютуб .
9. Уайт, Нил, ред. (1986), Теория матроидов , Энциклопедия математики и ее приложений, т. 26, Кембридж: Cambridge University Press, ISBN 978-0-521-30937-0, ЗБЛ  0579.00001
10. Ардила, Федерико (2012). «Матроиды, лекция 7». Ютуб .