Параметризованные алгоритмы графического представления графов: различия между версиями

Граф G описывается множеством его вершин V и ребер E, т.е. G = (V, E), где <math>E \subseteq V \times V \;</math>. Обозначим за <math>N(v) \;</math> (открытую) [[окрестность]] вершины v, включающую все вершины, смежные с v; за <math>N[v] = N(v) \cup \{ v \} \;</math> – закрытую окрестность v; за <math>deg(v) = |N(v)| \;</math> – [[степень вершины]] v. Для множества вершин S, <math>N(S) = \bigcup_{v \in S} N(v) \;</math> и <math>N[S] = N(S) \cup S \;</math>. <math>G[S] \;</math> обозначает граф, порожденный множеством вершин, т.е. <math>G[S] = (S, E \cap (S \times S)) \;</math>. Граф G = (V, E) с множеством вершин V и множеством дуг <math>E \subseteq V \times V \;</math> является [[двудольный граф|двудольным]], если существует разбиение <math>V \;</math> на два множества <math>V_1 \;</math> и <math>V_2 \;</math>, такие, что <math>V = V_1 \cup V_2 \;</math>, <math>V_1 \cap V_2 = \empty \;</math> и <math>E \subseteq V_1 \times V_2 \;</math>. Для наглядности запишем это в следующем виде: <math>G = (V_1, V_2, E) \;</math>.

Двухуровневое графическое представление двудольного графа G = <math>(V_1, V_2, E) \;</math> может быть описано при помощи двух отношений линейного порядка: <math><_1 \;</math> на <math>V_1 \;</math> и <math><_2 \;</math> на <math>V_2 \;</math>. Это представление можно реализовать следующим образом: вершины из подмножества <math>V_1 \;</math> располагаются на линии <math>L_1 \;</math> (также называемой уровнем) в порядке, порождаемом отношением <math><_1 \;</math>, а вершины из <math>V_2 \;</math> располагаются на втором уровне <math>L_2 \;</math>, параллельном первому, в порядке, порождаемом отношением <math><_2 \;</math>; затем следует изобразить прямолинейный отрезок для каждого ребра <math>e = (u_1, u_2) \;</math> из E, соединяющего точки, представляющие <math>u_1 \;</math> и <math>u_2 \;</math>, соответственно. ''Пересечение'' представляет собой пару ребер <math>e = (u_1, u_2) \;</math> и <math>f = (v_1, v_2) \;</math>, имеющих общую точку в реализации двухуровневого графического представления <math>(G, <_1, <_2) \;</math>. Хорошо известно, что два ребра пересекаются в том и только том случае, если <math>u_1 <_1 v_1 \;</math> и <math>v_2 <_2 u_2</math>; иными словами, это понятие несет чисто комбинаторный смысл, не зависящий от конкретной реализации двухуровневого графического представления. Обозначим за <math>cr(G, <_1, <_2) \;</math> количество пересечений в описываемом двухуровневом представлении. В контексте представления графов, разумеется, очень желательно получить минимальное число пересечений. В самой простой (и, вероятно, самой важной) форме это выглядит следующим образом: порядок вершин на одном уровне фиксируется, задача заключается в минимизации количества пересечений путем выбора порядка на втором уровне. Более формально:

Вычислим ''матрицу количества пересечений'' (<math>c_uv \;</math>) для этого графа.

Для задач, для которых не предполагается существования полиномиальных алгоритмов, очень желательно найти точные алгоритмы с экспоненциальным временем исполнения.

'''Лемма 3'''. <math>\sum_{u, v \in V_2, u <_2 c_{uv} } C_{uv} = cr(G, <_1, <_2) \;</math>.

'''Теорема 4 ([9]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM (<math>G = (V_1, V2_, E), <_1 \;</math>), то <math>\sum_{u, v \in V_2, u \ne v} min \{ c_{uv}, v_{vu} \} \le k < 1,4664 \sum_{u, v \in V_2, u \ne v} min \{ c_{uv}, v_{vu} \} \;</math>'''.

Нагамочи предложил алгоритм аппроксимации с коэффициентом меньше 1,4664.

