Статья: Модификация матричного метода разрезания графа

Модификация матричного метода разрезания графа

А.С. Шандриков

Техническое проектирование радиоэлектронных средств (РЭС) предполагает в первую очередь решение задачи компоновки модулей в определённые конструктивные единицы. Для решения данной задачи используется математическая модель в виде графа G = (X, U), которым заменяется принципиальная электрическая схема проектируемого РЭС. Множество вершин X обозначает радиоэлектронные компоненты (РЭК) проектируемого изделия, а множество рёбер U - связи между ними в соответствии с принципиальной электрической схемой. Компоновка, т.е. распределение РЭК по определённым конструктивным электронным модулям, моделируется разрезанием графа на куски с заданным количеством вершин в каждом из них. Для оценки качества решения задачи разрезания графа используются такие количественные показатели, как минимум внешних связей между кусками K (K = min K) или максимум коэффициента разрезания ?G, вычисляемого по формуле

?G = /K (1)

где - суммарное количество внутренних рёбер графа, связывающих вершины внутри кусков.

Разрезание графов осуществляется различными методами, чаще всего последовательными и итерационными.

Последовательные методы легко реализуются на ЭВМ, отличаются простотой и высокой производительностью, но в большинстве случаев не обеспечивают оптимальных результатов [1, с. 61].

Итерационные методы позволяют получить более приемлемые с точки зрения критерия (1) результатов, однако полученные результаты также не всегда оптимальны.

Среди итерационных методов наибольшей эффективностью обладает матричный метод [2, с. 62-70]. Суть матричного метода разрезания графа заключается в следующем. Любой граф можно подробно описать матрицей инцидентности I, матрицей цепей T и матрицей смежности R. Из этого следует, что разрезание графа G на k кусков G₁, G₂,…, G_k эквивалентно делению матрицы на клетки. В случае матрицы смежности R разрезание графа соответствует разрезанию матрицы на k² клеток (подматриц) как показано на рис. 1.

Рис. 1. Разрезание матрицы смежности, соответствующее разрезанию графа на три куска

Клетки (подматрицы), расположенные по главной диагонали матрицы R, соответствуют кускам G_i графа G. Элементы, расположенные в диагональных клетках, определяют количество рёбер, соединяющих вершины куска G_i между собой (внутренние связи). Элементы, расположенные в остальных клетках, определяют количество рёбер, соединяющих куски между собой (внешние связи).

Решение задачи разрезания графа G на k кусков сводится к изоморфному преобразованию матрицы смежности путём выполнения ряда перестановок строк и столбцов, в результате которых должна быть достигнута максимизация сумм элементов, расположенных в диагональных подматрицах.

Применяемый на практике матричный метод разрезания графа G на k кусков выполняется следующим образом. Задаётся стандартная матрица F = f_ij||_n, которая разделяется на k² подматриц. При этом по главной диагонали располагают k единичных подматриц. Порядок единичных подматриц определяется количеством вершин, заданным для каждого куска. Недиагональные подматрицы заполняются нулями. В матрице смежности R по главной диагонали выделяются подматрицы в соответствии с делением стандартной матрицы F. После этого строится первая вспомогательная матрица M = m_ijn, где i, j J = {1, 2, …, n}, представляющая собой результат умножения матриц F и R:

M = F R (2)

Элементы матрицы M вычисляются по формулам:

m_ij = , m_ji = (3)

Далее осуществляется построение матрицы (инверсии матрицы F), в которой каждый единичный элемент матрицы F заменяется на нулевой и наоборот. Как результат поэлементного перемножения матриц F и R вычисляется вторая вспомогательная матрица B:

B = F R (4)

По формулам

p_ij = m_ij - b_ij; p_ij = m_ij - b_ij (5)

_ij = p_ij + p_ji - (p_ii + p_jj) (6)

вычисляются элементы третьей вспомогательной матрицы P и перестановочной матрицы H соответственно. В перестановочной матрице H выбирается максимальный положительный элемент _ij и соответствующие ему элементы x_i и x_j меняются местами, т.е. производится перестановка вершин x_i и x_j графа из одного куска в другой.

