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

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

58 байт добавлено , 30 марта 2016

м

4430

правок

@@ Строка 62: / Строка 62: @@
-Теорема 4 ([ ]). Если k – минимальное количество пересечений ребер в экземпляре задачи OSCM (G = (V1, V2, E); <1), то ^      minfcuv; cvug < k < 1:4664 E minfcuv;cvug : =v
+'''Теорема 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 \;</math>'''
 Нагамочи предложил алгоритм аппроксимации с коэффициентом меньше 1,4664.