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

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

Примеры

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

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

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

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

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

Обмен

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

• Свойство базиса-обмена : если , то существует такой элемент , который является базисом.${\ Displaystyle а \ в А \ setminus B}$${\ Displaystyle б \ в В \ setminus А}$${\ Displaystyle (А \ setminus \ {а \}) \ чашка \ {Ь \}}$
• Свойство симметричного базисного обмена : если , то существует такой элемент , что оба и являются базисами. Бруальди ^[4] показал, что оно на самом деле эквивалентно свойству замены базиса.${\ Displaystyle а \ в А \ setminus B}$${\ Displaystyle б \ в В \ setminus А}$${\ Displaystyle (А \ setminus \ {а \}) \ чашка \ {Ь \}}$${\ Displaystyle (В \ setminus \ {Ь \}) \ чашка \ {а \}}$
• Множественное симметричное свойство обмена базисом : если , то существует подмножество такое, что оба и являются базами. Брылявский, Грин и Вудалл показали (независимо), что оно на самом деле эквивалентно свойству базисного обмена.${\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 -наборами основ с одним и тем же мультимножественным объединением, то существует последовательность симметричных обменов, которая превращает В в В' .

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

Базисы матроида полностью характеризуют матроид: множество независимо тогда и только тогда, когда оно является подмножеством базиса. Более того, можно определить матроид как пару , где - набор оснований и - набор подмножеств , называемых «базами», со следующими свойствами: ^{[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\}}$

Другое свойство схем состоит в том, что если множество независимо, а множество зависимо (т. е. добавление элемента делает его зависимым), то содержит единственную схему , и она содержит . Эта схема называется основной схемой wrt . Это аналогично факту линейной алгебры, что если добавление вектора к независимому набору векторов делает его зависимым, то существует уникальная линейная комбинация элементов , равная . ^[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 — количество элементов в матроиде), вершины которого являются векторами-индикаторами оснований матроида.

использованная литература