4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 18:56, 30 марта 2016
, 30 марта 2016→Основные результаты
Irina (обсуждение | вклад) м (→Нотация) |
Irina (обсуждение | вклад) |
||
| Строка 46: | Строка 46: | ||
Теорема 1 ([6]). Задача разрешимости, соответствующая k-OSCM, является NP-полной. | '''Теорема 1 ([6]). Задача разрешимости, соответствующая k-OSCM, является NP-полной.''' | ||
Далее будем предполагать, что <math>G = (V_1, V_2, E) \;</math> – экземпляр задачи OSCM с фиксированным порядком <math><_1 \;</math> на <math>V_1 \;</math>. | |||
Теорема 2 ([3]). cr(G | Проверить, существует ли порядок на <math>V_2 \;</math>, позволяющий избежать пересечений, можно за полиномиальное время. Это наблюдение основывается на одной из следующих теоретико-графовых характеристик: | ||
Теорема 2 ([3]). '''cr(G, <_1, <_2) = 0 \;''' в том и только том случае, если G является ациклическим и для любого пути (x, a, y) в G, '''x, y \in V_1 \;''', выполняется следующее: для всех '''u \in V_1 \;''' при <math>x <_1 u <_1 y \;</math> единственным ребром, инцидентным u, если таковое существует, является (u, a). | |||
Ранее введенное понятие является критически важным по следующим причинам: | Ранее введенное понятие является критически важным по следующим причинам: | ||
Лемма 3. Pu;v2V2;u<2v cuv = cr(G; <1 ; <2): | Лемма 3. Pu;v2V2;u<2v cuv = cr(G; <1 ; <2): | ||