4551
правка
Параметризованные алгоритмы графического представления графов: различия между версиями
Перейти к навигации
Перейти к поиску
м
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 19:03, 30 марта 2016
, 30 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 62: | Строка 62: | ||
'''Теорема 4 ([9]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM (<math>G = (V_1, V2_, E), <_1 \;</math>), то <math>\sum_{u, v \in V_2, u \ne v} min \{ c_{uv}< v_{vu} \} \le k < 1.4664 \sum_{u, v \in V_2, u \ne v} \;</math>'''. | '''Теорема 4 ([9]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM (<math>G = (V_1, V2_, E), <_1 \;</math>), то <math>\sum_{u, v \in V_2, u \ne v} min \{ c_{uv}< v_{vu} \} \le k < 1.4664 \sum_{u, v \in V_2, u \ne v} min \{ c_{uv}< v_{vu} \} \;</math>'''. | ||