Геометричний пошук, Детальна інформація

Теорема. Довільний регулярний граф можна розбити на повну множину ланцюгів, монотонних відносно осі y.

Доведення. Покажемо виконання двох властивостей повної множини монотонних ланцюгів. Позначимо через W(e) вагу ребра e – кількість ланцюгів, яким належить e. Введемо позначення:

,

Покажемо, що ваги ребер можна обрати так, щоб виконувалися умови:

1. кожне ребро має додатню вагу;

2. для довільного vj (j \xF0B9 1, N) WIN (vj) = WOUT (vj).

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

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

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

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

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

begin

for кожне ребро з e do W(e) \xF0AC\xF0201; /* ініціалізація */

for i \xF0AC\xF0202 to N - 1 do

begin

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

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

if (WIN (vi) > vOUT (vi)) then W(d1) \xF0AC\xF020WIN (vi) - vOUT (vi) + 1;

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

for i \xF0AC\xF020N - 1 downto 2 do

begin

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

d2 \xF0AC\xF020крайнє зліва ребро, що входить у vi;

if (WOUT (vi) > WIN (vi)) then W(d2) \xF0AC\xF020WOUT (vi) - WIN (vi) + W(d2);

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

end.

нумерація вершин та ініціалізація ребер перший прохід



другий прохід повна множина ланцюгів

Приклад.