Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

Определение [ править ]

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

Матроид является регулярным , когда для каждого поля , может быть представлена в виде системы векторов более . [1] [2]

Свойства [ править ]

Если матроид является правильным, то также и его двойственный матроид , [1], и каждый из его миноров - тоже . [3] Всякая прямая сумма регулярных матроидов остается регулярной. [4]

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

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

Характеристики [ править ]

Равномерный матроид (четыре точки линия) не является регулярным: он не может быть реализован в течение двух элементов конечного поля GF (2) , так что это не является двоичным матроидом , хотя оно может быть реализовано в течение всех других областей. Матроид плоскости Фано (матроид третьего ранга, в котором зависимы семь троек точек) и двойственный к нему также не являются регулярными: они могут быть реализованы над GF (2) и над всеми полями характеристики два, но не по каким-либо другим полям, кроме этих. Как показал Тутте (1958) , эти три примера являются фундаментальными для теории регулярных матроидов: каждый нерегулярный матроид имеет по крайней мере один из этих трех в качестве второстепенного. . Таким образом, обычные матроиды - это именно те матроиды, у которых нет одного из трех запрещенных миноров , плоскости Фано или ее двойника. [8]

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

Регулярные матроиды - это матроиды, которые могут быть определены из полностью унимодулярной матрицы , матрицы, в которой каждая квадратная подматрица имеет определитель 0, 1 или -1. Векторы, реализующие матроид, можно принять за строки матрицы. По этой причине обычные матроиды иногда также называют унимодулярными матроидами . [10] Эквивалентность регулярных матроидов и унимодулярных матриц и их характеризация запрещенными минорами - глубокие результаты У. Т. Тутте , первоначально доказанные им с использованием гомотопической теоремы Тутте . [8] Джерардс (1989) позже опубликовал альтернативное и более простое доказательство характеризации унимодулярных матриц запрещенными минорами. [11]

Алгоритмы [ править ]

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

Ссылки [ править ]

  1. ^ a b Fujishige, Satoru (2005), Субмодульные функции и оптимизация , Анналы дискретной математики, Elsevier, стр. 24, ISBN 9780444520869.
  2. ^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, 3 , Oxford University Press, стр. 209, ISBN 9780199202508 CS1 maint: обескураженный параметр ( ссылка ).
  3. ^ Оксли (2006) , стр. 112.
  4. ^ Оксли (2006) , стр. 131.
  5. ^ Tutte, WT (1965), "Лекция по матроидам" , Журнал исследований Национального бюро стандартов , 6 : 1-47, DOI : 10,6028 / jres.069b.001 , MR 0179781 .
  6. ^ Seymour, PD (1980), "Разложение регулярных матроидов", Журнал комбинаторной теории , серии B, 28 (3): 305-359, DOI : 10,1016 / 0095-8956 (80) 90075-1 , ЛВП : 10338. dmlcz / 101946 , Руководство пользователя 0579077  CS1 maint: обескураженный параметр ( ссылка ).
  7. ^ Maurer, Стивен Б. (1976), "Матричные обобщения некоторых теорем о деревьях, циклов и коциклов в графах", SIAM журнал по прикладной математике , 30 (1): 143-148, DOI : 10,1137 / 0130017 , MR 0392635 .
  8. ^ Б Tutte, WT (1958), "Гомотопией теорема для матроидов I, II.", Труды Американского математического общества , 88 (1): 144-174, DOI : 10,2307 / 1993244 , JSTOR 1993244 , MR 0101526   CS1 maint: обескураженный параметр ( ссылка ).
  9. ^ Seymour, PD (1979), "матроида представление над GF (3)", Журнал комбинаторной теории , серии B, 26 (2): 159-173, DOI : 10,1016 / 0095-8956 (79) 90055-8 , MR 0532586  CS1 maint: обескураженный параметр ( ссылка ).
  10. ^ Оксли (2006) , стр. 20.
  11. ^ Gerards, АМГ (1989), "Короткое доказательство характеристики TUTTE о совершенно унимодулярными матриц", Линейная алгебра и ее применения , 114/115: 207-212, DOI : 10,1016 / 0024-3795 (89) 90461-8.
  12. ^ Truemper, К. (1982), "Об эффективности представимости испытаний для матроидов", Европейский журнал комбинаторике , 3 (3): 275-291, DOI : 10.1016 / s0195-6698 (82) 80039-5 , MR 0679212 .