Устройство для раскраски графов Советский патент 1989 года по МПК G06F15/173 

8

Фи5.1

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

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

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

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

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

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

5

0

5

0

5

0

5

0

5

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

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

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

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

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

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

1 . Устройство для раскраски гра - фов, содержащее блок синхронизации, блок формирования комбинаций, блок

0

5

5

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

2, Устройство по по п.I, о т л и- чающееся тем, что блок формирования комбинации содержит регистр сдвига, элемент И, элемент задержки, элемент ИЛИ и группу из В счетчиков, причем тактовьй вход блока формирования комбинаций подключен к суммирующим входам всех счетчиков и к входу элемента задержки, вькод которого подключен к первому входу

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

сравнения раскраски вершин, блок опре-до элемента И, вход режима работы блока

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

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

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

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

Составитель А.Мишин Редактор А.Шандор Техред М.Ходанич

Заказ 7045/51

Тираж 668

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/3

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

которых является выходом значения К-го числа в комбинации блока формирования комбинаций.

211

Фиг. г

Корректор Т.Палий

Подписное