Неглубокий минор или минор ограниченной глубины — это ограниченный вид минора графа, в котором стянутые[1] подграфы имеют малый диаметр. Неглубокие миноры ввели Плоткин, Рао и Смит[2], но они приписывают определение термина Чарльзу Лейзерсону и Сивану Толедо[3].
Определение
Один из способов определения минора неориентированного графа 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].
Примечания
Литература
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
