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

В математической теории матроидов , A минор из матроидов М является еще матроидом Н , который получается из M последовательностью операций ограничения и сжатия. Миноры матроидов тесно связаны с минорами графов , а операции ограничения и сжатия, с помощью которых они формируются, соответствуют операциям удаления и сжатия ребер в графах. Теория миноров матроидов приводит к структурным разложениям матроидов и характеризации семейств матроидов запрещенными минорами, аналогично соответствующей теории в графах.

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

Если M - матроид на множестве E, а S - подмножество E , то ограничение M на S , записанное M  | S , является матроидом на множестве S , чьи независимых множества являются независимым множеством М , которые содержатся в S . Его схемы являются схемы M , которые содержатся в S и его ранговая функция является то , что M ограничивается подмножеств S .

Если Т является независимым подмножество Е , сужение М на Т , написанный М / Т , является матроид на основном множестве Е - Т , чьи независимые множества являются множества, объединение с Т является независимым в М . Это определение может быть расширено до произвольного T , выбирая основу для Т и определения набора , чтобы быть независимым в свертке , если его объединение с этой основой остается независимым в M . Ранговая функция сжатия равна

Матроид N является минором матроида M, если он может быть построен из M с помощью операций ограничения и сжатия.

В терминах геометрической решетки, образованной плоскостями матроида, взятие минора матроида соответствует взятию интервала решетки, части решетки, лежащей между заданной нижней границей и верхним ограниченным элементом. [1]

Запрещенные характеристики матроидов [ править ]

Многие важные семейства матроидов закрываются при операции взятия миноров: если матроид M принадлежит семейству, то каждый минор M также принадлежит семейству. В этом случае семейство может быть охарактеризовано набором «запрещенных матроидов», мино-минимальных матроидов, не принадлежащих к семейству. Матроид принадлежит к семейству тогда и только тогда, когда у него нет запрещенного матроида в качестве несовершеннолетнего. Часто, но не всегда, набор запрещенных матроидов конечен, что соответствует теореме Робертсона – Сеймура, которая утверждает, что множество запрещенных миноров семейства минорно-замкнутых графов всегда конечно.

Примером этого явления являются обычные матроиды , матроиды, представимые во всех полях. Эквивалентно матроид является регулярным, если он может быть представлен полностью унимодулярной матрицей (матрицей, все квадратные подматрицы которой имеют определители, равные 0, 1 или -1). Тутте (1958) доказал, что матроид является правильным тогда и только тогда, когда он не имеет одного из трех запрещенных миноров: равномерного матроида (четырехточечная прямая), плоскости Фано или двойственного матроида плоскости Фано. Для этого он использовал свою трудную теорему о гомотопии . С тех пор были найдены более простые доказательства.

В графических матроиды , матроиды чьи независимые множества являются лесные подграфы графа, пять запрещенных несовершеннолетних: три для обычных матроидов, и два двойников графических матроидов для графов K 5 и K 3,3 , что по теореме Вагнера являются запрещенными минорами для плоских графов .

В бинарных матроиды , матроиды представимых через два-элемента конечного поля , включают в себя как графические и регулярные матроиды. Тутте снова показал, что эти матроиды имеют запрещенную второстепенную характеристику: это матроиды, у которых нет четырехточечной линии как второстепенной. Рота предположил, что для любого конечного поля представимые над этим полем матроиды имеют конечное число запрещенных миноров. [2] Полное доказательство этой гипотезы было объявлено Гиленом, Джерардсом и Уиттлом; [3] по состоянию на 2015 год не появилось. Однако матроиды, которые могут быть представлены над действительными числами, имеют бесконечно много запрещенных миноров. [4]

Branchwidth [ править ]

Разбиения по ветвям матроидов можно определить аналогично их определению для графов. Разбиение по ветвям матроида - это иерархическая кластеризация элементов матроида, представленная в виде бинарного дерева без корней с элементами матроида на его листьях. Удаление любого ребра этого дерева разбивает матроиды на два непересекающихся подмножества; такое разделение называется электронным разделением. Если r обозначает ранговую функцию матроида, то ширина e-разделения определяется как r ( A ) + r ( B ) - r ( M ) + 1. Ширина разложения - это максимальная ширина любого из его электронных разделений, а ширина ветвления матроида - это минимальная ширина любого из его разложений по ветвям.

