Студопедия — Промежуточные данные подпрограммы LAY
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Промежуточные данные подпрограммы LAY






MC (M, M) - матрица смежности графа конфликтов соединений;

SC (M) - вектор цветов, в которые окрашены вершины. Например, SC 5=2 означает, что 5-я вершина графа конфликтов окрашена во второй цвет (т. е. пятое соединение помещено во второй слой);

F - переменная для счета числа итераций алгоритма раскраски;

I, J - номера вершин графа конфликтов;

К - номер цвета вершин (номер слоя платы);

KV(S) - количество вершин Р -го цвета, смежных I -й вершине. Например, KV 2 = 4 означает, что из всех вершин, смежных 2 -й вершине, четыре окрашены во 2-й цвет;

P, H - переменные для запоминания номера цвета.

Описание схемы подпрограммы TREE (рис. 11)

В программе ТRЕЕ реализован алгоритм Прима, который работает следующим образом. Выбирается оче­редная электрическая цепь схемы (блоки 2, 3, 18), определяется (блок 4) число Q ее контактов (концов), их координаты ХС, YC(Q), и формируется матрица ML(Q, Q) длин ребер полного графа (блок 5), построенного на этих контактах.

 

 

Рис. 11. Схема программного модуля TLO-3

 

 

 

 

Рис. 12. Схема подпрограммы LAY-3

 

Первоначально (блок 6) все метки и локальные степени вершин принимают нулевые значения. Затем одна из вершин (здесь первая) вклю­чается (блок 7) в дерево. Далее фрагмент дерева разрастается. Вы­бирается ближайшая к фрагменту I -я вершина (блоки 8...I6). Затем I -я вершина включается (блок 23) в дерево, а соответствующее сое­динение пополняет (блоки 24, 25) список соединений. Процесс продол­жается до тех пор, пока не будет выбрано ровно (Q -1) ребер для оче­редной цепи (блоки 7, 8, 17).

Описание подпрограммы LAY (рис. 12)

Блок 1 предназначен для формирования матрицы смежности графа конфликтов соединений. Предварительно все вершины окрашива­ются одинаково (блок 3). Далее выбирается очередная I -я вершина (блоки 5, 17), отыскиваются смежные с ней J -е вершины (блоки 7, 8, 10) и среди них подсчитывается число вершин каждого (P -го) цвета (блок 9). Затем определяется цвет Н, в который окрашено минимальное число вершин, смежных с I -й (блоки 11,..., 15), и в этот цвет окрашивается I -я вершина (блок 16). В случае если I -я вершина изолирована (P =0), т.е. соединение не конфликтует с дру­гими, то его помещают (блок 16) в тот слой, где находятся другие соединения той же цепи. Перекраска вершин выполняется заданное число раз (блоки 4, 18).







Дата добавления: 2014-11-10; просмотров: 478. Нарушение авторских прав; Мы поможем в написании вашей работы!



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

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Аальтернативная стоимость. Кривая производственных возможностей В экономике Буридании есть 100 ед. труда с производительностью 4 м ткани или 2 кг мяса...

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

Понятие метода в психологии. Классификация методов психологии и их характеристика Метод – это путь, способ познания, посредством которого познается предмет науки (С...

ЛЕКАРСТВЕННЫЕ ФОРМЫ ДЛЯ ИНЪЕКЦИЙ К лекарственным формам для инъекций относятся водные, спиртовые и масляные растворы, суспензии, эмульсии, ново­галеновые препараты, жидкие органопрепараты и жидкие экс­тракты, а также порошки и таблетки для имплантации...

Тема 5. Организационная структура управления гостиницей 1. Виды организационно – управленческих структур. 2. Организационно – управленческая структура современного ТГК...

Понятие о синдроме нарушения бронхиальной проходимости и его клинические проявления Синдром нарушения бронхиальной проходимости (бронхообструктивный синдром) – это патологическое состояние...

Опухоли яичников в детском и подростковом возрасте Опухоли яичников занимают первое место в структуре опухолей половой системы у девочек и встречаются в возрасте 10 – 16 лет и в период полового созревания...

Способы тактических действий при проведении специальных операций Специальные операции проводятся с применением следующих основных тактических способов действий: охрана...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия