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

(21)4483628/24

(22)15.09.88

(46) 30.04.91. Бкш. № 16

(71)Таганрогский радиотехнический институт им. В, Д. Калмыкова

(72)В.К. Глушань, И.Г. Ефремов и В,П. Карелин

(53) 681.333(088.8)

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

Р 1283783, кл. G 06 F 15/20, 1985.

Авторское свидетельство СССР Н 1524065, кл„ с 06 F 15/20, 1988.

, . Ч

(54) УСТРОЙСТВО ЛЛЯ РАСКРАСКИ ГРАФИВ (57) Изобретение относится к вычислительной технике и может быть использовано для раскраски вершин графа в заданное число цветов„ Целью изобретения является повышение быстродействия устройства. Устройство содержит блок 1 задания матрицы смежности, блоки 2, 6 сравнения, блок 3 проверки связности вершин, блок 4 синхронизации, блок 5 перечисления множеств, входы и выходы устройства, 1 з.п. ф-лы, 3 ил.

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

Целью изобретения является повышение быстродействия устройства.

На фиг„ 1 представлена Функциональная схема устройства; на фиг, 2 - функциональная схема блока перечисления множеств; на фиг„ 3 - диаграммы.

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

Блок 5 перечисления множеств состоит из узла 10 синхронизации, первого 11 и второго 12 многоканальных счетчиков, коммутатора 13 и регистра 14 сдвига и имеет тактовый вход 15, вход 16 задания максимального значения элемента, вход 17 задания количества шагов возврата, выход IP признака возврата к пустому множеству, выходы 19 значений элементов множества, вход 20 режима работы, выход 21 признака назначения класса элементов и три выхода 22-24 узла 10 синхронизации.

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

Перед началом работы устанавливают в исходное состояние блок 5 перечисления множеств, в блок 1 задания матрицы смежности заносят информацию о топологии графа. Fla вход 7 пуска устройства подают импульсный сигнал уровня 1. При этом блок 4 синхронизации формирует на своем выходе последовательность тактовых импульсов уровня 1. По каждому импульсу на

