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

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

Примеры

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

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

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

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

• В графической матроид , где независимые наборы являются лесами, основания называются охватывающими лесами графика.
• В поперечном матроде , где независимые наборы представляют собой конечные точки соответствия на данном двухпартийном графике , основания называются попереками .
• В линейной матроид , где независимые наборы представляют собой линейно-независимые наборы векторов в данном векторном пространстве, основания просто называются основаниями векторного пространства. Следовательно, концепция основы Matroid обобщает концепцию основы из линейной алгебры .
• В униформе Matroid , где все независимые наборы представляют собой наборы с кардинальностью в большинстве K (для некоторого целого k ), все основания - это наборы с кардинальностью ровно k .
• В разделе Matroid , где элементы разделены на категории, а независимые наборы представляют собой наборы, содержащие в большинстве K _C из каждой категории C, все основания - это наборы, которые содержат ровно k _{-элементы} из категории C. элементов
• В бесплатном матроид , где все подмножества наземных настройки являются независимыми, уникальная основа- E.

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

Обмен

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

• Свойство базисного обмена : если $a\in A\setminus B$, тогда существует элемент $b\in B\setminus A$ так что $(A\setminus \{a\})\cup \{b\}$ это основа.
• Свойство симметричного базисного обмена : если $a\in A\setminus B$, тогда существует элемент $b\in B\setminus A$ так что оба $(A\setminus \{a\})\cup \{b\}$ и $(B\setminus \{b\})\cup \{a\}$ базы. Бруалди показал, что на самом деле это эквивалентно свойству базисного обмена.
• Несколько симметричных свойств базисного обмена : если $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$ в М -части, существует раздел $(B_{1},B_{2},\ldots ,B_{m})$ из $B$ в М -части, так что для каждого $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 -Tuples of Bases с одним и тем же мульти -сетом, то существует последовательность симметричных обменов, которые преобразуют B в B' .

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

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

(B1) Есть хотя бы одна база - ${\mathcal {B}}$ это непусты;

(B2) if $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*) if $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$.

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

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