Конференции ИВТ СО РАН

Тезисы докладов

Вычислительная математика

Разрезание графа на отдельные, связанные между собой куски - одна из распространённых графовых задач комбинаторно-логического типа. Решение таких задач, в частности, моделирует процесс компоновки радиоэлектронных средств, то есть разбиения принципиальной электрической схемы на отдельные части. Критерием качественного решения задачи разрезания графа чаще всего является минимум рёбер, соединяющих вершины из разных кусков. Множество таких рёбер называется числом рёберного соединения [1, с. 57]. В физическом смысле число рёберного соединения представляет собой количество внешних связей между кусками графа, сформированными в процессе разрезания.

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

Последовательные алгоритмы являются самыми высокопроизводительными и наиболее экономичными с точки зрения затрат оперативной памяти электронно-вычислительных средств (ЭВС), но и самыми неэффективными по результатам решения задач компоновки с использованием критерия минимума связей между сформированными кусками (внешних связей).

Причина этого недостатка заключается в следующем. В качестве критерия выбора начальной вершины формируемого куска служит минимальное или максимальное значение локальной степени вершины. В большинстве случаев заданному критерию выбора начальной вершины формируемого куска удовлетворяют одновременно несколько вершин. В данной ситуации рекомендуется отдавать предпочтение вершине, имеющей кратные рёбра [2, с. 30], а при наличии  нескольких вершин с этой характеристикой выбор осуществляется произвольно [3, с. 386].

Автоматизированное решение задачи разрезания графа исключает возможность произвольного выбора и требует чёткой конкретной формулировки критерия выбора начальной вершины из числа вершин с одинаковыми оценками. Для этой цели можно использовать индекс вершины - младший или старший номер позиции вершины в матрице смежности [4].

После выбора начальной вершины x_i выполняется построение множества Гx_i = {x_i, x_j, :, x_k}, содержащего выбранную начальную вершину x_i и все смежные ей вершины. Мощность полученного множества | Гx_i | сравнивается с количеством вершин, заданным для формируемого куска, и в случае их равенства кусок считается сформированным, а вошедшие в него вершины удаляются из исходного графа. Чаще всего оказывается, что | Гx_i | ≠ n_m, где m - количество вершин, заданное для формируемого куска.

Если | Гx_i | < n_m, то необходимо выполнить следующие шаги [2, с. 31].

Шаг 1. Во множестве Гx_i выбрать вершину x_j, имеющую максимальное количество связей со всеми остальными вершинами множества Гx_i и связанную с вершинами множества X Гx_i.

Шаг 2. Построить множество Гx_j.

Шаг 3. Сформировать объединённое множество Гx_i È Гx_j-.

Шаг 4 Проверить выполнение условия | Гx_i È Гx_j- | = n_m и в случае его невыполнения вновь повторить описанные шаги.

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

1) непонятно, как следует поступать, если критерию выбора вершины для дополнения куска соответствуют несколько вершин x_j--, x_k Î Гx_i;

2) по каким критериям следует выбирать вершину x_p Î XГx_i.

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

Оптимальность результата разрезания графа последовательным методом можно существенно повысить, если выбор вершины x_j для пополнения формируемого куска начинать  не в самом множестве X₁, как предлагается в [2], а в множестве XX₁ и использовать для этого числовую характеристику - число связности δ(x_j), которое определяется по формуле:

δ(x_j) = a(x_j) - z(x_j) {x_i | x_j ÎXX₁,                                      (1)

где a(x_j) - количество внешних связей, т.е. количество рёбер, соединяющих вершину x_j ÎXX₁ с вершинами, ранее назначенными в формируемый кусок;

z(x_j) - количество внутренних связей, т.е. количество рёбер, соединяющих вершину x_j с вершинами множества XX₁.

Из (1) очевидно, что число связности может принимать как положительное так отрицательное значение или быть равным нулю. Отрицательное значение δ(x_j) свидетельствует о том, что приращение внешних связей формируемого куска будет больше приращения внутренних связей, а положительное значение δ(x_j), наоборот, говорит о том, что приращение внешних связей формируемого куска будет меньше приращения внутренних связей. Так как для минимизации внешних связей определяющим является второй вариант, то выбор вершины для назначения в формируемый кусок следует осуществлять по критерию

δ(x_j) = max δ(x_j),                                                  (2)

В процессе формирования куска также может возникнуть ситуация, когда из куска необходимо удалить лишнюю вершину или несколько вершин, т.е. когда |Гx_i| > n_i. В этом случае для удаления рекомендуется выбирать вершину с минимальным количеством внутренних рёбер [2]. Если лишних вершин несколько, то удаление производится поочерёдно несколькими шагами, по одной вершине на каждом шаге.

Данный критерий выбора удаляемой вершины также нельзя назвать удачным. Как и в предыдущем случае, из [2] неясно, как поступать если данному критерию удовлетворяют несколько вершин.

Оптимальность результата в этом случае можно повысить, если выбор вершины для удаления осуществлять по критерию

δ(x_i) = a(x_i) - z(x_i) {x_i | x_i ÎX.                                       (3)

Из (3) следует, что наиболее оптимальный результат по критерию минимизации внешних связей обеспечит удаление из куска G₃ вершины x_i ÎX, удовлетворяющей условию

δ(x_i) = max δ(x_i),                                                   (4)

При разрезании графа на неравные по количеству вершин куски по методу [4] формирование первого куска выполняется до получения | X₁ | = min n_i, где n_i - количество вершин в наименьшем куске заданного разрезания. Производится вычисление текущего коэффициента разрезания, а формирование куска продолжается до следующего в порядке возрастания количества вершин, вновь вычисляется коэффициент разрезания и так далее до тех пор, пока не будут рассмотрены все варианты с разным количеством вершин в куске графа. Окончательно выбирается тот вариант, который соответствует максимальному значению коэффициента разрезания. Сформированный кусок удаляется из исходного графа, и описанная процедура повторяется для формирования каждого следующего куска графа. В результате многочисленных разрезаний графов методом [4] было установлено, что не во всех случаях удаётся получить оптимальный по критерию минимума внешних связей результат. Было выявлено неочевидное на первый взгляд обстоятельство: коэффициент разрезания не является объективным показателем качества по критерию минимума внешних связей в процессе выбора приемлемого с практической точки зрения варианта формируемого куска. При оценке различных вариантов увеличение коэффициента разрезания может иметь место при большем приращении внешних связей по сравнению с приращением внутренних связей формируемого куска графа.

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

ε(r) = k - l = min ε(r)

Выводы:

1) разрезание графа последовательным алгоритмом по предлагаемой методике, то есть с использованием чисел связности, позволяет минимизировать количество внешних связей между сформированными кусками. Это способствует улучшению эксплуатационных параметров проектируемых РЭС и повышает технологичность их производства;

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

Дополнительные материалы:

Полный текст доклада

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск