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

Параметризованные алгоритмы графического представления графов (посмотреть исходный код)

Нет изменений в размере , 1 апреля 2016

м

4551

правка

Версия от 22:20, 1 апреля 2016 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 22:20, 1 апреля 2016 (просмотреть исходный код) 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} min \{ c_{uv}, v_{vu} \} \;</math>'''.		'''Теорема 4 ([9]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM <math>(G = (V_1, V_2, 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>'''.