Глава 2. Постановка задачи разрезания графов

Задача разрезания формулируется следующим образом. Требуется разрезать граф G=(S,V) на части G_j=(S_j,V_j), j=1,2,…,F, где F – число частей, на которые разрезается граф; S_j – множество вершин, принадлежащих j-й части; Vj – множество ребер инцидентных вершинам S_j.

Совокупность частей B(G_j) называется разбиением графа G, если

Здесь V_fq – множество ребер, связывающих пары вершин, одна из которых принадлежит части G_f, а другая – G_q.

Обозначим и назовем его числом реберного соединения частей G_f и G_q. Тогда число реберного соединения разрезания графа G определяется величиной g:

Традиционным критерием решения задачи разрезания графа G является минимизация числа реберного соединения g при ограничении на число вершин в частях G_j.

Задачу разрезания графа на минимально связанные части можно отнести к числу классических задач теории графов, широко используемых в практических приложениях. Среди наиболее ранних и хорошо разработанных приложений является задача разбиения схемы вычислительного устройства, представленного в виде графа [3] или в виде более адекватной модели – гиперграфа [4].

Среди известных алгоритмов разрезания графов существуют точные алгоритмы, использующие методы решения задач дискретного программирования, и приближенные. Более широкое распространение получили приближенные алгоритмы, среди которых выделяются последовательные, итерационные и смешанные.

В приближенных алгоритмах последовательного типа сначала по определенному критерию выбирается вершина графа, затем к ней присоединяются другие вершины до получения первой части. Затем из оставшихся вершин графа формируется вторая часть и последующие части до полного разрезания

Итерационные алгоритмы в качестве исходного берут некоторое разрезание, полученное, например, с помощью одного из последовательных алгоритмов, а затем последовательно в связанных парах частей производятся перестановки вершин из одной части в другую так, чтобы улучшалось значение критерия качества.

Анализ данных алгоритмов приводит к следующим выводам:

• наличие большого разнообразия алгоритмов, которое порождается стремлением учесть специфику исследуемых объектов и используемых для их описания графов;

• ориентация алгоритмов на работу непосредственно со списками вершин, ребер и их атрибутов;

• выполнение операций по оптимизации реберного соединения между двумя частями графа носит локальный характер и «не видит», что происходит с реберными соединениями между другими частями разрезания.

Первые два вывода отражают как положительные, так и отрицательные свойства алгоритмов. Так, учет специфики приводит к уникальности алгоритмов, но позволяет повышать их эффективность. Использование списков является предпочтительным для графов с большим числом вершин и малым числом ребер. Что касается третьего вывода, то он отражает труднопреодолимый недостаток таких алгоритмов, когда оптимизация осуществляется локальными улучшениями реберных соединений внутри очередной пары частей разрезания.

Предлагаемый в данной работе алгоритм разрезания основан на представлении графа передачи данных (рис. 2) матрицей связности вершин и более полном анализе оценок эффективности назначения вершин в подграфы разрезания[6].