4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Перейти к навигации
Перейти к поиску
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 18:33, 30 марта 2016
, 30 марта 2016→Нотация
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
Двухуровневое графическое представление двудольного графа 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>, соответственно. Пересечение представляет собой пару ребер e = ( | Двухуровневое графическое представление двудольного графа 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> количество пересечений в описываемом двухуровневом представлении. В контексте представления графов, разумеется, очень желательно получить минимальное число пересечений. В самой простой (и, вероятно, самой важной) форме это выглядит следующим образом: порядок вершин на одном уровне фиксируется, задача заключается в минимизации количества пересечений путем выбора порядка на втором уровне. Более формально: | ||
Задача 1 (k-OSCM) | '''Задача 1 (k-OSCM)''' | ||
Дано: простой двудольный граф с n вершинами G = ( | Дано: простой двудольный граф с n вершинами <math>G = (V_1, V_2, E) \;</math> и отношение линейного порядка <math><_1 \;</math> на <math>V_1 \;</math>; неотрицательное целое число k (параметр). | ||
Требуется: если это возможно, найти такой линейный порядок < | Требуется: если это возможно, найти такой линейный порядок <math><_2 \;</math> на <math>V_2 \;</math>, что <math>cr(G, <_1, <_2) \le k \;</math>. Если такого линейного порядка не существует, алгоритм должен выдать соответствующее сообщение. | ||
Возьмем для примера G = ( | Возьмем для примера <math>G = (V_1, V_2, E) \;</math> и <math><_1 \;</math> из задачи односторонней минимизации пересечений (OSCM) и две вершины <math>u, v \in V_2 \;</math>. | ||