4551
правка
Параметризованные алгоритмы графического представления графов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 19:14, 30 марта 2016
, 30 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 59: | Строка 59: | ||
Лемма 3. <math>\sum_{u, v \in V_2, u <_2 c_{uv} } C_{uv} = cr(G, <_1, <_2) \;</math>. | '''Лемма 3'''. <math>\sum_{u, v \in V_2, u <_2 c_{uv} } C_{uv} = cr(G, <_1, <_2) \;</math>. | ||
| Строка 70: | Строка 70: | ||
Лемма 5 ([5]). При любом оптимальном отношении порядка <math><_2 \;</math> на вершинах <math>V_2 \;</math>, <math>u <_2 v \;</math> найдено, если <math>r_u \le_1 l_v \;</math>. | '''Лемма 5 ([5])'''. При любом оптимальном отношении порядка <math><_2 \;</math> на вершинах <math>V_2 \;</math>, <math>u <_2 v \;</math> найдено, если <math>r_u \le_1 l_v \;</math>. | ||
Это означает, что все подходящие пары встречаются в своем естественном порядке. | Это означает, что все подходящие пары встречаются в своем естественном порядке. | ||
Теперь можно сформулировать первый параметризованный алгоритм односторонней минимизации пересечений (OSCM), представляющий собой простой алгоритм поиска по дереву. По мере выполнения этого алгоритма последовательно строится подходящий порядок < | Теперь можно сформулировать первый параметризованный алгоритм односторонней минимизации пересечений (OSCM), представляющий собой простой алгоритм поиска по дереву. По мере выполнения этого алгоритма последовательно строится подходящий порядок <math><_2 \;</math> на <math>V_2 \;</math>; при установлении отношения порядка между u и v на <math>V_2 \;</math> в него будет ''включено'' <math>u <_2 v \;</math> или <math>v <_2 u \;</math>. Таким образом, обобщенный экземпляр задачи OSCM помимо двудольного графа <math>G = (V_1, V_2, E) \;</math> содержит отношение частичного порядка <math><_2 \;</math> на <math>V_2 \;</math>. Вершина <math>v \in V_2 \;</math> ''полностью включена'', если для всех <math>u \in V_2 \backslash \{ u, v \} \;</math> пара <math>\{ u, v \} \;</math> включена. | ||