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

 

Изобретение относится к области автоматики и вычислительной техники и предназначено для автоматизации решения комбинаторно-графовых задач, в частности задачи раскраски графов в заданное количество цветов. Целью изобретения является повышение быстродействия устройства за счет автоматизации процесса раскраски графа в заданное число цветов. Устройство содержит генератор импульсов , элемент И, двоичные счетчики , схемы сравнения, блок задания исходных данных, группу элементов И, элемент ИДИ-НЕ, два триггера, элемент НЕ. Работа устройства основана на 1 енерации вариантов раскраски вершин графа и проверке требований по раскраске графа в заданное количество цветов. Устройство позволяет автоматизировать процесс раскраски графа, в заданное количество цветов и может найти применение при решении логико-комбинаторных задач в специализированных вычислительных устройствах , а также в качестве аппаратной реализации макрокоманды раскраски неориентированного графа в специализированных процессорах. З Ил. (Л

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

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

РЕСПУБЛИК (so 4 0 06 F 15/20

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3873784/24-24 (22) 27.03.85 (46) 15.01.87. Бюл. ¹ 2 (71) Харьковский авиационный институт им. Н.Е. Жуковского (72) С.А. Губка, В.А. Дергачев, В.А. Балалаев и Ю.С. Нефедов (53) 681.333 (088.8) (56) Авторское свидетельство СССР № 643880, кл. G 06 F 15/20, 1976.

Авторское свидетельство СССР № 877552, кл. 0 06 Р 15/20, )979.

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

¹ 433485, кл. G 06 F 15/20, 1972. (54) УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРАФОВ (57) Изобретение относится к области автоматики и вычислительной техники и предназначено для автоматизации решения комбинаторно-графовых задач, в частности задачи раскраски графов в заданное количество цветов.

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

Устройство содержит генератор импульсов, элемент И, двоичные счетчики, схемы сравнения, блок задания исходных данных, группу элементов И, элемент ИЛИ-НЕ, два триггера, элемент НЕ. Работа устройства основана на . операции вариантов раскраски вершин графа и проверке требований по раскраске графа в заданное количество цветов. Устройство позволяет автоматизировать процесс раскраски графа в заданное количество цветов и может найти применение при решении логико-комбинаторных задач в специализированных вычислительных устройствах, а также в качестве аппаратной реализации макрокоманды раскраски неориентированного графа в специализированных процессорах. 3 ил.

12837

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

f0

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

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

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

8, группу информационных входов 9 устройства, вход 10 сброса устройства, триггер 11, элемент НЕ 12, вход 13 запуска устройства, информационный выход 14 устройства, выход 15 индикации существования раскраски графа в заданное число цветов, триггер 16.

На фиг, 2 обозначены установочный вход 9, вход сброса 10, счетный, вход 17, выход 18 переноса, информационный выход 19,.триггеры со счетным входом 20,-20, элемент ИЛИ 21

40 элементы сравнения 22 — 22 (элеменP ты равнозначности) элемент И 23.

На фиг. 3 обозначены первая 24 и вторая 25 группы входов по р разрядов в каждой, выход 26, элементы

45 сравнения 27, -27Р(элементы равно-. значности), элемейт И 28.

Выходы двоичных счетчиков 3, — Зйй соединены с входами узлов 5 сравнения попарно в лексикографическом порядке. Это означает следующее.

Произвольный граф б (Ч Е) задается множеством вершин Ч V,,× и множеством ребер Б= (е,,е,...,e l где М вЂ” количество вершин, à q количество ребер.

Вершина с номером i, (i=1M ) соответствует -й двоичный счетчик 3;, 83 2 сбрасываюшийся в нулевое состояние при значении, равном заданному количеству цветов К, в которое необходимо раскрасить граф. Значение сигналов на выходах двоичного счетчика

3„ соответствует цвету (коду цвета)

i-й вершины. Произвольный граф с M вершинами одновременно задается матрицей смежности, в которой элемент (i, g) матрицы принимает значение

"1", если существует ребро, соединяющее вершины с номерами i и 3. Матрица смежности неориентированного графа является симметричной относительно диагонали, образованной элементами матрицы вида (i, $ ) (i=1 M) „

Поэтому для задания неориентированного графа достаточно задать только половину матрицы, так как вторая половина будет симметрична. Количество ребер в полном графе с М верши2 нами равно С„. Обозначим значения элементов половины матрицы через

B = (Ъ,,Ге,...Ь,„о и расположим их последов а тельно в яч ейках мат рицы в направлении слева направо и сверху вниз. Ниже приведена матрица смежноссти неориентированного графа с обозначенными элементами матрицы.

1 2 3 4

1», 1, ь„ьм„. °

1 ам-

Ьс2м.!

b, Каждому элементу множества В соответствует некоторое ребро (i J)

Поставим в соответствие каждому ребру некоторое десятичное число Н вида

Н =/мин (i,j)/ /макс (i,J)/. Например, ребру(3,5) соответствует число

35, а ребру (5,4) — число 45. Элементам множества В таким образом поставим в соответствие элементы множества.Н. Элементы множества Н являются лексикографически упорядоченными. В общем виде последовательность соче— таний на множестве элементов (1,2, З,...,И) представлена в лексикогра— фическом поряцке, если она записана в порядке возрастания получающихся чисел.

Значения (В) нодаютоя на выходы соответствующих разрядов блока 6 задания исходных данных (значение Ь на i-й шины).

Количество информационных входов в группе информационных входов устройства, триггеров 20, элементов сравнения 22, количество входов в группах входов 24 и 25 обозначено р и определяется следующим образом: р 11og (К+1) (Граф называется К-раскрашиваемым, если любые две смежные вершины соединенные ребром окрашены в разные цвета. Следовательно, раскраска заданного графа и заданное количество цветов будет найдена, если на- выходах всех элементов И 7 будет сигнал

"0". При этом, на выходе элемента

ИЛИ-НЕ 8 появляется сигнал "1", поступающий на выход 35 устройства (и, следовательно, свидетельствует о зо том что решение найдено) и вход установки в нуль триггера 16, сбрасывая его в состояние "0". При этом закрывается элемент И 2 и сигналы с выхода генератора 1 тактовых импульсов не поступают через элемент

35 И 2 на входы двоичных счетчиков и не меняют их состояние..На информационном выходе результата 14 получаем двоичные слова, соответствующие кодам вершин.

Если в процессе поиска перебраны все варианты, а решение не найдено то на выходе переноса двоичного счетчика 3„ появляется импульс, сбрасывающий триггер 31 в состояние "1", которое поступает на выход 4 устройства (и свидетельствует об отсутст- вии решения) и через элемент НЕ 12 на вход элемента И 2, при этом сигналы с выхода генератора 1 тактовых где К вЂ” число цветов, в которые раскрашивается граф, )...j — означает, что р принимает ближайшее целое положительное значение не меньшее, чем выражение, стоящее в указанных скобках.

Например, для К=З, р=2, для K=5, р=3 и т.д.

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

В исходном состоянии на вход 10 устройства подается сигнал "Сброс".

При этом состояние двоичных счетчиков 3, — 3„ .становится "0...0", триггер 33 устанавливается в состояние

"0", а триггер 16 — вд состояние "1 ".

На вход 13 устройства подается сигнал запуска, включающий генератор 1 тактовых импульсов. Поскольку сигналы на выходах элемента НЕ 12 и триггера 16 равны "1", то импульсы с выхода генератора 1 импульсов поступают на вход элемента И 2, проходят на его выход и поступают на счетный вход двоичного счетчика 3!, меняя его состояние. При достижении двоичным счетчиком 3! состояния, соответствующего десятичному числу К, счетчик сбрасывается в нулевое состояние. При этом, на выходе переноса формируется импульс, изменяющий cостояние следующего за ним двоичного счетчика 3 . Указанный процесс повторяется для всех двоичных счетчиков.

При этом, на выходах двоичных счетчиков формируются двоичные слова, соответствующие кодам цветов вершин. Схемы 5 сравнения производят сравнение цветов смежных вершин для всех возимпульсов не передаются на входы двоичных счетчиков 3 и не меняют их состояние..Формула изобретения

Устройство для раскраски графов, содержащее блок задания исходных. данных, генератор тактовых импульсов, о т л и ч а ю щ е е с я тем, что, 283783 4 можных ребер и формируют сигнал "1" на выходе, если цвета смежных вершин одинаковы. Сигналы с выходов схем 5 сравнения поступают на входы соответствующих элементов И 7. На вторые входы элементов И 7 поступают соответствующие сигналы с выходов блока задания 6 исходных данных. Поскольку в заданном графе некоторые ребра отЯ сутствуют, то информация о цветах вершин, которые не связаны ребрами, исключается из дальнейшего анализа.

Если -е ребро отсутствует, то сигнал на 1 -м разряде блока 6 задания

f5 исходных данных равен "0" и, следовательно, сигнал на выходе элемента И 7 также равен "0".

12837 с целью повып ення быстродействия,за счет автоматизации процесса раскрас— ки графа в заданное число цветов, в него введены группа из M — двоичных счетчиков, группа из С„схем сравнения, группа элементов И, элемент НЕ, элемент ИЛИ вЂ , два триггера, элемент И, причем вход генератора тактовых импульсов является входом запуска устройства, выход генератора !0 тактовых импульсов подключен к первому входу элемента И, второй. вход которого подключен к выходу первого триггера, вход установки в "1" которого объединен с входами сброса дво- 15 ичных счетчиков группы, объединен с входом установки в "0" второго триггера и является входом сброса устройства, выход второго триггера подключен к входу элемента НЕ и явля- .20 ется выходом индикации окончания процесса поиска раскраски графа устройства, выход элемента НЕ подключен к третьему входу элемента И, выход которого подключен к счетному входу первого двоичного счетчика группь1, выход переноса каждого i-ro двоич83 6 ного счетчика группы (где i =1,2, ...,М-1) подключен к счетному входу (i + 1)-ro двоичного счетчика группы, выход переноса M-го двоичного счетчика группы подключен к входу установки в "1" второго триггера, информационные выходы двоичных счетчиков группы подключены к соответ— ствующим входам соответствующих схем сравнения группы и являются группой информационных выходов устройства, выход каждой схемы сравнения групп подключен к первому входу одноименного элемента И группы, второй вход каждого j-ro элемента И группы подключен к j-му разряду блока зада2 ния исходных данных (! =1,2,...,С„,) выход j-го элемента И группы подлючен к )-му входу элемента ИЛИ-НЕ, выход которого подключен к входу установки в "0" первого триггера, и является выходом индикации существования раскраски графа в заданное число цветов устройства, установочные входы счетчиков являются группой информационных входов устройства. 283783

71 фиг. Я

Составитель Т. СапуноваТехред Л.Олейник Корректор С. Черни

Редактор В. Ковтун

Заказ 7443/48

Тираж 670 Подписное

BHHHIIH Государственного комитета СССР по делам изобретений и открытий

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

Произвоцственчо-полит рафическое предприятие, г. Ужгород, ул. Проектная, 4