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

 

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

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

РЕСПУБЛИК (19>, 01) (51) 5 C 06 F 15/419

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

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

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

ПРИ ГКНТ СССР

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4483628/24 (22) 15.09.88 (46) 30.04.91. Бюл, Р 16 (71) Таганрогский радиотехнический институт им. В,Д. Калмыкова (72) R.Ì. Глушань, И.Г, Ебремов и В.П. Карелин (53) 681.333(088.Я) (56) Авторское свидетельство СССР

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

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

Р 1524065, кл. Г 06 F 15/20, 1988.

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

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

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

Блок 5 перечисления множеств состоит из узла 10 синхронизации, первого

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

1 э и ф лыр 3 ил чиков, коммутатора 13 и регистра 1ч сдвига и имеет тактовый вход 15, вход С„

16 задания максимального значения элемента, вход 17 задания количества шагов возврата, выход 18 признака виаиь возврата к пустому множеству, вьмоды

19 значений элементов множества, вам вход 20 режима работы, выход 21 признака назначения класса элементов и три выхода 22-24 узла 10 синхронизации т

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

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

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

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

К-й и М-й информационные входы (К=1, Ц; И=1. . ., В, где  — количество вершин графа), формиует на своем (К,М)-м выходе признака попарного равенства потенциал уровня " 1" (это означает, что К-я и P-я вершины имеют 15 одинаковую окраску). Одновременно блок 6 сравнения формирует потенциалы уровня " 1" на тех своих выходах, для которых значение информационных сигналов на соответствующем информационном входе не равно нулю (т.е. соответствующая вершина раскрашена). В том случае, если ни одна из вершин, заданная блоком 6, не связана дугами, заданными блоком 2, на выходе блока 3 25 проверки связности сохраняется потенциал уровня "1" и устройство работает аналогично. В противном случае (если одинаковую раскраску имеют связные вершины) потенциал уровня "1" снимается с выхода блока 3 и блок 5 изменяет режим формирования комбинаций. Работа устройства продолжается аналогично до тех пор, пока на одном из выходов 8 или 9 устройства не появится потенциал уровня "1". При 5 этом останавливается блок 4 синхронизации, а информация на выходах значений элементов блока 5 перечисления множеств (при наличии сигнала на выходе 8) соответствует заданной

40 раскраске вершин rpaAa.

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

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

При этом тот канал счетчиков, на входе разрешения счета которого присутствует потенциал уровня " 1", увеличивает значение хранимого в нем кода на единицу, т.е. текущая вершина (в данном случае первая) окрашивается в текущий цвет. Через время, достаточное для окончания операции счета, узел

10 снимает потенциал уровня "1" с выхода 22 и формирует потенциал уровня

"1" на своих выходах 23 и 24. При этом регистр сдвига при наличии потенциала уровня "1" на входе 20 сдвигает единицу на один разряд вправо, переходя к окраске очередной вершины.

Далее блок 5 работает аналогично до тех пор, пока на его входе 20 сохраняется потенциал уровня "1", Если указанный потенциал отсутствует, сдвига в регистре 14 не происходит, в очередном цикле работы блока 5 изменяется код того же канала счетчика 11, что и в предыдущем цикле, т.е. окрашивается в следующий по порядку цвет та же вершина, что и в предыдущем цикле.

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

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

5 появляется импульс уровня " 1", который устанавливает в " 0" все признаки счетчика 11. При этом коммутатор 13 подключает свой информационный вход íà 1ð первый информационный выход, разрешая работу одного из каналов счетчика, а регистр 14 переходит в режим сдвига вправо, т.е. осуществляется переход к прямым шагам раскраски. 15

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

35 первого многоканального счетчика, выход признака переполнения первого канала которого является выходом признака возврата к пустому множеству

40 блока перечисления множеств вход задания количества шагов возврата при формировании К-го элемента которого подключен к входу загрузки К-ro канала второго многоканального счетчика, второй вькод узла синхронизации подключен к суммирующему входу второго многоканального счетчика, выход признака переполнения которого подключен к входу установки в "0" признаков первого многоканального счетчика, выход признака наличия переполнения которого подключен к входу разрешения сдвига влево регистра сдвига и к управляющему входу

55 коммутатора, K-A Разряд nepsoro информационного выхода которого под ключен к входу разрешения работы

К-го канала первого многоканального счетчика, вькод признака перепапне1. Устройство для раскраски графов, содержащее блок задания матрицы смежно ти, первый блок сравнения, блок синхронизации и блок перечисления множест}, причем вход пуска устройства подключен к входу пуска блока cHHxpG низации, выход которого подключен к тактовому входу блока перечисления множеств, выход признака назначения класса элементов которого является выходом признака окончания работы устройства и подключен к первому входу останова блока синхронизации, выход признака возврата к пустому множеству блока перечисления множеств является вькодом признака отсутствия раскраски устройства и подключен к второму входу останова блока синхронизации, выход значения К-го элемента блока перечисления множеств (К = 1,..., В, где  — количество вершин в графе) подключен к К-му информационному входу первого блока сравнения, о т л и— ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены блок проверки связности вершин и второй блок сравнения, причем вькод признака наличия (К,,И)-f» формула изобретения

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

1645970

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

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

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

Техред Л.Олийнык

Корректор Н.Король

Редактор Л. Пчолннская

Заказ 1351 Тираж 415 Подписное

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

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

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