Ширина ветвления графа и ширина ветвления соответствующего графического матроида могут различаться: например, трехреберный граф путей и трехреберная звезда имеют разные значения ширины ветвления, 2 и 1 соответственно, но оба они индуцируют один и тот же графический матроид с шириной ветвления. 1. [5] Однако для графов, которые не являются деревьями, ширина ветвления графа равна ширине ветвления связанного с ним графического матроида. [6] Ширина ветвления матроида всегда равна ширине ветвления его двойника. [5]

Ширина ветвления является важным компонентом попыток распространить теорию миноров графов на матроиды: хотя ширина дерева также может быть обобщена на матроиды [7] и играет большую роль, чем ширина ветвления в теории миноров графов, ширина ветвления имеет более удобные свойства в настройка матроида. [8] Если минорно-замкнутое семейство матроидов, представимых над конечным полем, не включает графические матроиды всех планарных графов, то существует постоянная граница на ширину ветвления матроидов в семействе, обобщая аналогичные результаты для минорно-замкнутых семейства графов. [9]

Хорошо-квазиупорядоченный [ править ]

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

Робертсон и Сеймур предположили, что матроиды, представимые над любым конкретным конечным полем , хорошо квазиупорядочены. Пока это доказано только для матроидов с ограниченной шириной ветвления. [10]

Разбиения Matroid [ править ]

Теорема о структуре графов - важный инструмент в теории миноров графов, согласно которому графы в любом минорно-замкнутом семействе могут быть построены из более простых графов операциями клик-суммы . Некоторые аналогичные результаты известны и в теории матроидов. В частности, теорема Сеймура о разложении утверждает, что все обычные матроиды могут быть построены простым способом как клик-сумма графических матроидов, их двойников и одного специального матроида с 10 элементами. [11] Как следствие, линейные программы, определяемые полностью унимодулярными матрицами, могут быть решены комбинаторно путем объединения решений в набор минимального остовного дерева. задачи, соответствующие графической и копографической частям этой декомпозиции.

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

Одним из важных компонентов теории минора графов является наличие алгоритма для проверки того, является ли граф H второстепенным по отношению к другому графу G , при этом требуется время, полиномиальное от G для любого фиксированного выбора H (и более строго фиксированного -параметр послушный, если разрешено изменять размер H ). Объединив этот результат с теоремой Робертсона – Сеймура, можно распознать члены любого семейства минорно-замкнутых графов за полиномиальное время. Соответственно, в теории матроидов было бы желательно разработать эффективные алгоритмы для распознавания того, является ли данный фиксированный матроид второстепенным по отношению к входному матроиду. К сожалению, такой сильный результат невозможен: в модели оракула матроидов единственные миноры, которые могут быть распознаны за полиномиальное время, - это однородные матроиды с рангом или корангом. [12] Однако, если проблема ограничивается матроидами, которые могут быть представлены над некоторым фиксированным конечным полем (и представлены в виде матрицы над этим полем), то, как и в случае с графом, предполагается, что можно распознать матроиды, которые содержат любой фиксированный минор за полиномиальное время. [8]

