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

'''Двухуровневое графическое представление''' двудольного графа 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 v} c_{uv} = cr(G, <_1, <_2) \;</math>.

'''Теорема 4 ([9]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM <math>(G = (V_1, V_2, 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 \} \;</math> верно <math>c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали:

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

Этот простой алгоритм поиска по дереву можно улучшить. Во-первых, отметим, что нет необходимости ветвления в <math>\{ x, y \} \subset V_2 \;</math>, если <math>c_{xy} = c_{yx} \;</math>. Это позволяет внести две модификации в Алгоритм 1:

• На строке 5 следует исключить равенство <math>c_{xy} = c_{yx} \;</math>.

• Как эффективно вычислить все количества пересечений <math>c_{xy} \;</math> на этапе предварительной обработки?

'''Теорема 7. Задачу односторонней минимизации пересечений можно решить за время <math>O^*(1,4656^k) \;</math>.'''

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

1. Изменение цели оптимизации: минимизация количества дуг, участвующих в пересечениях – одноуровневая планаризация. Как было отмечено в [7, 10], из теоремы 2 практически непосредственно следует идея алгоритма решения этой задачи с временем выполнения <math>O^*(3^k) \;</math>, которое впоследствии было улучшено в [10] до <math>O^*(2^k) \;</math>.

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

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