4430
правок
Двумерность: различия между версиями
Материал из WEGA
→Двумерные параметры
Irina (обсуждение | вклад) м (→Классы графов) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Во-первых, подход с использованием параметров – это альтернативный взгляд на задачи оптимизации. Параметр P представляет собой функцию, отображающую графы на неотрицательные целые числа. Задача разрешимости, связанная с P, для заданного графа G и неотрицательного целого числа k спрашивает, выполняется ли соотношение P(G) | Во-первых, подход с использованием параметров – это альтернативный взгляд на задачи оптимизации. [[Параметр]] P представляет собой функцию, отображающую графы на неотрицательные целые числа. [[Задача разрешимости]], связанная с P, для заданного графа G и неотрицательного целого числа k спрашивает, выполняется ли соотношение <math>P(G) \le k \;</math>. Многие задачи оптимизации могут быть сформулированы в виде подобных задач разрешимости для графового параметра P. | ||
Параметр является g(r)-двумерным (или просто двумерным), если он равен не менее чем g(r) в графе-решетке размером r | Параметр является ''g(r)-двумерным'' (или просто ''двумерным''), если он равен не менее чем g(r) в графе-решетке размером <math>r \times r \;</math> и если он не повышается при взятии миноров (''g(r)-минорно-двумерный'') либо выполнении сжатий (''g(r)-сжато-двумерный''). Точное определение «графа-решетки» зависит от класса допустимых графов и от того, рассматривается ли минорная двумерность или двумерность со сжатием. Для случая минорной двумерности и для любого класса графов, свободного от H-миноров, «графом-решеткой» является решетка <math>r \times r \;</math>, т.е. планарный граф с <math>r^2 \;</math> вершин, расположенных в виде квадратной решетки, ребра которой связывают горизонтально и вертикально смежные вершины. В случае двумерности со сжатием «граф-решетка» определяется следующим образом: | ||
1. Для планарных графов и графов, свободных от миноров с однократным пересечением, «граф-решетка» представляет собой решетку r | 1. Для планарных графов и графов, свободных от миноров с однократным пересечением, «граф-решетка» представляет собой решетку <math>r \times r \;</math>, частично [[триангуляция графа|триангулированную]] дополнительными ребрами, сохраняющими планарность. | ||
2. Для графов с ограниченным родом «граф-решетка» представляет собой такую частично триангулированную решетку r | 2. Для графов с ограниченным родом «граф-решетка» представляет собой такую частично триангулированную решетку <math>r \times r \;</math> с дополнительными ребрами («ручками») числом не более genus(G). | ||
3. Для графов, свободных от апексных миноров, «граф-решетка» представляет собой решетку r | 3. Для графов, свободных от апексных миноров, «граф-решетка» представляет собой решетку <math>r \times r \;</math> с дополнительными ребрами, такую, что каждая вершина инцидентна O(1) ребер, ведущих к неграничным вершинам решетки. (Здесь O(1) зависит от исключенного апексного графа). | ||
Таким образом, двумерность со сжатием не определена для графов, свободных от H-миноров (или графов общего вида). | Таким образом, двумерность со сжатием не определена для графов, свободных от H-миноров (или графов общего вида). | ||
Примерами двумерных параметров могут служить количество вершин, диаметр и размеры различных структур – таких как [[разрывающее множество вершин]], [[вершинное покрытие]], минимальное [[паросочетание]] с максимальным весом, [[покрытие гранями]], серия параметров для удаления вершин, [[доминирующее множество]], доминирующее множество ребер, R-доминирующее множество, [[связное доминирующее множество]], связное доминирующее множество ребер, связное R-доминирующее множество, невзвешенная [[метрическая задача коммивояжера]] (обход графа с посещением всех вершин) и [[хордальное дополнение]] (заполнение). Например, разрывающее множество вершин является <math>\Omega (r^2) \;</math>-минорно-двумерным (и, следовательно, сжато-двумерным), поскольку: (1) удаление или сжатие ребра сохраняет существующие разрывающие множества вершин; (2) любая вершина разрывающего множества вершин разрушает не более четырех квадратов решетки <math>r \times r \;</math>, а поскольку в ней имеется <math>(r — 1)^2 \;</math> квадратов, любое разрывающее множество вершин должно содержать <math>\Omega (r^2) \;</math> вершин. В [1, 3] можно ознакомиться с рассуждениями по поводу минорной двумерности и двумерности со сжатием для других параметров. | |||
== Основные результаты == | == Основные результаты == | ||
