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

ОЮЗ СОВЕТСНИХ ОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 4 19) (1(51)4 С 06 Р 1 ОСУДАРСТВЕННЫО ИЗОБРЕТЕНИЯМРИ ГКНТ СССР НОМИТЕ ОТНРЫТ САНИЕ ИЗОБРЕТЕ Яф 37адиотехническиймыковаИ.Резниченко тельство СССР15/20, 1972. ельство СССР Р 15/20, 1985 РАСКРАСКИ ГРА 57 в печа крас ет в платцвет ее сл М 4 ь АВТОРСКОМУ С 8 И ТЕЛЬ 1(56), Авторское свидУ 433485, кл, С 06Авторское свидетВ 1283783, кл. С 06(54) УСТРОЙСТВО ДЛЯФОВ Изобретение относится к вычислиной технике и может быть испольно при автоматизации разработки тншх плат. В этом случае число ок (классов раскраски) определяерхнюю границу количества слоевпри том, что вершины одного а могут быть расположены в одном ое. Цель изобретения - повышение быстродействия устройств а. Устройствосодержит блок 1 синхронизации, блок 2определения класса раскраски, блок 3задания матрицы смежности и блок 4 регистрации. Кроме этого, на фиг. 1 цифровые обозначения, имеют вход 5 начальноч установки устройства, вход 6пуска устройства, с первого по третий выходы 7 - 9 блока 1 синхронизации и выходы 10 группы блока 1 синхронизации, выходы 11 признаков наличияветвей графа блока 3 и выходы 12 признаков принадлежности вершин составукласса блока 2 определения классараскраски. После начальной установкиустройства в блок 3 заносят информацию о топологии графа. После подачисигнала на вход 6 пуска блок 1 синхронизации формирует последовательностьсигналов, обеспечивающую определениепри помощи блока 2 состава вершинкаждого классараскраски и регистрацию в блоке 3. 1 з.п.ф-лы, 4 ил.15134 3Изобретние относится к вычислительной технике и может быть использовано при автоматизации разработки печатных плат, в этом случае число красокопределяет верхнюю границу количества слоев платы при том, что вершиныодного цвета могут быть расположены водном ее слое.Цель изобретения - повышение быстродействия устройства.На фиг, 1 представлена функциональная схема устройства; на фиг. 2 - временная диаграма работы блока синхронизации; на фиг. 3 - функциональнаясхема блока определения класса раскраски; на фиг. 4 - функциональнаясхема узла синхронизации,Устройство содержит блок 1 синхронизации, блок 2 определения класса раскраски, блок 3 задания матрицысмежности и блок 4 регистрации. Кроме того, устройство имеет вход 5 начальной установки устройства, вход 6пуска устройства, с первого по третий 25выходы 7 - 9 блока 1 синхронизации ивыходы 10 группы блока 1 синхрониза-:.ции, выходы 11 признаков наличия ветвей графа блока 3 и выходы 12 признаков принадлежности вершин составу 30класса блока 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 синхронизаций формируетсигнал уровня логической единицы навыходе 8 и втором выходе 10,Работа устройства повторяется дотех пор пока не будут раскрашены всевершины графа. В общем случае дляэтого может потребоваться от одногодо В тактов, где В - количество вершин в графе.Блок 2 определения класса раскраски работает следующим образом.По сигналу начальной установкикоммутатор 14 замыкает каждую из своих В информационных цепей. По сигналу подготовки накапливающий узел логического сложения обнуляется. По сигналу пуска 13 синхронизации начинаетформировать сигналы, предусмотренныевременной диаграммой его работы. Сигнал уровня логической единицы появляется на первом выходе 9 узла 13 синхронизации, При этом узел 16 проверкисмежности проверяет отсутствие смежности вершин, накопленных на выходеузла 15. Через время, достаточноедля проверки, узел 13 синхронизацииформирует сигнал уровня логическойединицы на своем тактовом выходе 18,При этом блок 16 выдает значение признака отсутствия смежности на тактовый вход накапливающего узла 17 логического сложения. Если значениепризнака равно единице (те, вершина,номер которой соответствует номерувозбужденного выхода 19 узла 13, несмежна ни с одной из вершин, которыеуже отнесены к текущему классу),узел 15 накапливает (по ИЛИ) код насвоем информационном входе (вершина,номер которой соответствует номерувозбужденного выхода 19, добавляетсяк текущему классу). Одновременно сигналом с выхода узла 17 размыкаетсядо подачи сигнала с входа 5 начальной установки соответствующая информационная цепь коммутатора 14. При равенстве нулИ признака отсутствия смежности накопления кода и отключе-.5 ния информационной цепи коммутатора 14 не происходит. Через время, достаточное для накопления кода, узел 13 синхронизации снимает сигнал со своего тактового выхода 18 и текущего вы хода 19 и формирует сигнал на следующем по порядку выходе 19. Далее работа устройства повторяется, После того, как будут просмотрены все вершины на предмет их включения в теку щий класс раскраски, на выходе узла 17 формируется состав вершин текущего класса, При следующем запуске работа блока 2 повторяется, однако все вершины, отнесенные к предыдущим 20 классам исключаются иэ рассмотрения отключением соответствующих их номерам информационных цепей коммутатора 14. 25изобретения Формула 1, Устройство для раскраски графов, содержащее блок синхронизации, блок регистрации и блок задания мат рицы смежности, причем вход пуска устройства подключен к входу пуска блока синхронизации, о т л и ч а ющ е е с я тем, что, с целью повьппения быстродействия устройства, в него введен блок определения класса раскраски, причем первый и второйвыходы блока синхронизации подключены к входу подготовки и к входу пуска блока определения класса раскраски соответ ственно,выход признака наличия (К,М)-й ветви блока задания матрицы смежности (К = 1, , В; М = 1, , В;где В-количество вершин в графе) подключен к одноименному входу блока 5 определения класса раскраски, выход признака принадлежности М-й вершины составу класса которого подключен к М-му разряду информационного входа блока регистрации, Р-й выход группы 50 блока синхронизации (Р = 1, , Т, где Т - количество классов раскраски) подключен к Р-му разряду адресного входа блока регистрации, входпризнака записи которого подключен к третьему выходу блока синхронизации, вход начальной установки устройства подключен к входам начальной установки блока регистрации и блока определеления класса раскраски.2,Устройство по п.1, о т л и ч аю щ е е с я тем, что, блок определения класса раскраски содержит узел синхронизации, узел логического сложения, накапливающий узел логического сложения, узел проверки смежности вершин и коммутатор, причем вход пуска блока определения класса раскраски подключен к входу пуска узла синхронизации, М-й выход группы которого подключен к М-му разряду входа первого слагаемого узла логического сложения и к М-му разряду информационного входа накапливающего узла логического сложения, М-й разряд информационного выхода которого является выходом признака принадлежности М-й вершины составу класса и подключен к М-му управляющему входу коммутатора и к М-му разряду входа второго слагаемого субблока логического сложения, М-й разряд информационного выхода которого подключен к входу признака соответствия М-й вершины составу опрашиваемых узла проверки смежности вершин, вход признака наличия (К, М)-й ветви которого является одноименным 1входом блока определения класса вершин, тактовый выход узла синхронизации подключен к входу опроса узла про" верки смежных вершин, выход признака отсутствия смежности которого подключен к тактовому входу накапливающего узла логического смежения, вход ус- тановки в "О" которого является входом подготовки блока определения класса раскраски, вход начальной установки которого подключен к входу включения информационных цепей коммутатора.1513470 остав ь Г,Смирно Редакто ь Яцола Техре Дидык ектор Заказ 6081/49 Тираж 668ВНИИПИ Государственного комитета и113035, Москва, ЖПодписноо изобретениям и о35, Раушская наб;,ГКНТ ССС ытия роизводственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101