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

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

Примеры

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

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

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

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

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

Свойства

Обмен

Все матроиды удовлетворяют следующим свойствам для любых двух различных базисов. $A$ и $B$:

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

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

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

Кардинальность

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

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

Уайта

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

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

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

(B1) Существует хотя бы одно основание -- ${\mathcal {B}}$ непусто;

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

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

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

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

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

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

Схемы

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

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

(C1) Пустое множество не является контуром;

(C2) Правильное подмножество схемы не является схемой;

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

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

См. также

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