Устройство для раскраски графов

Устройство для раскраски графов

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано при автоматизации разработки печатных плат. В этом случае число красок (классов раскраски) определяет верхнюю границу количества слоев платы, при том, что вершины одного цвета могут быть расположены в одном ее слое. Цель изобретения - повышение быстродействия устройства. Устройство содержит блок 1 синхронизации, блок 2 определения класса раскраски, блок 3 задания матрицы смежности и блок 4 регистрации. Кроме этого, на фиг. 1 цифровые обозначения имеют вход 5 начальной установки устройства, вход 6 пуска устройства, с первого по третий выходы 7...9 блока 1 синхронизации и выходы 10 группы блока 1 синхронизации, выходы 11 признаков наличия ветвей графа блока 3 и выходы 12 признаков принадлежности вершин составу класса блока 2 определения класса раскраски. После начальной установки устройства в блок 3 заносят информацию о топологии графа. После подачи сигнала на вход 6 пуска блок 1 синхронизации формирует последовательность сигналов, обеспечивающую определение при помощи блока 2 состава вершин каждого класса раскраски и регистрацию в блоке 3. 1 з.п. ф-лы, 4 ил.

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ РЕСПУБЛИН (ц) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ НОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4321404/24-24 (22) 26.10.87 (46) 07.10,89. Бюп. У 37 (71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (72) В.М.Глушань, С.И.Резниченко и И.Г.Ефремов (53) 681.333(088.8) (56)1 Авторское свидетельство СССР

У 433485, кл. G 06 F 15/20, 1972.

Авторское свидетельство СССР

У 1283783, кл. С 06 Р 15/20, 1.985.

° (54) УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРА-

ФОВ (57) Изобретение относится к вычислительной технике и может быть использовано при автоматизации разработки печатных плат..В этом случае число красок (классов раскраски) определяет верхнюю границу количества слоев платы, при том, что вершины одного цвета могут быть расположены в одном ее слое. Цель изобретения — повышение

„„Я0„„1513470 A1

2 быстродействия устройств а. Устройство содержит блок 1 синхронизации, блок 2 определения класса раскраски, блок 3 задания матрицы смежности и блок 4 регистрации. Кроме этого, на фиг. 1 цифровые обозначения, имеют вход 5 начальноч установки устройства, вход 6 пуска устройства, с первого по третий выходы 7 — 9 блока 1 синхронизации и выходы 10 группы блока 1 синхронизации, выходы 11 признаков наличия ветвей графа блока 3 и выходы 12признаков принадлежности вершин составу класса блока 2 определения класса раскраски. После начальной установки устройства в блок 3 заносят информа- а цию о топологии графа. После подачи сигнала на вход 6 пуска блок 1 синхронивации формирует последовательность сигнапов, обеспечивающую определение Ш при помощи блока 2 состава вершин каждого класса раскраски и регистра. цию в блоке 3. 1 з.п.ф-лы, 4 ил.

Мима

15134

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

Цель изобретения — повышение быст- 10 родействия устройства.

На фиг, 1 представлена функциональная схема устройства; на фиг. 2 — временная диаграма работы блока синхронизации; на фиг. 3 — функциональная схема блока определения класса раскраски; на фиг. 4 — функциональная схема узла синхронизации.

Устройство содержит блок 1 синхронизации, блок 2 определения клас- 20 са раскраски, блок 3 задания матрицы смежности и блок 4 регистрации. Кроме того, устройство имеет вход 5 начальной установки устройства, вход 6 пуска устройства, с первого по третий 25 выходы 7 — 9 блока 1 синхронизации и выходы 10 группы блока 1 синхрониза-:. ции, выходы 11 признаков наличия вет-! вей графа блока 3 и выходы 12 признаков принадлежности вершин составу 30

I класса блока 2 определения класса раскраски.

Блок 2 определения, класса раскраски содержит узел 13 синхронизации, коммутатор 14, узел 15 логического сложения, узел 16 проверки смежности вершин, накапливающий узел 17 логического сложения, тактовый выход 18 узла 13 синхронизации и его выходы 19 группы. 40

Устройство р абот ает следующим о бразом.

На вход 5 начальной установки подают импульсный сигнал уровня логической единицы. При этом в блоках 2 5 и 4 производятся начальные установки.

В блок 3 задания матрицы смежности заносят информацию о топологии графа.

На вход 6 пуска устройства подают импульсный сигнал уровня логической .единицы. При этом блок 1 синхронизации формирует последовательность сигнаЛов предусмотренную его временной диаграммой. Сигнал уровня логической единицы появляется на первом выходе 7 и первом выходе 10 блока 1 синхронизации. При этом в блоке 2 определения класса раскраски производится подготовка к определению состава вершин

70 4 очередного класса. Через время доста) точное для подготовки схем блока 2, блок 1 синхронизации снимает сигнал с выхода 7 и формирует импульсный сигнал уровня логической единицы на выходе 8. При этом блок 2 определяет класс раскраски вершин, принадлежащих очередному классу. Через время, достаточное для определения всех вершин класса, блок 1 синхронизации формирует импульсный сигнал уровня логической единицы на выходе 9. При этом состав вершин, принадлежащих текущему классу, заносится в блок 4 регистрации. Блок 1 синхронизаций формирует сигнал уровня логической единицы на

