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

'''Теорема 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).'''

'''Теорема 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>'''