Учебная САПР электронных средств. Асланянц В.Р. - 50 стр.

UptoLike

ВУЗ: 

ВлГУ | Владимир

Составители: 

Рубрика: 

50
Первоначально (блок 6) все метки и локальные степени вершин при-
нимают нулевые значения. Затем одна из вершин (здесь первая) вклю-
чается (блок 7) в дерево. Далее фрагмент дерева разрастается. Выбирается
ближайшая к фрагменту I-я вершина (блоки 8...I6). Затем I-я вершина
включается (блок 23) в дерево, а соответствующее соединение пополняет
(блоки 24, 25) список соединений. Процесс продолжается до тех пор, пока
не будет выбрано ровно (Q-1) ребер для очередной цепи (блоки 7, 8, 17).
Описание подпрограммы LAY (рис. 12)
Блок 1 предназначен для формирования матрицы смежности
MM
IJ
MC
×
графа конфликтов соединений. Предварительно все вершины ок-
рашиваются одинаково (блок 3). Далее выбирается очередная I-я вершина
(блоки 5, 17), отыскиваются смежные с ней J-е вершины (блоки 7, 8, 10) и
среди них подсчитывается число
P
KV
вершин каждого (P-го) цвета (блок
9). Затем определяется цвет Н, в который окрашено минимальное число
вершин, смежных с I-й (блоки 11, ... , 15), и в этот цвет окрашивается I-я
вершина (блок 16). В случае если I-я вершина изолирована (P=0), т.е. со-
единение не конфликтует с другими, то его помещают (блок 16) в тот слой,
где находятся другие соединения той же цепи. Перекраска вершин выпол-
няется заданное число раз (блоки 4, 18).
Контрольная задача Test3-4
Входные данные
Входными данными программы TLO-3 являются 5 файлов проекта
Test3x4, обработанные программой PLACE-3 (см. раздел 3).
Выходные данные (упорядоченный список соединений).
49 M
27 21 28 21 6 1
28 13 29 13 7 1
11 18 10 13 17 1 X1, Y1, X2, Y2, CC, SC (49)
............................. (Файл BDP.SO)
9 4 28 29 3 2
8 4 29 29 5 2
Результаты представлены на рис. 13. Штриховыми линиями показа-
ны соединения, помещенные во 2-й слой. 
       Первоначально (блок 6) все метки и локальные степени вершин при-
нимают нулевые значения. Затем одна из вершин (здесь первая) вклю-
чается (блок 7) в дерево. Далее фрагмент дерева разрастается. Выбирается
ближайшая к фрагменту I-я вершина (блоки 8...I6). Затем I-я вершина
включается (блок 23) в дерево, а соответствующее соединение пополняет
(блоки 24, 25) список соединений. Процесс продолжается до тех пор, пока
не будет выбрано ровно (Q-1) ребер для очередной цепи (блоки 7, 8, 17).
       Описание подпрограммы LAY (рис. 12)
       Блок 1 предназначен для формирования матрицы смежности
 MC IJ M ×M графа конфликтов соединений. Предварительно все вершины ок-
рашиваются одинаково (блок 3). Далее выбирается очередная I-я вершина
(блоки 5, 17), отыскиваются смежные с ней J-е вершины (блоки 7, 8, 10) и
среди них подсчитывается число KVP вершин каждого (P-го) цвета (блок
9). Затем определяется цвет Н, в который окрашено минимальное число
вершин, смежных с I-й (блоки 11, ... , 15), и в этот цвет окрашивается I-я
вершина (блок 16). В случае если I-я вершина изолирована (P=0), т.е. со-
единение не конфликтует с другими, то его помещают (блок 16) в тот слой,
где находятся другие соединения той же цепи. Перекраска вершин выпол-
няется заданное число раз (блоки 4, 18).
                                    Контрольная задача Test3-4
      Входные данные
      Входными данными программы TLO-3 являются 5 файлов проекта
Test3x4, обработанные программой PLACE-3 (см. раздел 3).
      Выходные данные (упорядоченный список соединений).
      49                                                  M
      27 21 28 21 6 1
      28 13 29 13 7 1
      11 18 10 13 17 1                                 X1, Y1, X2, Y2, CC, SC (49)
      .............................                        (Файл BDP.SO)
       9 4 28 29 3 2
       8 4 29 29 5 2
      Результаты представлены на рис. 13. Штриховыми линиями показа-
ны соединения, помещенные во 2-й слой.




                                                                               50

Страницы