I выходе 8 и втором выходе 10.

Работа устройства повторяется до тех пор пока не будут раскрашены все вершины графа. В общем случае для этого может потребоваться от одного до В тактов, где  — количество вершин в графе.

Блок 2 определения класса раскраски работает следующим образом.

По сигналу начальной установки коммутатор 14 замыкает каждую из своих В информационных цепей. По сигналу подготовки накапливающий узел логического сложения обнуляется. По сигналу пуска 13 синхронизации начинает формировать сигналы, предусмотренные временной диаграммой его работы. Сигнал уровня логической единицы появляется на первом выходе (9 узла 13 синхронизации. При этом узел 16 проверки смежности проверяет отсутствие смежности вершин, накопленных на выходе узла 15. Через время, достаточное для проверки, узел 13 синхронизации формирует сигнал уровня логической единицы на своем тактовом выходе 18.

При этом блок 16 выдает значение признака отсутствия смежности на тактовый вход накапливающего узла 17 логического сложения. Если значение признака равно единице (т ° е. вершина, номер которой соответствует номеру возбужденного выхода 19 узла 13, не смежна ни с одной из вершин, которые уже отнесены к текущему классу), узел 15 накапливает (по ИЛИ) код на своем информационном входе (вершина, номер которой соответствует номеру возбужденного выхода I9, добавляется к текущему классу). Одновременно сигналом с выхода узла 17 размыкается до подачи сигнала с входа 5 началь1513470 ной установки соответствующая информационная цепь коммутатора 14. При равенстве нулИ признака отсутствия смежности накопления кода и отключе-.

5 ния информационной цепи коммутатора 14 не происходит. Через время, достаточное для накопления кода, узел 13 синхронизации снимает сигнал со своего тактового выхода 18 и текущего вы- 10 хода 19 и формирует сигнал на следующем по порядку выходе 19. Далее работа устройства повторяется. После того, как будут просмотрены все вершины на предмет их включения в теку- 15 щий класс раскраски, на выходе узла 17 формируется состав вершин текущего класса. При следующем запуске работа блока 2 повторяется, однако все вершины, отнесенные к предыдущим 20 классам исключаются иэ рассмотрения отключением соответствующих их номерам информационных цепей коммутатора 14.

25 изобретения

Формула

1, Устройство для раскраски графов, содержащее блок синхронизации, блок регистрации и блок задания мат- 30 рицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, о т л и ч а ющ е е с я тем, что, с целью повышения быстродействия устройства, в него введен блок определения класса раскраски, причем первый и второй выходы блока синхронизации подключены к входу подготовки и к входу пуска блока определения класса раскраски соответ- 40 ственно, выход признака наличия (К, М) -й ветви блока задания матрицы смежности (К=1, ..., В; М=19 ..., В; где В-количество вершин в графе) подключен к одноименному входу блока 45 определения класса раскраски, выход признака принадлежности М-й вершины составу класса которого подключен к

М-му разряду информационного входа блока регистрации, P-й выход группы 50 блока синхронизации (Р = 1, ..., Т, где Т вЂ” количество классов раскраски) подключен к Р-му разряду адресного входа блока регистрации, входпризнака записи которого подключен к третьему выходу блока синхронизации, вход начальной установки устройства подключен к входам начальной установки блока регистрации и блока определеления класса раскраски.

2.Устройство по п.1, о т л и ч аю щ е е с я тем, что, блок определения класса раскраски содержит узел синхронизации, узел логического сложения, накапливающий узел логического сложения, узел проверки смежности вершин и коммутатор, причем вход пуска блока определения класса раскраски подключен к входу пуска узла синхронизации, М-й выход группы которого подключен к М-му разряду входа первого слагаемого узла логического сложения и к М-му разряду информационного входа накапливающего узла логического сложения, М-й разряд информационного выхода которого является выходом признака принадлежности М-й вершины .составу класса и подключен к

М-му управляющему входу коммутатора и к М-му разряду входа второго слагаемого субблока логического сложения, М-й разряд информационного выхода которого подключен к входу признака соответствия М-й вершины составу опрашиваемых узла проверки смежности вершин, вход признака наличия (К, М)-й ветви которого является одноименным входом блока определения класса вершин, тактовый выход узла синхронизации подключен к входу опроса узла про" верки смежных вершин, выход признака отсутствия смежности которого подключен к тактовому входу накапливающего узла логического смежения, вход ус- тановки в "О" которого является входом подготовки блока определения класса раскраски, вход начальной установки которого подключен к входу включения информационных цепей коммутатора.

1513470

12, 12 fag

Фиг.8

° 4 °

f9

Составитель Г.Смирнова

Редактор Н.Яцола Техред M.Äèäûê Корректор Н.Король

Заказ 6081/49 Тираж 668 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб;, д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101