Теория и практика параллельных вычислений
Деление с учетом связности
С самых общих позиций понятно, что при разделении графа информационная зависимость между разделенными подграфами будет меньше, если соседние вершины (вершины, между которыми имеются дуги) будут находиться в одном подграфе. Алгоритм деления графов с учетом связности (the levelized nested dissection algorithm) пытается достичь этого, последовательно добавляя к формируемому подграфу соседей. На каждой итерации алгоритма происходит разделение графа на 2 части. Таким образом, разделение графа на требуемое число частей достигается путем рекурсивного применения алгоритма.
Общая схема алгоритма может быть описана при помощи следующего набора правил.
Алгоритм 10.2. Общая схема выполнения алгоритма деления графов с учетом связности
- Iteration = 0.
- Присвоение номера Iteration произвольной вершине графа.
- Присвоение ненумерованным соседям вершин с номером Iteration номера Iteration + 1.
- Iteration = Iteration + 1.
- Если еще есть неперенумерованные соседи, то переход на шаг 3.
- Разделение графа на 2 части в порядке нумерации.
Для минимизации информационных зависимостей имеет смысл в качестве начальной выбирать граничную вершину. Поиск такой вершины можно осуществить методом, близким к рассмотренной схеме. Так, перенумеровав вершины графа в соответствии с алгоритмом 10.2 (начиная нумерацию из произвольной вершины), мы можем взять любую вершину с максимальным номером. Как нетрудно убедиться, она будет граничной.
Пример работы алгоритма приведен на рис. 10.15. Цифрами показаны номера, которые получили вершины в процессе разделения. Сплошной линией показана граница, разделяющая 2 подграфа. Также на рисунке показано лучшее решение (пунктирная линия). Очевидно, что полученное алгоритмом разбиение далеко от оптимального, так как в приведенном примере есть решение только с тремя пересеченными ребрами вместо пяти.
Рис. 10.15. Пример работы алгоритма деления графов с учетом связности
