4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Перейти к навигации
Перейти к поиску
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 18:37, 30 марта 2016
, 30 марта 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 16: | Строка 16: | ||
Возьмем для примера <math>G = (V_1, V_2, E) \;</math> и <math><_1 \;</math> из задачи односторонней минимизации пересечений (OSCM) и две вершины <math>u, v \in V_2 \;</math> | Возьмем для примера <math>G = (V_1, V_2, E) \;</math> и <math><_1 \;</math> из задачи односторонней минимизации пересечений (OSCM) и две вершины <math>u, v \in V_2 \;</math>, | ||
Вычислим матрицу количества пересечений ( | <math>c_{uv} =cr(G[N[ \{ u, v \} ]], <_1 \cap (N( \{ u, v \} ) \times N( \{ u, v \} )), \{ (u, v) \} ) \;.</math> | ||
Таким образом, при выборе упорядочения <math>u <_2 v \;</math> необходимо рассматривать замкнутые окрестности u и v. | |||
Рассмотрим следующий пример: | |||
Пример 1. На рис. 1 приведен пример конкретного графического представления двудольного графа. Является ли это представление оптимальным в смысле количества пересечений, предполагая, что порядок верхнего уровня фиксирован? В случаях, когда пересекаются более двух ребер, на рисунке указано количество пересечений. Все пересечения отмечены красными квадратами. | |||
[[Файл:PADG_pic1.png]] | |||
Рис. 1. Пример графа из задачи односторонней минимизации пересечений. | |||
Вычислим ''матрицу количества пересечений'' (<math>c_uv \;</math>) для этого графа. | |||
[[Файл:PADG_table.png]] | [[Файл:PADG_table.png]] | ||
| Строка 42: | Строка 60: | ||
Лемма 3. Pu;v2V2;u<2v cuv = cr(G; <1 ; <2): | Лемма 3. Pu;v2V2;u<2v cuv = cr(G; <1 ; <2): | ||