4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 18:25, 30 марта 2016
, 30 марта 2016→Нотация
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Нотация) |
||
| Строка 6: | Строка 6: | ||
Двухуровневое графическое представление двудольного графа G = ( | Двухуровневое графическое представление двудольного графа 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 = (U1 ; u2) и f = (v1 ; v2), которые пересекаются в реализации двухуровневого графического представления (G; <1 ; <2). Хорошо известно, что два ребра пересекаются в том и только том случае, если щ <1 v1 и v2 <2 u2; иными словами, это понятие несет чисто комбинаторный смысл, не зависящий от конкретной реализации двухуровневого графического представления. Обозначим за cr(G; <1 ; <2) количество пересечений в описываемом двухуровневом представлении. В контексте представления графов, разумеется, очень желательно получить минимальное число пересечений. В самой простой (и, вероятно, самой важной) форме это выглядит следующим образом: порядок вершин на одном уровне фиксируется, задача заключается в минимизации количества пересечений путем выбора порядка на втором уровне. Более формально: | ||