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

Авторы патента:

G06F15/173 - с использованием сети связи, например, соединение по схеме матрицы, смешанное соединение, соединение по схеме пирамиды, звезды, снежинки (схемы переключения интерфейсов G06F 13/40)

Изобретение относится к вычислительной технике и может быть использовано при автоматизации разработки печатных плат. В этом случае число красок (классов раскраски) определяет верхнюю границу количества слоев платы, при том, что вершины одного цвета могут быть расположены в одном ее слое. Цель изобретения - повышение быстродействия устройства. Устройство содержит блок 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 °

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

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

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

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

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

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

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

Устройство для моделирования задач о длиннейшем пути в сетях // 1509925

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

Устройство для анализа параметров графа // 1509923

Изобретение относится к вычислительной технике и позволяет определять характеристики связности каждой вершины графа

Матричное вычислительное устройство // 1509920

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

Устройство для исследования параметров графов // 1508229

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

Устройство для моделирования сетей // 1506452

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

Устройство для анализа параметров сети // 1506451

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

Устройство для анализа параметров графа // 1501084

Изобретение относится к вычислительной технике и может быть использовано для исследования достижимости ориентированных графов

Модель дуги сети // 1499372

Изобретение относится к области вычислительной техники и может быть использовано в устройствах для анализа параметров сетей

Устройство маршрутизации сети связи // 1499370

Изобретение относится к вычислительной технике и технике связи и может найти применение при построении узлов коммутации в сетях передачи дискретной информации

Устройство для решения задач на графах // 2100838

Изобретение относится к вычислительной технике и может быть использовано для определения состава и веса критических путей в орграфе без петель

Устройство для исследования параметров графа // 2111533

Изобретение относится к вычислительной технике и может быть использовано для исследования параметров систем, описываемых графами

Устройство для исследования сетей петри // 2126171

Изобретение относится к вычислительной технике и может быть использовано при моделировании посредством сетей Петри

Способ работы узла интерфейса пользователя в соответствии с распределенной многовыходовой системой поискового вызова, способ работы распределенной многовыходовой системы поискового вызова // 2157596

Изобретение относится к системам поискового вызова

Устройство для выбора рациональных решений // 2158955

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

Матричный коммутатор "prosto" // 2160925

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

Модуль коммуникационной сети // 2166793

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

Модуль матричного коммутатора // 2168204

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

Устройство для распознавания ситуаций // 2168207

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

Устройство для распознавания ситуаций // 2168764