Мелкий минор - Shallow minor

В теория графов, а мелкий минор или же минор ограниченной глубины ограниченная форма граф минор в котором подграфы, которые сокращаются для образования второстепенного, имеют небольшие диаметр. Мелкие несовершеннолетние были представлены Плоткин, Рао и Смит (1994), которые приписали свое изобретение Чарльз Э. Лейзерсон и Сиван Толедо.^[1]

Определение

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

Один из способов определения минора неориентированного графа грамм это путем указания подграфа ЧАС из грамм, и набор непересекающихся подмножеств S_я вершин грамм, каждый из которых образует связаны индуцированный подграф ЧАС_я из ЧАС. У минора есть вершина v_я для каждого подмножества S_я, и край v_яv_j всякий раз, когда существует ребро из S_я к S_j это принадлежит ЧАС.

В этой постановке d-shallow minor (также называется мелким минором глубины) d) - минор, который можно определить таким образом, что каждый из подграфов ЧАС_я имеет радиус в большинстве d, что означает, что он содержит центральную вершину c_я что на расстоянии d всех остальных вершин ЧАС_я. Обратите внимание, что это расстояние измеряется числом прыжков в ЧАС_я, и поэтому оно может быть больше, чем расстояние в грамм.^[1]

Особые случаи

Мелкие миноры нулевой глубины - это то же самое, что подграфы данного графа. При достаточно больших значениях d (включая все значения, по крайней мере, равные количеству вершин), d-положенные миноры данного графа совпадают со всеми его минорами.^[1]

Классификация семейств графов

Нешетржил и Оссона де Мендес (2012) используйте мелкие миноры, чтобы разбить семейства конечных графов на два типа. Говорят, что граф семья F является где-то плотно если существует конечное значение d для чего d-малые миноры графов в F состоят из каждого конечного графа. В противном случае говорят, что семейство графов нигде не плотный.^[2] Данная терминология оправдана тем, что если F нигде не плотный класс графов, то (для любого ε> 0) п-вершинные графы в F имеют О(п^{1 + ε}) края; таким образом, нигде не плотные графы разреженные графики.^[3]

Более ограниченным типом семейства графов, описываемым аналогично, являются семейства графов ограниченное расширение. Это семейства графов, для которых существует функция ж такое, что отношение ребер к вершинам в каждом d-shallow minor не более ж(d).^[4] Если эта функция существует и ограничена многочлен, семейство графов имеет полиномиальное расширение.

Разделительные теоремы

В качестве Плоткин, Рао и Смит (1994) показал, что графы с исключенными мелкими минорами могут быть разбиты аналогично теорема о плоском сепараторе за планарные графы. В частности, если полный граф K_час это не dмелкий минор п-вершинный граф грамм, то существует подмножество S из грамм, с размером О(dh² бревноп + п/d), так что каждая связная компонента грамм\S имеет не более 2п/ 3 вершины. Результат конструктивный: существует алгоритм с полиномиальным временем, который либо находит такой разделитель, либо d-мелкий K_час незначительный.^[5]Как следствие они показали, что каждое семейство минорно-замкнутых графов подчиняется теореме о разделителе, почти такой же сильной, как и теорема для плоских графов.

Плоткин и др. также применил этот результат к разбиению метод конечных элементов сетки в более высоких измерениях; для этого обобщения необходимы неглубокие миноры, поскольку (без ограничения глубины) семейство сеток в трех или более измерениях имеет все графы как миноры. Тэн (1998) расширяет эти результаты на более широкий класс многомерных графов.

В более общем смысле, семейство наследственных графов имеет теорему о разделителе, в которой размер разделителя является сублинейной степенью п тогда и только тогда, когда он имеет полиномиальное расширение.^[6]

Примечания

^ ^а ^б ^c Нешетржил и Оссона де Мендес (2012), Раздел 4.2 «Мелкие несовершеннолетние», стр. 62–65.
^ Нешетржил и Оссона де Мендес (2012), раздел 5.3 «Классификация классов по минорным кликам», стр. 100–102.
^ Нешетржил и Оссона де Мендес (2012), Теорема 5.3, с. 100.
^ Нешетржил и Оссона де Мендес (2012), Раздел 5.5 «Классы с ограниченным расширением», стр. 104–107.
^ Алгоритм Плоткина и соавт. требуется время О(мин/d), куда м количество ребер на входе. Вульф-Нильсен (2011) улучшил это для не разреженных графов, чтобы О(м + п^{2 + ε}/d).
^ Дворжак и Норин (2015).