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

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

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

м

4430

правок

Версия от 22:19, 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, 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>'''.