Реферат: Методы и алгоритмы компоновки, размещения и трассировки печатных плат
Сформулируем алгоритм последовательной компоновки конструктивных элементов.
1) t:0
2) Xf = Xt = Ø; t=t+1; Θ=1; α=nmax ,
Где t, Θ – порядковые номера формируемого куска и присоединяемой вершины; α – ограничение на число вершин в куске.
3) По матрице смежности исходного графа | αhp |NxN , где N– число вершин исходного графа (при большом значении N для сокращения объема оперативной памяти ЭВМ используем не саму матрицу смежности, а её кодовую реализацию), определяем локальные степени вершин 
.
4) Из множества нераспределенных вершин Xвыбираем вершину xj с ρ(xj ) = 
. Переходим к п.6. Если таких вершин несколько, то переходим к п.5
5) Из подмножества вершин Xl с одинаковой локальной степенью выбирают вершину xj с максимальным числом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj | = 
.
6) Запоминаем исходную вершину формируемого куска графа 
. Переходим к п.10
7) По матрице смежности 
строим множество Xs = 
и определяем относительные веса вершин 
:
.
8) Из множества XS выбираем вершину 
. Переходим к п.10. Если таких вершин несколько, то переходим к п.9.
9) Из подмножества вершин Xv с одинаковым относительным весом выбираем вершину xj с максимальной локальной степенью, т.е. 
.
10)
.
11) Если >m , то переходим к п.13.
12) Рассмотренные вершины включаем в формируемый кусок Xf = Xt .
13)Θ = Θ + 1.
14) Если Θ> α, то переходим к п.15, а противном случае – к п.7.
15) Если |Xf |<nmin , где nmin – минимально допустимое число вершин в куске, то переходим к п.21.
16) Выбираем окончательный вариант сформированного куска графа:
Xt = Xf ; X = X \ Xt ; α = nmax .
17)Если |X|> nmax , то переходим к п.20.
18) Если |X|< nmin , то переходим к п.21.
19) Определяем число внешних связей последнего куска графа:
,
где F – множество индексов вершин, входящих в X. Если 
, то переходим к п.21, в противном случае – к п.24.
20) Если t<k – 1 , где k - число кусков разрезания графа, то переходим к п.2, в противном случае – к п.23.
21) Предыдущий цикл «разрезания» считаем недействительным. Если t>1, т.е. имеется как минимум один ранее сформированный кусок, то переходим к п.22. в противном случае – к п.23.
22) Ищем другой допустимый вариант формирования предыдущего куска с меньшим числом вершин: t = t – 1; 
.
Переходим кп.7.