Несмотря на свою эффективность, матричный метод не получил широкого применения и практически не используется. Это объясняется тем, что кроме матрицы смежности исходного графа G необходимо построить шесть вспомогательных матриц. Таким образом, в течение одной итерации обрабатываются семь матриц. Количество итераций зависит от чередования строк и столбцов в начальной матрице смежности R и может быть неопределённо большим. Необходимость обработки больших числовых массивов, насчитывающих в сумме 7n² элементов, где n - количество вершин разрезаемого графа, накладывает существенные ограничения на номенклатуру проектируемых изделий по такому параметру, как количество РЭК, распределяемых по электронным модулям, а также на производительность процесса.

Есть и ещё один существенный недостаток матричного метода разрезания графа. Как показывает практика, оптимальный результат обеспечивается только:

- при разрезании графа на одинаковые по количеству вершин куски;

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

Отмеченные недостатки можно устранить, если матричное разрезание графа G выполнять с использованием чисел связности. Число связности - это параметр, характерный для любой вершины x_k разрезанного на куски G_i, G_j, …, G_l графа G и в физическом смысле представляет собой разность между количеством внешних б(x_i) и внутренних z(x_i) связей.

Логика применения чисел связности для парной перестановки вершин из одного куска в другой с целью минимизации внешних связей описана в [1, с. 78-87] и заключается в следующем. Предположим, что некоторый граф G разрезан на два куска G₁ = (X₁, U₁) и G₂ = (X₂, U₂). Вершина x_i X₁ содержит z(x_i) внутренних связей и б(x_i) - внешних. Число связности определяется по формуле

радиоэлектронный компоновка модуль граф

д(x_i) = б(x_i) - z(x_i) (7)

Если д(x_i) > 0, то это означает, что перемещение вершины x_i из куска G₁ в кусок G₂ уменьшит количество внешних связей на величину д(x_i). Если в куске G₂ также имеется вершина x_j X₂, для которой д(x_j) ? 0, то её перемещение из куска G₂ в кусок G₁ ещё уменьшит количество внешних связей на величину д(x_j). В результате парного перемещения вершин x_i и x_j из одного куска в другой количество внешних связей K между кусками G₁ и G₂ уменьшится на величину

ДK = д(x_i) + д(x_j) - 2u_ij, (8)

где 2u_ij - количество рёбер, соединяющих перемещаемые вершины x_i и x_j между собой.

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

На рис. 2 представлен граф G = (X, U), содержащий 14 вершин и 21 соединительное ребро. Данный граф требуется разрезать на четыре куска, содержащие 3, 3, 4 и 4 вершин соответственно без каких-либо технологических ограничений.

Рис. 2

Решение данной задачи осуществляется в следующей последовательности.

1. Построить матрицу смежности, выделив в ней по главной диагонали две подматрицы 3-го и две подматрицы 4-го порядка в соответствии с заданным разрезанием графа.

2. Для каждой вершины графа определить числа связности с вершинами других кусков графа. Полученные результаты представлены в дополнительных столбцах матрицы смежности (9).

3. По числам связности построить матрицу перестановочных коэффициентов ДK, элементы Дk_ij которой вычисляются по формуле (8).

4. Построить множество двухэлементных подмножеств, каждое из которых содержит пару вершин с положительным перестановочным коэффициентом:

T = {{x₁, x₉}, {x₁, x₁₂}, {x₂, x₈}, {x₂, x₁₄}, {x₃, x₈}, {x₃, x₁₁}, {x₃, x₁₂},

{x₃, x₁₃}, {x₃, x₁₄}, {x₄, x₈}, {x₄, x₁₁}, {x₄, x₁₂}, {x₄, x₁₃}, {x₄, x₁₄},

{x₅, x₁₁}, {x₅, x₁₂}, {x₅, x₁₄}, {x₆, x₁₁}, {x₆, x₁₃}, {x₆, x₁₄}, {x₇, x₁₁},

{x₇, x₁₄}, {x₈, x₁₂}, {x₈, x₁₃}, {x₈, x₁₄}, {x₉, x₁₁}, {x₉, x₁₂}, {x₉, x₁₃},

{x₉, x₁₄}, {x₁₀, x₁₂}, {x₁₀, x₁₃}, {x₁₀, x₁₄}} (11)

5. Из множества (11) сформировать возможные варианты множеств, содержащих двухэлементные непересекающиеся подмножества, т.е. подмножества не связанных между собой пар вершин. Таких вариантов для рассматриваемого графа оказалось 85. Учитывая ограниченность объёма, в статье приводятся только некоторые из полученных вариантов:

