4430
правок
Параметризованные алгоритмы графического представления графов: различия между версиями
Материал из WEGA
Параметризованные алгоритмы графического представления графов (посмотреть исходный код)
Версия от 14:11, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 65: | Строка 65: | ||
Нагамочи предложил алгоритм | Нагамочи предложил аппроксимационный алгоритм с коэффициентом меньше 1,4664. | ||
Далее, для любой вершины <math>u \in V_2 \;</math> с <math>deg(u) > 0 \;</math> обозначим за <math>l_u \;</math> самого левого соседа u в <math>L_1 \;</math>, а за <math>r_u \;</math> – самого правого. Две вершины <math>u, v \in V_2 \;</math> называются неподходящими, если существует некоторое <math>x \in N(u) \;</math>, такое, что <math>l_v <_1 x <_1 r_v \;</math>, либо существует некоторое <math>x \in N(v) \;</math>, такое, что <math>l_u <_1 x <_1 r_u \;</math>. В противном случае они называются подходящими. Заметим, что для подходящих <math>\{ u, v \} \;</math> верно <math>c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали: | Далее, для любой вершины <math>u \in V_2 \;</math> с <math>deg(u) > 0 \;</math> обозначим за <math>l_u \;</math> самого левого соседа u в <math>L_1 \;</math>, а за <math>r_u \;</math> – самого правого. Две вершины <math>u, v \in V_2 \;</math> называются неподходящими, если существует некоторое <math>x \in N(u) \;</math>, такое, что <math>l_v <_1 x <_1 r_v \;</math>, либо существует некоторое <math>x \in N(v) \;</math>, такое, что <math>l_u <_1 x <_1 r_u \;</math>. В противном случае они называются подходящими. Заметим, что для подходящих <math>\{ u, v \} \;</math> верно <math>c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали: | ||
