Русская Википедия:Минор ограниченной глубины
Неглубокий минор или минор ограниченной глубины — это ограниченный вид минора графа, в котором стянутые[1] подграфы имеют малый диаметр. Неглубокие миноры ввели Плоткин, Рао и СмитШаблон:Sfn, но они приписывают определение термина Чарльзу Лейзерсону и Сивану ТоледоШаблон:Sfn.
Определение
Один из способов определения минора неориентированного графа G заключается в указании подграфа H графа G и набора непересекающихся множеств Si вершин графа G, каждое из которых образует связный порождённый подграф Hi графа H. Минор имеет вершину vi для каждого подмножества Si и ребро vivj, если существует ребро из Si в Sj, принадлежащее H.
В этой формулировке d-неглубокий минор (другое название — минор глубины d) — это минор, который может определён указанным выше образом с условием, что каждый из подграфов Hi имеет радиус, не превосходящий d, что означает, что подграф содержит вершину ci, расстояние от которой до всех остальных вершин подграфа Hi не превосходит d. Заметим, что расстояние здесь измеряется в числе дуг в графе Hi, а потому это расстояние может быть больше расстояния в графе GШаблон:Sfn.
Частные случаи
Миноры глубины ноль — это то же самое, что подграфы данного графа. При достаточно большом d (например, число вершин графа), миноры глубины d состоят из всех миноров графаШаблон:Sfn.
Классификация семейств графов
Нешрил и Оссона де МендезШаблон:Sfn использовали неглубокие миноры для разделения семейств конечных графов на семейства двух типов. Они говорят, что граф семейство графов F кое-где плотно, если существует конечное значение d, для которого множество миноров глубины d графов из F содержит любой конечный граф. В противном случае говорят, что семейство графов нигде не плотноШаблон:Sfn. Эта терминология оправдывается тем, что если F нигде не плотный класс графов, то (для любого ε > 0) графы с n вершинами из F имеют O(n1 + ε) вершин. Таким образом, нигде не плотные графы являются разреженными графамиШаблон:Sfn.
Более ограниченное семейство графов, описываемое подобным образом, это семейство графов с Шаблон:Не переведено 5. Это семейства графов, для которых существует функция f, такая, что отношение числа рёбер к числу вершин в любом миноре глубины d не превосходит f(d)Шаблон:Sfn. Если такая функция существует и ограничена многочленом, говорят, что семейство имеет полиномиальное расширение.
Теорема об отделении
Как показали Плоткин, Рао и СмитШаблон:Sfn, графы с исключёнными неглубокими минорами могут быть разбиты аналогично разбиению в теореме о сепараторе для планарных графов. В частности, если полный граф Kh не является минором глубины d графа G с n вершинами, то существует подмножество S вершин графа G размера O(dh2 log n + n/d), такое, что любая связная компонента графа G\S имеет максимум 2n/3 вершин. Результат является конструктивным — существуют алгоритмы с полиномиальным временем исполнения, которые находят либо такой сепаратор, либо минор Kh глубины d [2]. Как следствие, Плоткин и др. показали, что для любого семейства графов, замкнутого относительно миноров, теорема о сепараторе выполняется почти так же строго, как для планарных графов.
Плоткин и др. также применили эти результаты для разделения сеток в методе конечных элементов в больших размерностях. Для этого неглубокие миноры необходимы, поскольку (при отсутствии ограничений) семейство сеток в размерностях три и выше имеют в качестве миноров все графы. ТенгШаблон:Sfn распространил эти результаты на более широкий класс графов в пространствах высокой размерности.
Дворак и Норин показали, что для классов, замкнутых относительно операции создания подграфов, из строгой сублинейности сепараторов вытекает полиномиальность расширенияШаблон:Sfn.
Примечания
Литература
- ↑ Минор образуется стягиванием рёбер. Если некий подграф стягивается в вершину, будем говорить о стянутом подграфе.
- ↑ Алгоритм Плоткина выполняется за время O(mn/d), где m — число рёбер. Вульф-Нильсен Шаблон:Harv улучшил это время для неразреженных графов до O(m + n2 + ε/d).
