Матроид минор

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

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

СОДЕРЖАНИЕ

  • 1 Определения
  • 2 Запрещенные характеристики матроидов
  • 3 Пропускная способность
  • 4 Ну-квазиупорядочение
  • 5 разложения матроидов
  • 6 Алгоритмы и сложность
  • 7 Примечания
  • 8 ссылки

Определения

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

Если Т является независимым подмножество Е, сужение М на Т, написанный М / Т, является матроид на основном множестве Е - Т, чьи независимые множества являются множества, объединение с Т является независимым в М. Это определение может быть расширено до произвольного T, выбирая основу для Т и определения набора, чтобы быть независимым в свертке, если его объединение с этой основой остается независимым в M. Ранговая функция сжатия равна р ( А ) знак равно р ( А Т ) - р ( Т ) . {\ displaystyle r '(A) = r (A \ cup T) -r (T).}

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

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

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

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

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

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

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

Пропускная способность

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

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

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

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

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

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

Разложения матроидов

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

Алгоритмы и сложность

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

Заметки

Рекомендации

Последняя правка сделана 2024-01-01 11:52:18
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте