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

Двухуровневое графическое представление двудольного графа 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> количество пересечений в описываемом двухуровневом представлении. В контексте представления графов, разумеется, очень желательно получить минимальное число пересечений. В самой простой (и, вероятно, самой важной) форме это выглядит следующим образом: порядок вершин на одном уровне фиксируется, задача заключается в минимизации количества пересечений путем выбора порядка на втором уровне. Более формально: