Информационные технологии проектирования электронных средств

- 34 - Последовательные алгоритмы компоновки Основная идея последовательных алгоритмов состоит в том, что по опре- деленным правилам формируется первый кусок разбиения, начиная с вершины, которая имеет наименьшую (наибольшую) локальную степень. Если таких вершин несколько, то начинаем с первой по порядку. Затем для этой вершины выделяются ее связи с другими вершинами графа, т.е. опре- деляется количество смежных с ней вершин. Если оказывается, что мощность множества  Г( x i )  = n 1 для выбранной вершины, то первый кусок сформирован. Тогда из матрицы смежности Е исключаются все вершины, вошедшие в первый кусок. Это означает, что из нее удаляются соответствующие строки и столбцы. Если окажется, что  Г( x i )  > n 1 , то в этом случае необходимо из Г 1 уда- лить “лишние вершины”. Как только мы начинаем удалять вершину, ее связи с остающимися вершинами станут внешними, отсюда следует, что мы должны удалить вершину, которая связана с остающимися вершинами меньшим числом ребер. Если  Г( x i )  < n 1 , то в этом случае мы должны добавить вершины в кусок G 1 по условию: σ( x j ) = ρ ( x j ) – a j = ) max j j σ(x , где ρ ( x j ) − локальная степень вершины x j , a j − количество связей вершины x j с еще не вошедшими в кусок G 1 вершинами. После того как кусок G 1 сформирован, т.е. из матрицы смежности удале- ны строки и столбцы, соответствующие вершинам, вошедшим в первый кусок, для матрицы смежности пересчитываются локальные степени оставшихся вер- шин. Процесс повторяется, т.е. мы приступаем к формированию куска G 2 . Последовательный алгоритм разрезания графа G считается завершенным, если сформирован ( ℓ –1)-й кусок. Иногда по конструктивным соображениям требуется закрепить некото- рые элементы схемы за вполне определенными кусками. Это означает, что по-