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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) 1 И) 5/419 1)5 Со ТЕНИ ГОСУДАРСТВЕННЫИ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ИСАНИЕ ИЗОБР А ВТОРСНОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРР 1283783, кл . С 06 Р 15/20, 1985.Авторское свидетельство СССРР 1524065, кл. Г 06 Р 15/20, 1988,Изобретение относится .к вычислительной технике и может быть использовано для раскраски вершин графа в заданное число цветов.Целью изобретения является повышение быстродействия устройства.На фиг, 1 представлена бункциональная схема устройства; на фиг. 2 - функциональная схема блока перечисления множеств; на фиг. 3 - диаграммы,Устройство содержит блок 1 задания матрицы смежности, первый блок 2 сравнения, блок 3 проверки связности вершин, блок 4 синхронизации, блок 5 перечисления множеств, блок 6 сравнения, вход 7 пуска устройства, выход 8 признака окончания работы устройства и вьмод 9 признака отсутствия раскраски устройства.Блок 5 перечисления множеств состоит из узла 10 синхронизации, первого 11 и второго 12 иногоканальнык счет, /(57) Изобретение относится к вычислительной технике и может быть использовано для раскраски вершин графав заданное число цветов, Целью изоб"ретения является повышение быстродействия устройства Устройство содержит блок 1 задания матрицы смежности, блоки 2, 6 сравнения, блок 3проверки связности вершин, блок 4синхронизации, блок 5 перечисленилмножеств, входы и выходы устройства,1 эп,флы, Зил,чиков, коммутатора 13 и регистра 14 сдвига и имеет тактовый вход 15, вхо 16 задания максимального значения элемента, вход 17 эарания количества шагов возврата, выход 18 признака возврата к пустому множеству, вьмоды 19 значений элементов множества, вход 20 режима работы, выход 21 признака назначения класса элементов и три выхода 22-24 узла 10 синхронизации тУстройство работает следу)оп 1 ии образом. Перед началом работы устанавливают в исходное состояние блок 5 перечисления множеств, в блок 1 задания матрицы смежности заносят инбормацию о топологии графа. На вход 7 пуска устройства подают импульсный сигнал уровня "1". При этом блок 4 синхронизации формирует на своем выходе последовательность тактовых импульсов уровня "1". По каждому импульсу наего тактовом входе блок 5 перечисления множеств формирует на своих выходах комбинацию чисел, соответствующую текущей раскраске вершин графов. При этом блок 2 сравнивает попарно значения, поступившие на его информационные входы, и при совпадении значений, поступивших, например, на его К-й и М-й информационные входы (К=1,Ц; И=1. . ., В, где В - количество вершин граФа), формиует на своем (К,М)-м выходе признака попарного равенства потенциал уровня " 1" (это означает, что К-я и 1 ф-я вершины имеют 15 одинаковую окраску). Одновременно блок 6 сравнения формирует потенциалы уровня "1" на тех своих выходах, для которых значение информационных сигналов на соответствующем информационном входе не равно нулю (т.е. соответствующая вершина раскрашена). В том случае, если ни одна из вершин, заданная блоком 6, не связана дугами, заданными блоком 2, на выходе блока 3 25 проверки связности сохраняется потенциал уровня "1" и устройство работает аналогично. В противном случае (если одинаковую раскраску имеют связные вершины) потенциал уровня "1"снимается с выхода блока 3 и блок 5 изменяет режим формирования комбинаций, Работа устройства продолжается аналогично до тех пор, пока на одном из выходов 8 или 9 устройства не появится потенциал уровня "1". При 35 этом останавливается блок 4 синхронизации, а информация на выходах значений элементов блока 5 перечисления множеств (при наличии сигнала на выходе 8) соответствует заданной40 раскраске вершин графа.Блок 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 под"ключает свой информационный вход напервый информационный выход, разрешаяработу одного из каналов счетчика,а регистр 14 переходит в режим сдвига вправо, т.е. осуществляется переход к прямым шагам раскраски. 15Указанные процессы продолжаются дотех пор, пока при очередном сдвигев регистре 14 не переместится вкрайний правый разряд, при этом потенциал уровня "1" появляется на выходе 21 блока 5, что является признаком того, что вершины графа раскрашены в заданное количество цветов, илидо тех пор, пока не переполнится первый канал счетчика 11, что свидетельствует о невозможности раскраски вершин графа в заданное количество цветов,2, Устройство по п, 1, о т л и -ч а ю щ е е с я тем, что блок перечисления множеств содержит два многоканальных счетчика, узел синхронизации, коммутатор и регистр сдвига, причем тактовый вход блока перечислениямножеств подключен к входу пуска узласинхронизации, первый выход которогоподключен к суммирующему входу первого многоканального счетчика, инЗ 0 формационный выход К-го канала которого является выходом значения К-гоэлемента блока перечисления множеств,вход задания максимального значенияэлемента которого подключен к входузадания максимальной емкости каналов 35первого многоканального счетчика, выход признака переполнения первого канала которого является выходом признака возврата к пустому множеству 40 блока перечисления множеств, входзадания количества шагов возвратапри формировании К-го элемента которого подключен к входу загрузки К-гоканала второго многоканального счетчика, второй вькод узла синхронизации подключен к суммирующему входувторого многоканального счетчика,вькод признака переполнения которогоподключен к входу установки в "0"признаков первого многоканальногосчетчика, выход признака наличияпереполнения которого подключен квходу разрешения сдвига влево регистра сдвига и к управляющему входукоммутатора, К-й разряд первогоинформационного выхода которого подключен к входу разрешения работыК-го канала первого многоканальногосчетчика, вькод признака перепопнеФормула изобретения 1. Устройство для раскраски графов, содержащее блок задания матрицы смежно ти, первый блок сравнения, блок синхронизации и блок перечисления множестпричем вход пуска устройства подключен к входу пуска блока синхронизации, выход которого подключен к тактовому входу блока перечисления множеств, выход признака назначения класса элементов которого является выходом признака окончания работы устройства и подключен к первому входу останова блока синхронизации, выход признака возврата к пустому множеству блока перечисления множеств является вькодом признака отсутствия раскраски устройства и подключен к второму входу останова блока синхронизации, выход значения К-го элемента блока перечисления множеств (К = 1 В, где В - количество вершин в грайе) подключен к К-му информационному входу первого блока сравнения, о т л и - ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства, в него введены блок проверки связности вершин и второй блок сравнения, причем выход признака наличия (КИ)-й 706дуги блока задания матрицу смежности (М 1 В) подключен к одноименному входу блока проверки связности зерцс:н, (К, М)-й выход признака попарного равенства чисел входных информационных направлений первого блока сравнения подключен к входу опроса (К, М) .Л дуги блока проверки связности вершин, выход признака отсутствия связности которого подключен к входу режима работы блока перечисления множеств, выход значения К-го элемента которого подключен к К"му информационному входу второго блока сравнения, К-й выход признака неравенства нулю которого подключен к входу опроса К-й вершины блока проверки связности вершин, 1645970ния К-го канала которого подключен к входу разрешения работы К-го канала второго многоканального счетчика, третий выход блока синхронизации5 подключен к тактовому входу регистра сдвига, информационный выход которого подключен к одноименному входу коммутатора, К-й разряд второго инФормационного выхода которого подключен к входу установки в "О" К-го каналапервого многоканального счетчика,вход режима работы. блока перечисления множеств подключен к входуразрешения сдвига вправо регистрасдвига, (В+1)-й разряд информационного выхода которого является выходомпризнака назначения класса элементовблока перечисления множеств.1645970 Составитель А. МишинТехред Л,Олийнык Корректор Н.Король Редактор Л. Пчолннская Заказ 1351 Тираж 415 ПодписноеВНИИПИ Государственного комитете по изобретениям и открытиям при ГКНТ СССР113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101