Заметки [ править ]

  1. ↑ Валлийский (2010) .
  2. ^ Рота (1971) .
  3. ^ «Решение гипотезы Роты» (PDF) , Уведомления Американского математического общества : 736–743, 17 августа 2014 г.
  4. ^ Vámos (1978) .
  5. ^ a b Mazoit & Thomassé (2007) .
  6. ^ Mazoit & Thomasse (2007) ; Хикс и МакМюррей (2007) .
  7. ^ Hliněný & Whittle (2006) .
  8. ^ a b Гилен, Джерардс и Уиттл (2006) .
  9. ^ Гилен, Джерардс и Уиттл (2006) ; Гилен, Джерардс и Уиттл (2007) .
  10. ^ Гилен, Джерардс и Уиттл (2002) ; Гилен, Джерардс и Уиттл (2006) .
  11. ^ Сеймур (1980) .
  12. ^ Сеймур и Уолтон (1981) .

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

  • Geelen, JF ; Джерардс, AMH; Капур, А. (2000), "Исключенные несовершеннолетними для GF (4) -представимых матроиды" , Журнал комбинаторной теории , Series B, 79 (2): 247-299, DOI : 10,1006 / jctb.2000.1963 , МР  1769191.
  • Гилен, Джим ; Джерардс, Берт; Робертсон, Нил ; Уиттл, Джефф (2003), «Об исключенных минорах для матроидов с шириной ветвления k », Журнал комбинаторной теории , серия B, 88 (2): 261–265, DOI : 10.1016 / S0095-8956 (02) 00046 -1.
  • Гилен, Джим ; Джерардс, Берт; Виттл, Geoff (2002), "Отделение ширина и хорошо квази-упорядочение в матроидах и графиках" , Журнал комбинаторной теории , серии B, 84 (2): 270-290, DOI : 10,1006 / jctb.2001.2082.
  • Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2006), "К теории структуры матриц и матроидов" (PDF) , Proc. Международный конгресс математиков , III , стр. 827–842..
  • Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2007), «Исключение плоского графа из GF ( q ) -представимых матроидов» (PDF) , Журнал комбинаторной теории , серия B, 97 (6): 971–998, doi : 10.1016 / j.jctb. 2007.02.005 , архивировано из оригинала (PDF) 24.09.2010 CS1 maint: обескураженный параметр ( ссылка ).
  • Хикс, Илья В .; Мак - Мюррей, Нолан Б., младший (2007), "О branchwidth графов и их цикл матроиды", Журнал комбинаторной теории , серии B, 97 (5): 681-692, DOI : 10.1016 / j.jctb.2006.12. 007.
  • Hliněný, Петр (2003), "О свойствах матроидов, определяемых в логике MSO", Proc. 28-й Международный симпозиум по математическим основам информатики (MFCS '03) , конспект лекций по информатике, 2747 , Springer-Verlag, стр. 470–479, doi : 10.1007 / 978-3-540-45138-9_41
  • Глинены, Петр; Уиттл, Джефф (2006), "Matroid tree-width" (PDF) , European Journal of Combinatorics , 27 (7): 1117–1128, doi : 10.1016 / j.ejc.2006.06.005 , заархивировано из оригинала (PDF) на 6 марта 2012 г. , получено 17 августа 2012 г.. Дополнение и исправление: Hliněný, Petr; Уиттл, Джефф (2009), «Дополнение к ширине дерева матроидов», Европейский журнал комбинаторики , 30 (4): 1036–1044, DOI : 10.1016 / j.ejc.2008.09.028.
  • Мазуа, Фредерик; Томассе, Стефан (2007), «Разветвление графических матроидов», в Хилтоне, Энтони; Талбот, Джон (ред.), Surveys in Combinatorics 2007 (PDF) , Серия лекций Лондонского математического общества, 346 , Cambridge University Press, стр. 275.
  • Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Actes du Congrès International des Mathématiciens (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, MR  0505646.
  • Seymour, PD (1980), "Разложение регулярных матроидов", Журнал комбинаторной теории , Series B, 28 (3): 305-359, DOI : 10,1016 / 0095-8956 (80) 90075-1 , МР  0579077 CS1 maint: обескураженный параметр ( ссылка ).
  • Сеймур, PD ; Walton, PN (1981), "Обнаружение матроид несовершеннолетних", журнал Лондонского математического общества , вторая серия, 23 (2): 193-203, DOI : 10,1112 / jlms / s2-23.2.193 , MR  0609098.
  • Tutte, WT (1958), "Гомотопией теорема для матроидов I, II.", Труды Американского математического общества , 88 (1): 144-174, DOI : 10,2307 / 1993244 , JSTOR  1993244 , MR  0101526.
  • Вамос П. (1978), «Утраченная аксиома теории матроидов потеряна навсегда», Журнал Лондонского математического общества , вторая серия, 18 (3): 403–408, doi : 10.1112 / jlms / s2-18.3.403 , MR  0518224.
  • Уэлш, DJA (2010) [1976], «4.4 Миноры и их представление в решетке», Теория матроидов , Courier Dover Publications, стр. 65–67, ISBN 9780486474397.