A₁ = {{x₁, x₉}, {x₄, x₁₁}, {x₅, x₁₂}};

A₂ = {{x₁, x₉}, {x₄, x₁₁}, {x₆, x₁₃}};

A₃ = {{x₁, x₉}, {x₄, x₁₂}, {x₁₀, x₁₃}};

…;

A₄₀ = {{x₃, x₁₂}, {x₈, x₁₁}};

…;

A₈₅ = {{x₉, x₁₃}, {x₁₀, x₁₂}}.

6. Для каждого полученного множества подсчитать сумму перестановочных коэффициентов входящих в него пар вершин:

S₁ = Дk₁₉ + Дk₄₁₁ + Дk₅₁₂ = 2 + 1 + 1 = 4;

S₂ = Дk₁₉ + Дk₄₁₁ + Дk₆₁₃ = 2 + 1 + 1 = 4;

S₃ = Дk₁₉ + Дk₄₁₂ + Дk₁₀₁₃ = 2 + 3 + 3 = 8;

…;

S₄₀ = Дk₃₁₂ + Дk₈₁₁ = 2 + 3 = 5;

…;

S₈₅ = Дk₉₁₃ + Дk₁₀₁₂ = 1 + 1 = 2.

7. Выбрать множество, имеющее максимальную сумму перестановочных коэффициентов. Если данному условию удовлетворяют несколько множеств, то выбрать следует то, у которого сумма локальных степеней вершин, составляющих двухэлементные подмножества, минимальна. Это позволяет уменьшить количество последующих итераций. В описываемом примере среди всех (85) полученных вариантов имеется только одно множество с максимальной суммой перестановочных коэффициентов входящих в него пар вершин. Это множество A₃, для которого сумма перестановочных коэффициентов S₃ = 8 = max.

8. Переставить в матрице смежности R попарно x₁ и x₉, x₄ и x₁₂, x₁₀ и x₁₃ строки и столбцы. В результате будет получена матрица смежности R₁, изоморфная исходной матрице смежности R:

9. Для каждой вершины графа вновь подсчитать числа связности с вершинами других кусков графа. Полученные результаты представлены в дополнительных столбцах матрицы смежности (12).

10. Используя формулу (8), построить матрицу перестановочных коэффициентов ДK₁:

11. Из элементов полученной матрицы может быть образовано только два двухэлементных множества, состоящих из пары вершин с положительным перестановочным коэффициентом, причём эти множества пересекающиеся, т.к. в состав каждого из них входит вершина x₂. По этой причине для перестановки может быть выбрано только одна пара вершин: x₂ и x₁₂ или x₂ и x₅. Так как перестановочные коэффициенты этих пар одинаковы (Дk₂₁₂ = Дk₂₅ = 1), то для перестановки выбираем ту пару вершин, у которой сумма локальных степеней меньше. Этому условию удовлетворяет пара вершин x₂ и x₅ (с(x₅) = 2 < с(x₁₂) = 3).

Переставить в матрице смежности R₁ x₂ и x₅ строки и столбцы. Получим матрицу смежности R₂.

12. Построить матрицу перестановочных коэффициентов ДK₂:

13. В полученной матрице ДK₂ нет ни одного положительного перестановочного коэффициента. Это означает, что после второй итерации в текущем варианте разрезания графа нет ни одной пары вершин, перестановка которых из одного куска в другой могла бы уменьшить количество внешних связей и куски G₁ = (X₁, U₁), G₁ = (X₂, U₂), G₃ = (X₃, U₃) и G₄ = (X₄, U₄) следует считать сформированными, где X₁ = {x₃, x₅, x₉}; X₂ = {x₂, x₆, x₁₂}; X₃ = {x₁, x₇, x₈, x₁₃}и X₄ = {x₄, x₁₀, x₁₁, x₁₄}. Графическая иллюстрация полученного разрезания представлена на рис. 3.

Рис. 3

Литература

1. Морозов К.К., Мелихов А.Н., Бернштейн Л.С. Методы разбиения схем РЭА на конструктивно законченные части. - М.: Сов. радио, 1978.

2. Мелихов А.Н., Бернштейн Л.С., Курейчик В.М. Применение графов для проектирования дискретных устройств. - М.: Наука, 1974.