Минор ограниченной глубины

Перейти к навигацииПерейти к поиску

Неглубокий минор или минор ограниченной глубины — это ограниченный вид минора графа, в котором стянутые[1] подграфы имеют малый диаметр. Неглубокие миноры ввели Плоткин, Рао и Смит[2], но они приписывают определение термина Чарльзу Лейзерсону и Сивану Толедо[3].

Определение

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

Один из способов определения минора неориентированного графа G заключается в указании подграфа H графа G и набора непересекающихся множеств Si вершин графа G, каждое из которых образует связный порождённый подграф Hi графа H. Минор имеет вершину vi для каждого подмножества Si и ребро vivj, если существует ребро из Si в Sj, принадлежащее H.

В этой формулировке d-неглубокий минор (другое название — минор глубины d) — это минор, который может определён указанным выше образом с условием, что каждый из подграфов Hi имеет радиус, не превосходящий d, что означает, что подграф содержит вершину ci, расстояние от которой до всех остальных вершин подграфа Hi не превосходит d. Заметим, что расстояние здесь измеряется в числе дуг в графе Hi, а потому это расстояние может быть больше расстояния в графе G[3].

Частные случаи

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

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

Нешрил и Оссона де Мендез[4] использовали неглубокие миноры для разделения семейств конечных графов на семейства двух типов. Они говорят, что граф семейство графов F кое-где плотно, если существует конечное значение d, для которого множество миноров глубины d графов из F содержит любой конечный граф. В противном случае говорят, что семейство графов нигде не плотно[5]. Эта терминология оправдывается тем, что если F нигде не плотный класс графов, то (для любого ε > 0) графы с n вершинами из F имеют O(n1 + ε) вершин. Таким образом, нигде не плотные графы являются разреженными графами[6].

Более ограниченное семейство графов, описываемое подобным образом, это семейство графов с ограниченным расширением[англ.]. Это семейства графов, для которых существует функция f, такая, что отношение числа рёбер к числу вершин в любом миноре глубины d не превосходит f(d)[7]. Если такая функция существует и ограничена многочленом, говорят, что семейство имеет полиномиальное расширение.

Теорема об отделении

Как показали Плоткин, Рао и Смит[2], графы с исключёнными неглубокими минорами могут быть разбиты аналогично разбиению в теореме о сепараторе для планарных графов. В частности, если полный граф Kh не является минором глубины d графа G с n вершинами, то существует подмножество S вершин графа G размера O(dh2 log n + n/d), такое, что любая связная компонента графа G\S имеет максимум 2n/3 вершин. Результат является конструктивным — существуют алгоритмы с полиномиальным временем исполнения, которые находят либо такой сепаратор, либо минор Kh глубины d [8]. Как следствие, Плоткин и др. показали, что для любого семейства графов, замкнутого относительно миноров, теорема о сепараторе выполняется почти так же строго, как для планарных графов.

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

Дворак и Норин показали, что для классов, замкнутых относительно операции создания подграфов, из строгой сублинейности сепараторов вытекает полиномиальность расширения[10].

Примечания

  1. ↑ Минор образуется стягиванием рёбер. Если некий подграф стягивается в вершину, будем говорить о стянутом подграфе.
  2. ↑ 1 2 Plotkin, Rao, Smith, 1994.
  3. ↑ 1 2 3 Nešetřil, Ossona de Mendez, 2012, с. 62–65,Section 4.2 "Shallow Minors".
  4. ↑ Nešetřil, Ossona de Mendez, 2012.
  5. ↑ Nešetřil, Ossona de Mendez, 2012, с. 100–102, section 5.3 "Classification of Classes by Clique Minors".
  6. ↑ Nešetřil, Ossona de Mendez, 2012, с. 100, Theorem 5.3.
  7. ↑ Nešetřil, Ossona de Mendez, 2012, с. 104–107, Section 5.5 "Classes with Bounded Expansion".
  8. ↑ Алгоритм Плоткина выполняется за время O(mn/d), где m — число рёбер. Вульф-Нильсен (Wulff-Nilsen 2011) улучшил это время для неразреженных графов до O(m + n2 + ε/d).
  9. ↑ Teng, 1998.
  10. ↑ Dvořák, Norin, 2015, с. 3.

Литература

  • Zdeněk Dvořák, Sergey Norin. Strongly sublinear separators and polynomial expansion. — 2015. — arXiv:1504.04821.
  • Serge Plotkin, Satish Rao, Warren D. Smith. Proc. 5th ACM-SIAM Symp. on Discrete Algorithms (SODA). — 1994. — С. 462–470..
  • Shang-Hua Teng. Combinatorial aspects of geometric graphs // Comput. Geom.. — 1998. — Т. 9, вып. 4. — С. 277–287. — doi:10.1016/S0925-7721(96)00008-9..
  • Christian Wulff-Nilsen. Proc. 52nd IEEE Symp. Foundations of Computer Science (FOCS). — 2011. — С. 37–46. — doi:10.1109/FOCS.2011.15.
  • Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Springer, 2012. — Т. 28. — (Algorithms and Combinatorics). — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.