4510
правок
Двумерность: различия между версиями
Перейти к навигации
Перейти к поиску
→Двумерные параметры
Irina (обсуждение | вклад) (Новая страница: «== Постановка задачи == Теория двумерности включает обобщенные техники разработки эффект…») |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
== Двумерные параметры == | == Двумерные параметры == | ||
Неявно понятие «двумерный» подразумевалось в различных работах [2, 5, 10, 11], однако первое явное упоминание было сделано в работе [3]. | Неявно понятие «двумерный» подразумевалось в различных работах [2, 5, 10, 11], однако первое явное упоминание было сделано в работе [3]. | ||
Во-первых, подход с использованием параметров – это альтернативный взгляд на задачи оптимизации. Параметр P представляет собой функцию, отображающую графы на неотрицательные целые числа. Задача разрешимости, связанная с P, для заданного графа G и неотрицательного целого числа k спрашивает, выполняется ли соотношение P(G) _ k. Многие задачи оптимизации могут быть сформулированы в виде подобных задач разрешимости для графового параметра P. | |||
Параметр является g(r)-двумерным (или просто двумерным)если он равен не менее чем g(r) в графе-решетке размером r x r и если он не повышается при взятии миноров g(r)(-минорно-двумерный) либо выполнении сжатий (g(r)-сжато-двумерный). Точное определение «графа-решетки» зависит от класса допустимых графов и от того, рассматривается ли минорная двумерность или двумерность сжатия. Для случая минорной двумерности и для любого класса графов, не содержащего H-миноров, «графом-решеткой» является решетка r x r, т.е. планарный граф с r2 вершин, расположенных в виде квадратной решетки, ребра которой связывают горизонтально и вертикально смежные вершины. В случае двумерности сжатия «граф-решетка» определяется следующим образом: | |||
1. Для планарных графов и графов, не содержащих миноров с однократным пересечением, «граф-решетка» представляет собой решетку r x r, частично триангулированную дополнительными ребрами, сохраняющими планарность. | |||
2. Для графов с ограниченным родом «граф-решетка» представляет собой такую частично триангулированную решетку r x r с дополнительными ребрами («ручками») числом не более genus(G). | |||
3. Для графов, не содержащих апексных миноров, «граф-решетка» представляет собой решетку r x r с дополнительными ребрами, такую, что каждая вершина инцидентна O(1) ребер, ведущих к неграничным вершинам решетки. (Здесь O(1) зависит от исключенного апексного графа). | |||
Таким образом, двумерность сжатия не определена для графов, не содержащих H-миноров (или графов общего вида). | |||
Примерами двумерных параметров могут служить количество вершин, диаметр и размеры различных структур – таких как разрывающее множество вершин, вершинное покрытие, минимальное паросочетание с максимальным весом, покрытие гранями, серия параметров для удаления вершин, доминирующее множество, доминирующее множество ребер, R-доминирующее множество, связное доминирующее множество, связное доминирующее множество ребер, связное R-доминирующее множество, невзвешенная метрическая задача коммивояжера (обход графа с посещением всех вершин) и хордальное дополнение (заполнение). Например, разрывающее множество вершин является £?(r2)-минорно-двумерным (и, следовательно, сжато-двумерным), поскольку: (1) удаление или сжатие ребра сохраняет существующие разрывающие множества вершин; (2) любая вершина разрывающего множества вершин разрушает не более четырех квадратов решетки r x r, а поскольку в ней имеется (r — 1)2 квадратов, любое разрывающее множество вершин должно содержать Q(r2) вершин. В [1, 3] можно ознакомиться с рассуждениями по поводу минорной двумерности и двумерности сжатия для других параметров. | |||
== Основные результаты == | |||