Далее, для любого <math>u \in V_2 \;</math> с <math>deg(u) > 0 \;</math> обозначим за <math>l_u \;</math> самого левого соседа u в <math>L_1 \;</math>, а за <math>r_u \;</math> – самого правого. Две вершины <math>u, v \in V_2 \;</math> называются неподходящими, если существует некоторое <math>x \in N(u) \;</math>, такое, что <math>l_v <_1 x <_1 r_v \;</math>, либо существует некоторое <math>x \in N(v) \;</math>, такое, что <math>l_u <_1 x <_1 r_u \;</math>. В противном случае они называются подходящими. Заметим, что для подходящих <math>{u, v} c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали:

Это означает, что все подходящие пары встречаются в своем естественном порядке.

Правило RR1: Для каждой пары вершин {u, v} из V2 с cuv = 0 необходимо включить u <2 v. В приведенном примере d будет полностью включено в результате применения правила RR1, поскольку столбец d в матрице пересечений заполнен нулями; следовательно, в последующих действиях d можно игнорировать. Алгоритм 1 представляет собой простой алгоритм поиска по дереву для задачи OSCM, последовательно применяющий правило RR1.

Лемма 6. OSCM можно вычислить за время 0*{2k).

yx.

• На строке 12 следует произвольным образом включить некоторую пару {x, y} С V2, которая еще не была включена, и рекурсивно повторить действие; только если включены все пары {x, y} С V2, следует вернуть значение ДА.

Дальнейшие улучшения возможны в результате более глубокого анализа локальных паттернов {x, y} 2 V2, таких, что cxycyx — 2. Таким образом было показано:

Возможный вариант исполнения улучшенного алгоритма поиска по дереву приведен на рис. 2, а его (оптимальный) результат – на рис. 3.

В различных публикациях рассматривались варианты этой задачи и родственные ей проблемы.

2. Можно повысить число степеней свободы, рассматривая два или более уровня присваиваний в одно и то же время. Параметризованные алгоритмы для минимизации пересечений и для планаризации были предложены в [3, 7, 10].

Помимо рассмотрения вопроса графического построения двудольных графов как задачи, интересной самой по себе (т.е., например, для качественного изображения диаграмм отношений), этот вопрос естественным образом возникает при применении так называемого подхода Судзиямы к построению иерархических графов [12]. Этот исключительно популярный подход решает задачу укладки иерархического графа в три этапа: (1) удаление циклов, (2) присваивание вершин уровням, (3) присваивание вершин уровням. Последний этап обычно реализуется посредством алгоритма с заметающей прямой, в процессе работы решающего несколько экземпляров задачи односторонней минимизации пересечений. Третий вариант задачи, упомянутый выше, находит множество важных вариантов применения в вычислительной биологии.  

else if 9fx; у} С V2 : не имеет места ни x <2 y, y <2 x then if OSCM-ST-simple(G,fc- 1;<1;<2 [ f(x, y)g) then

return OSCM-ST-simple(G ;k - 1; <b <2 [ f(y;x)g) end if else

return ДА 15: end if

Как и для всех алгоритмов с экспоненциальным временем исполнения, оказывается непросто улучшить это время или доказать определенную нижнюю границу времени исполнения при наличии разумных теоретико-сложностных предположений. Заметим, что негласные предположения, лежащие в основе подхода параметризованных алгоритмов, в данном сценарии полностью удовлетворяются: к примеру, графическое представление с большим количеством пересечений будет неприемлемым (если такая ситуация встретится на практике, придется прибегнуть к другому способу представления информации); таким образом, можно обоснованно предполагать, что параметр действительно окажется малым.

Это верно также для других NP-полных подзадач, относящихся к подходу Судзиямы. Однако на наличие простых решений рассчитывать не стоит. Например, для задачи построения множества ориентированных обратных дуг [ ], эквивалентной первой фазе, неизвестно о существовании подходящего параметризованного алгоритма [2].

 

Садермен [10] провел эксперименты практически со всеми вариантами данной задачи; в [ ] некоторые из экспериментальных результатов представлены в более наглядной форме.

 

Несколько JAVA-апплетов для решения задач, упомянутых в данной статье, приведены Садерменом на http://cgm.cs.mcgill. ca/~msuder/.