Теория и практика параллельных вычислений
Метод рекурсивного деления пополам
Для решения задачи разбиения графа можно рекурсивно применить метод бинарного деления (the binary bisection method), при котором на первой итерации граф разделяется на две равные части, далее на втором шаге каждая из полученных частей также разбивается на две части и т. д. В данном подходе для разбиения графа на k частей необходимо log2k уровней рекурсии и выполнение k-1 деления пополам. В случае когда требуемое количество разбиений k не является степенью двойки, каждое деление пополам необходимо осуществлять в соответствующем соотношении.
Поясним схему работы метода деления пополам на примере разделения графа на рис. 10.11 на 5 частей. Сначала граф следует разделить на 2 части в оотношении 2:3 (непрерывная линия), затем правую часть разбиения – в отношении 1:3 (штриховая линия), после этого осталось разделить 2 крайние подобласти слева и справа в отношении 1:1 (штрих-пунктир).
Рис. 10.11. Пример разбиения графа на 5 частей методом рекурсивного деления пополам
