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

) 4 0 06 1 15/2 ОСУДАРСТВЕННЫЙ КОМИТЕТО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯРИ ГКНТ СССР ОПИСАНИЕ ИЭОБРЕТЕНИ ВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Таганрогский радиотехнический институт им,В.Д.Калмыкова(56) Авторское свидетельство СССР Мф 433485, кл, С 06 Р 15/20, 1 972.Авторское свидетельство СССР В 1283783, кл, 0 06 Г 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для решения задач автоматизированной разработки печатных плат радиоэлектронной аппаратуры, где задача раскраски интерпретируется как задача определения количества слоев печатной платы и размещения элементов аппаратуры в каждом слое, Целью изобретения является повышение быстро - действия устройства за счет исключения заведомо непригодных комбинаций раскраски вершин графа. Устройствосодержит блок 1 синхронизации, блок2 формирования комбинаций, элементИЛИ 3, блок 4 сравнения раскраскивершин, блок 5 задания матрицы смежности и блок 6 определения пересечения частей графа, кроме того,оно имеет вход 7 пуска устройства, вход 8задания наибольшего числа в комбинации устройства, выход 9 признака от -сутствия решения, выход О признакарешения задачи и выходы 1 цветоввершин графа. После подачи на вход 7пуска устройства сигнала уровня логической единицы блок 1 начинает вьюрабатывать тактовые импульсы, по которым блок 2 формирует комбинации чисел, т.екомбинации цветов вершин.В том случае, если в одинаковый цветоказываются раскрашены смежные вершины, на выходе блока 6 исчезает по -тенциал уровня логической единицы иблок 2 изменяет алгоритм формирования комбинаций. 1 з.п.ф-лы, 2 ил.Изобретение относится к вычислительной техн ке и может быть исполь. зовано для решения задач автоматизированной разработки печатных платрадиоэлектронной аппаратуры, гдезадача раскраски интерпретируетсякак задача определения количестваслеов печатной платы и размещенияэлементов аппаратуры в каждом слое.Целью изобретения является повышение быстродействия устройства засчет исключения перебора заведомонепригодных комбинаций раскраски вершин графа.15На фиг.1 представлена функциональная схема устройства; на фиг.2функциональная схема блока формирования комбинаций,Устройство содержит блок 1 синхронизации, блок 2 формирования комбина -ций, элемент ИЛИ 3, блок 4 сравненияраскраски вершин, блок 5 задания матрицы смежности и блок 6 определенияпересечений частей графа, Кроме того, на фиг.1 обозначены вход 7 пуска устройства, вход 8 задания наибольшего числа в комбинации устройства,выход 9 признака отсутствия решенияустройства, выход 10 признака решениязадачи устройства и выходы 11 цветоввершин графа устройства,Блок 2 формирования комбинаций содержит регистр 12 сдвига, группу изВ счетчиков 13, где В - количествовершин в графе, элемент И 14, элемент35ИЛИ 15, и элемент 16 задержки. Кро -ме того, на фиг.2 обозначены входы ивыходы блока 2 формирования комбинаций: вход 17 режима работы, вход 18задания наибольшего числа в комбинации, выход 19 признака окончанияработы, выход 20 признака завершенияперебора комбинаций, выходы 21 значения чисел в комбинации и тактовыйвход 22,Устройство работает следующим образомПусть необходимо решить задачураскраски вершин графа в заданноеколичество цветов. Перед началом50работы в блок 5 заносят информациюо топологии графа, устанавливают висходное состояние блок 2 формирования комбинаций (цепи начальной установки на фиг.1 не показаны) и по 55входу 8 задают количество цветов, которые можно использовать для раскраски вершин графа. На вход пуска устройства подают импульсный сигнал уровня логической единицы, при этом блок 1 начинает формирование импульсов уровня логической единицы на своем тактовом выходе. По каждому из этих импульсов блок 2 формирует новую комбинацию чисел (т,е. фактически новую раскрасо ку вершин графа) в соответствии с алгоритмом, обусловленным его конструкцией. Блок 4 для каждой комбинации цветов определяет вершины, раскрашенные в один цвет (если вершины не были раскрашены, т.еесли на соответствующих им выходах 11 нули, то соответствие цветов не фиксируется) а блок 6 устанавливает наличие смежных вершин среди раскрашенных в один цвет. Если таких вершин нет, на вхо - де режима работы блока 2 сохраняется потенциал уровня логической единицы и блок 2 раскрашивает все последующие вершины в один цвет.В противном случае потенциал уровня логической единицы снимается с входа режима работы и блок 2 изменяет алгоритм раскраски вершин. Работа устройства продолжается до тех пор, пока не будет найдено решение, при этом появится импульсный сигнал на выходе 10 или до тех пор, пока блок 2 не сформирует импульсный сигнал на выходе 9, что свидетельствует о полном переборе всех возможных комбинаций раскраски вершин графа в заданное количество цветов. В любом случае блок 1 синхронизации будет остановлен.Блок 2 формирования комбинаций работает следующим образом.Перед началом работы обнуляют все счетчики 13 группы, в младший разряд регистра 12 сдвига заносят единицу, остальные разряды обнуляют, по входу 18 задают коэффициенты пересчета всех счетчиков 1 3. При подаче на вход 22 тактовых импульсов один из счетчиков 13, на вход разрешения счета которого подан потенциал уровня логической единицы с выхода соответствующего разряда регистра 12 сдвига, начинает счет импульсов. Причем при наличии на входе 17 потенциала уровня логической единицы единица в регистре 12 сдвига смещается в сторону старших разрядов, чем обеспечивается одинаковая вершина с последовательно возрастающими, номерами. Если потенциал уровня логической15240 единицы на входе 17 отсутствует (т,е, если в один цвет раскрашены смежные вершины графа) сдвиг единицы вправо в сторону старших разрядов прекраща 5 ется и счетчик 13, соответствующий вершине, нарушившей требования краскраске, увеличивает свое содержимое на единицу (тем самым изменяется краска данной вершины). Если правиль ность раскраски от этого восстановится, в том же такте единица в ре - гистре 12 сдвинется на разряд вправо. В противном случае счетчик 13 снова увеличит свое содержимое на 15 единицу и т,д, до тех пор, пока либо не устранится нарушение раскраски вершин, либо счетчик 13 не переполнится. В этом случае единица в регистре 12 сдвинется в сторону млад ших разрядов. Работа устройства продолжается до тех пор, пока либо на выходе признака переноса вправо не появится сигнал, что будет свидетельствовать о том, что правильно 25 раскрашены все вершины), либо на выходе признака переноса влево из младших разрядов также не появится сигнал (что будет свидетельствовать о том что все возможные комбинации 30 раскраски вершин опробованы и решения при данном количестве цветов не существует). Формула изобретения 1. Устройство для раскраски гра - фов, содержащее блок синхронизации, блок формирования комбинаций, блок сравнения раскраски вершин, блок определения пересечения частей графа и блок задания матрицы смежности, выход признака наличия (К,М)-го ребра которого (К = 1В; М = 1Б, где В - количество вершин в графе) 45 подключен к входу признака наличия (К,М)-го ребра в первой части графа блока определения пересечениячастей графа, вход пуска устройства подключен к входу пуска блока синхронизации, тактовый выход которого подключен к тактовому входу блока формирования комбинаций, выход значения К-го числа в комбинации которого является выходом цвета К-й вершины устройства и подключен к входу за - дания цвета К-й вершины графа блока сравнения цвета вершин графа, вьг ход признака совпадения цвета К-й и 65 6М-й раскрашенных вершин графа подключен к входу признака наличия(К,М)-го ребра во второй части графа блока определения пересечения частей графа, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства за счет исключения перебора заведомо непригодных комбинаций раскраски вершин графа, в него введен элемент ИЛИ, причем вы - ход признака отсутствия пересечений блока определения пересечения частей графа подключен к входу режима работы блока формирования комбинаций, вьг ход признака завершения перебора комбинаций которого является выходом признака отсутствия решения устройства и подключен к первому входу элемента ВИ, вход задания количества цветов устройства подключен к входу задания наибольшего числа в комбинации блока формирования комбинаций, выход признака окончания работы которого является выходом признака решения задачи устройства и подключен к второму входу элемента ИЛИ, выход которого подключен к входу останова блока синхронизации.2, Устройство по по п,1, о т л ич а ю щ е е с я тем, что блок формирования комбинации содержит регистр сдвига, элемент И, элемент задержки, элемент ИЛИ и группу из Ь счетчиков, причем тактовый вход бло - ка формирования комбинаций подключен к суммирующим входам всех счетчиков и к входу элемента задержки, выход которого подключен к первому входу элемента И, вход режима работы блока формирования комбинаций подключен к второму входу элемента И, выход которого подключен к входу признака сдвига вправо регистра сдвига, К-й разряд информационного выхода которого подключен к входу разрешения счета К-го счетчика группы, выход признака переполнения которого подключен к К-му входу элемента ИЛИ, выход которого подключен к входу признака сдвига влево регистра сдвига, выходы признака переноса вправо из старшего разряда и признака переноса влево из младшего разряда являются выходами признака окончания работы и признака завершения перебора комбинаций блока формирования комбинаций соответственно, вход задания наибольшего числа в комбинации блока формирования комбиЗаказ 7045/51 Тираж 668 ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101 наций подключен к входам задания ко -эффициента пересчета всех счетчиковгруппы, информационный выход К-го из которых является выходом значенияК-го числа в комбинации блока формирования комбинаций,