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

 

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

А) СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (l9) (11) 151) 4 G 06 F 15/20

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

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

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

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

ПРИ ГКНТ СССР

1 (21) 4400172/24-24 (22) 29.03 ° 88 (46) 23.11 89. Бюл. ¹ 43 (71) Таганрогский радиотехнический институт им,В.Д.Калмыкова (72) В. М. Глушань и В.П. Карелин (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 433485, кл, G 06 F 15/20, 1 972.

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

1283783, кл, G 06 Г 15/20, 1985. (54} УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач автоматизированной разработки печатных плат радиоэлектронной аппаратуры, где задача раскраски интерпретируется как задача определения количества слоев печатной платы и размещения элементов аппаратуры в каждом слое. Целью изобретения является повышение быстро— действия устройства за счет исключения заведомо непригодных комбинаций раскраски вершин графа. Устройство содержит блок l синхронизации, блок

2 формирования комбинаций, элемент

ИЛИ 3, блок 4 сравнения раскраски вершин, блок 5 задания матрицы смежности и блок 6 определения пересечения частей графа, кроме того,оно имеет вход 7 пуска устройства, вход 8 задания наибольшего числа в комбинации устройства, выход 9 признака от— сутствия решения, выход 10 признака решения задачи и выходы 1! цветов вершин графа. После подачи на вход 7 пуска устройства сигнала уровня логической единицы блок 1 начинает вь;— рабатывать тактовые импульсы, по которым блок 2 формирует комбинации чисел, т.е ° комбинации цветов вершин.

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

1524065

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

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

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

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

В счетчиков 13, где  — количество вершин в графе, элемент И 14, элемент

ИЛИ 15, и элемент 16 задержки. Кро— ме того, на фиг.2 обозначены входы и выходы блока 2 формирования комбинаций: вход 17 режима работы, вход 18 задания наибольшего числа в комбинации, выход 19 признака окончания работы, выход 20 признака завершения перебора комбинаций, выходы 21 значения чисел в комбинации и тактовый вход 22, Устройство работает следующим образом

Пусть необходимо решить задачу раскраски вершин графа в заданное количество цветов. Перед началом

50 работы в блок 5 заносят информацию о топологии графа, устанавливают в исходное состояние блок 2 формирования комбинаций (цепи начальной установки на фиг.1 не показаны) и по входу 8 задают количество цветов, которые можно использовать для раскраски вершин графа.

На вход пуска устройства подают импульсный сигнал уровня логической единицы, при этом блок 1 начинает формирование импульсов уровня логической единицы на своем тактовом выходе. По каждому из этих импульсов блок 2 формирует новую комбинацию чисел (т ° е. фактически новую раскрасо ку вершин графа) в соответствии с алгоритмом, обусловленным его конструкцией. Блок 4 для каждой комбинации цветов определяет вершины, раскрашенные в один цвет (если вершины не были раскрашены, т.е ° если на соответствующих им выходах 11 нули, то соответствие цветов не фиксируется) а блок 6 устанавливает наличие смежных вершин среди раскрашенных в один цвет. Если таких вершин нет, на вхо— де режима работы блока 2 сохраняется потенциал уровня логической единицы и блок 2 раскрашивает все последующие вершины в один цвет.

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

2 не сформирует импульсный сигнал на выходе 9, что свидетельствует о полном переборе всех возможных комбинаций раскраски вершин графа в заданное количество цветов. В любом случае блок 1 синхронизации будет остановлен °

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

Перед началом работы обнуляют все счетчики 13 группы, в младший разряд регистра 12 сдвига заносят единицу, остальные разряды обнуляют, по входу 18 задают коэффициенты пересчета всех счетчиков 1 3. При подаче на вход 22 тактовых импульсов один из счетчиков 13, на вход разрешения счета которого подан потенциал уровня логической единицы с выхода соответствующего разряда регистра 12 сдвига, начинает счет импульсов.

Причем при наличии на входе 17 потенциала уровня логической единицы единица в регистре 12 сдвига смещается в сторону старших разрядов, чем обеспечивается одинаковая вершина с последовательно во3pacтающими,номерами. Если потенциал уровня логической

15240 единицы на входе 17 отсутствует (т, е. если в один цвет раскрашены смежные вершины графа) сдвиг единицы вправо в сторону старших разрядов прекраща5 ется и счетчик 13, соответствующий вершине, нарушившей требования к раскраске, увеличивает свое содержимое на единицу (тем самым изменяется краска данной вершины). Если правиль- 10 ность раскраски от этого восстановится, в том же такте единица в ре— гистре 12 сдвинется на разряд вправо. В противном случае счетчик 13 снова увеличит свое содержимое на 1 единицу и т,д, до тех пор, пока либо не устранится нарушение раскраски вершин, либо счетчик 13 не переполнится. В этом случае единица в регистре 12 сдвинется в сторону млад- 20 ших разрядов. Работа устройства продолжается до тех пор, пока либо на выходе признака переноса вправо не появится сигнал, что будет свидетельствовать о том, что правильно 25 раскрашены все вершины), либо на выходе признака переноса влево из младших разрядов также не появится сигнал (что будет свидетельствовать о том что все возможные комбинации 30 раскраски вершин опробованы и решения при данном количестве цветов не существует).

Формула изобретения

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

65 6

М-й раскрашенных вершин графа подключен к входу признака наличия (K,."I)-ro ребра во второй части графа блока определения пересечения частей графа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства за счет исключения перебора заведомо непригодных комбинаций раскраски вершин графа, в него введен элемент ИЛИ, причем вы— ход признака отсутствия пересечений блока определения пересечения частей графа подключен к входу режима работы блока формирования комбинаций, вьг ход признака завершения перебора комбинаций которого является выходом признака отсутствия решения устройства и подключен к первому входу элемента KIH, вход задания количества цветов устройства подключен к входу задания наибольшего числа в комбинации блока формирования комбинаций, выход признака окончания работы которого является выходом признака решения задачи устройства и подключен к второму входу элемента

ИЛИ, выход которого подключен к входу останова блока синхронизации.

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

K-го счетчика группы, выход признака переполнения которого подключен к

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

Составитель А.Мишин

Редактор А.Шандор Техред М.Ходанич Корректор Т,Палий

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

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 наций подключен к входам задания ко— эффициента пересчета всех счетчиков группы, информационный выход К-го из которых является выходом значения

К-го числа в комбинации блока формирования комбинаций.