Обычный матроид

редактировать

В математике обычный матроид - это матроид, который может быть представлен по всем полям .

Содержание

1 Определение
2 Свойства
3 Характеристики
4 Алгоритмы
5 Ссылки

Определение

A матроид определяется как семейство подмножеств конечное множество, удовлетворяющее некоторым аксиомам. Наборы в семействе называются «независимыми наборами». Один из способов построения матроида - выбрать конечный набор векторов в векторном пространстве и определить подмножество векторов как независимых в матроиде, когда оно линейно независимое в векторном пространстве. Каждое семейство наборов, построенных таким образом, является матроидом, но не каждый матроид может быть построен таким образом, а векторные пространства над различными полями приводят к различным наборам матроидов, которые могут быть построены из них.

Матроид $M {\ displaystyle M}$ $M$ является обычным, когда для каждого поля $F {\ displaystyle F}$ $F$ , $M {\ displaystyle M}$ $M$ может быть представлена системой векторов над $F {\ displaystyle F}$ $F$ .

Свойства

Если матроид является правильным, то его двойным матроидом, как и все его несовершеннолетние. Каждая прямая сумма регулярных матроидов остается регулярной.

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

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

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

однородный матроид $U 4 2 {\ displaystyle U {} _ {4} ^ {2}}$ $U {} _ {4} ^ {2}$ (четырехточечная линия) не является регулярным: его нельзя реализовать над двухэлементным конечным полем GF (2), поэтому это не бинарный матроид ., хотя может быть реализовано и над всеми другими полями. Матроид плоскости Фано (матроид третьего ранга, в котором семь троек точек зависимы) и его двойник также не регулярны: они могут быть реализованы над GF (2) и над всеми поля характеристики два, но не над любыми другими полями, кроме этих. Как показал Тутт (1958), эти три примера являются фундаментальными для теории регулярных матроидов: каждый нерегулярный матроид имеет по крайней мере один из этих трех как минор. Таким образом, обычные матроиды - это именно те матроиды, у которых нет одного из трех запрещенных миноров $U 4 2 {\ displaystyle U {} _ {4} ^ {2}}$ $U {} _ {4} ^ {2}$ , плоскость Фано, или его двойственный.

Если матроид является регулярным, он, очевидно, должен быть реализован над двумя полями GF (2) и GF (3). Верно и обратное: любой матроид, реализуемый над обоими этими двумя полями, является регулярным. Результат следует из запрещенной минорной характеристики матроидов, реализуемых над этими полями, что является частью семейства результатов, кодифицированных гипотезой Роты.

. Обычные матроиды - это матроиды, которые могут быть определены из полностью унимодулярной матрицы, матрица, в которой каждая квадратная подматрица имеет определитель 0, 1 или -1. Векторы, реализующие матроид, можно принять за строки матрицы. По этой причине обычные матроиды иногда также называют унимодулярными матроидами . Эквивалентность регулярных матроидов и унимодулярных матриц и их характеризация запрещенными минорами - глубокие результаты работы W. T. Tutte, первоначально доказанный им с помощью гомотопической теоремы Tutte. Gerards (1989) позже опубликовал альтернативное и более простое доказательство характеризации унимодулярных матриц запрещенными минорами.

Алгоритмы

Существует алгоритм полиномиального времени для проверки того, является ли матроид регулярным, при условии доступа к матроиду через оракул независимости.

Ссылки