Геометричний пошук

Перша умова встановлює факт належності кожного ребра хоча б одному ланцюгу. Друга умова гарантує, що WIN (vj) ланцюгів проходить через vj і їх можна обрати так, щоб вони не перетиналися.

Теорема. Реалізація умови WIN = WOUT є розв’язком потокової задачи і може бути досягнута за два проходи по графу G.

Покладемо спочатку W(e) = 1 для кожного ребра e. При першому проході від v1 до vN отримаємо WIN (vi)  WOUT (vi) для всіх некрайніх vi. При другому проході від vN до v1 отримаємо WIN (vi)  WOUT (vi). Отже після двох проходів матимемо реалізацію умови WIN (vi) = WOUT (vi).

Позначимо vIN (v) = | IN(v)|, vOUT (v) = | OUT(v)|.

Балансування за вагою в регулярному графі

begin

for кожне ребро з e do W(e) 1; /* ініціалізація */

for i 2 to N - 1 do

begin

WIN (vi) сума ваг ребер, що входять у vi;

d1 крайнє зліва ребро, що виходить з vi;

if (WIN (vi) > vOUT (vi)) then W(d1) WIN (vi) - vOUT (vi) + 1;

end; /* перший прохід */

for i N - 1 downto 2 do

begin

WOUT (vi) сума ваг ребер, що виходять з vi;

d2 крайнє зліва ребро, що входить у vi;if (WOUT (vi) > WIN (vi)) then W(d2) WOUT (vi) - WIN (vi) + W(d2);

end; /* другий прохід */

end.

Приклад.

Перший прохід. Нехай i = 6 (ваги всіх ребер, що виходять з k - ої (k < 6) вершини, вже розставлені). WIN (v6) = 4 (вхідними є ребра: 36 – вага 1, 46 – вага 1, 56 – вага 2). Ребра, що виходять з v6: 67, 69. d1 = 69 (крайнє зліва ребро). vOUT (v6) = 2, WIN (v6) > vOUT (v6), тому що 4> 2. W(69) = 4 - 2 + 1 = 3.

Другий прохід. Нехай i = 3. WOUT (v3) = 3. Ребра, що входять у v3: 13. d2 = 13 (крайнє зліва ребро). W(13) = 1. WIN (v3) = 1. WOUT (v3) > WIN (v3), тому що 3 > 1. W(13) = 3 - 1 + 1 = 3.

Теорема. Довільний планарний граф можна перетворити в регулярний.

Доведення. Нехай v – нерегулярна вершина графа G. Припустимо, що з неї не виходить жодного ребра. Горизонтальна пряма, що проходить через v, протикає в загальному випадку пару ребер e1 та e2 графа G, найближчих до v зліва та справа. Оскільки v не є крайньою вершиною, то один з цих проколів повинен існувати. Нехай vi – верхня вершина ребер ei (i = 1, 2), а v* – та з вершин vi, що має найменшу ординату (наприклад, v2). Тоді відрізок vv* не перетинає ребер G (в загальному випадку це не вірно і тоді алгоритм регуляризації слід змінити) і може бути доданим до ребер планарного графу, регуляризуючи вершину v.