(Л

э -и

ел

со

10

его тактовом входе блок 5 перечисления множеств формирует на своих выходах комбинацию чисел, соответствующую текущей раскраске вершин грабюв,, , При этом блок 2 сравнивает попарно значения, поступившие на его информационные входы, и при совпадении значений, поступивших, например, на его К-й и М-й информационные входы (, . .„, В; , о.,, В, где В - количество вершин графа), формиует на своем (К,М)-м выходе признака попарного равенства потенциал уровня 1 (это означает, что К-я и М-я вершины имеют 15 одинаковую окраску). Одновременно блок 6 сравнения формирует потенциалы уровня 1 на тех своих выходах, для которых значение информационных сигналов на соответствующем инЛорма- ционном входе не равно нулю (т«е. соответствующая вершина раскрашена). В том случае, если ни одна из вершин, заданная блоком 6, не связана дугами,

20

пульса уровня 1 узел 10 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы (фиг„ 3). Потенциал уровня 1 единицы появляется на выходе 22 узла 10 синхронизации. При этом тот канал счетчиков, на входе разрешения счета которого присутствует потенциал уровня 1, увеличивает значение хранимого в нем кода на единицу, т.е„ текущая вершина (в данном случае первая) окрашивается в текущий цвет Через время, достаточ ное для окончания операции счета, узе 10 снимает потенциал уровня 1 с выхода 22 и формирует потенциал уровня 1 на своих выходах 23 и 24. При этом регистр сдвига при наличии потенциала уровня 1 на входе 20 сдвигает единицу на один разряд вправо, переходя к окраске очередной вершины Далее блок 5 работает аналогично до тех пор, пока на его входе 20 сохраня

заданными блоком 2, на выходе блока 3 25 ется потенциал уровня 1. Если укапроверки связности сохраняется потенциал уровня 1 и устройство работает аналогично. В противном случае (если одинаковую раскраску имеют связные вершины) потенциал уровня 1 снимается с выхода блока 3 и блок 5 изменяет режим Лорнирования комбинаций. Работа устройства продолжается аналогично до тех пор, пока на одном из выходов 8 или 9 устройства не появится потенциал уровня 1. При этом останавливается блок А синхронизации, а информация на выходах значений элементов блока 5 перечисления множеств (при наличии сигнала на выходе ft) соответствует заданной раскраске вершин rpacha.

Блок 5 перечисления множеств работает следующим образом

Перед началом работы по входу 16 задают максимальную емкость каналов счетчика 11 (задают максимально допустимое количество цветов раскраски), по входам 17 - отдельно для каждого канала счетчика 12 его емкость, определяя количество шагов возврата, необходимое для изменения цвета вершины, которая может быть смежна с вершиной, нарушившей окраску, т.е. разность номеров указанных вершин(в крайний левый разряд регистра 14 сдвига устанавливают в 1 , а остальные разряды обнуляют. При поступлении на тактовый вход 15 им0

5

0

пульса уровня 1 узел 10 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы (фиг„ 3). Потенциал уровня 1 единицы появляется на выходе 22 узла 10 синхронизации. При этом тот канал счетчиков, на входе разрешения счета которого присутствует потенциал уровня 1, увеличивает значение хранимого в нем кода на единицу, т.е„ текущая вершина (в данном случае первая) окрашивается в текущий цвет Через время, достаточ ное для окончания операции счета, узел 10 снимает потенциал уровня 1 с выхода 22 и формирует потенциал уровня 1 на своих выходах 23 и 24. При этом регистр сдвига при наличии потенциала уровня 1 на входе 20 сдвигает единицу на один разряд вправо, переходя к окраске очередной вершины Далее блок 5 работает аналогично до тех пор, пока на его входе 20 сохраня5 ется потенциал уровня 1. Если ука0

5

0

5

0

5

занныи потенциал отсутствует, сдвига в регистре 14 не происходит, в очередном цикле работы блока 5 изменяется код того же канала счетчика 11, что и в предыдущем цикле, т,е. окрашивается в следующий по порядку цвет та же вершина, что и в предыдущем цикле. Работа устройства продолжается аналогично, до тех пор, пока на входе 20 не появится потенциал уровня 1, что означает восстановление допустимой раскраски вершин, или до тех пор, пока канал счетчика 11 не переполнится, если исчерпано допустимое количество цветов. При этом на его выходе признака наличия переполнения появляется потенциал уровня 1, который разрешает сдвиг влево регистра 14, причем разрешение сдвига влево обладает большим приоритетом, чем сдвиг вправо Одновременно коммутатор 13 подключает свой информационный вход к второму информационному выходу и на вход разрешения работы одного из каналов счетчика 12 поступает потенциал уровня 1. Теперь при поступлении на тактовый вход регистра 14 импульсов уровня 1 происходит сдвиг информации влевоо При этом устанавливаются в О те каналы счетчика 11, которые соответствуют разрядам регистра 14, через которые проходит сдвигаемая в нем единица, при этом признаки переполнения, формируемые

счетчиком 11, сохраняются Указанные процессы (шаги возврата) осуществляются до тех пор, пока работающий канал счетчика 12 не переполнится. При этом на его выходе признака переполнения появляется импульс уровня 1, которы устанавливает в О все признаки счетчика 11 о При этом коммутатор 13 подключает свой информационный вход на первый информационный выход, разрешая работу одного из каналов счетчика, а регистр 14 переходит в режим сдвига вправо, т.е. осуществляется переход к прямым шагам раскраски„

Указанные процессы продолжаются до тех пор, пока при очередном сдвиге 1 в регистре 14 не переместится в крайний правый разряд, при этом потенциал уровня 1м появляется на выходе 21 блока 5, что является признаком того, что вершины графа раскрашены в заданное количество цветов, или до тех пор, пока не переполнится первый канал счетчика 11, что свидетельствует о невозможности раскраски вершин графа в заданное количество цветов.

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

25

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

выход признака отсутствия связности

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

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

0

5

0

0

0

5

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

Риг./

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

17

Л

234

ч

10

-0- 22

//

19

Ъ

Т

W Фиг. 2

&г.д