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

Далее, для любого <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} c_{uv} \cdot c_{vu} = 0 \;</math>. Джумович и Уайтсайдз показали: