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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 511 4 0 06 Г 15/ ОБРЕТЕН ИСА ЛЬСТ УСВ ВТОР ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ(71) Харьковский авиационный институт им. Н.Е. Жуковского(56) Авторское свидетельство СССР В 643880, кл, С 06 Р 15/20, 1976.Авторское свидетельство СССР В 877552, кл. 0 06 Р 15/20, 1979.Авторское свидетельство СССР 9 433485, кл. С 06 Р 15/20, 1972. (54) УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРАФОВ (57) Изобретение относится к области автоматики и вычислительной техники и предназначено для автоматизации решения комбинаторно-графовых задач, в частности задачи раскраски графов в заданное количество цветов Целью изобретения является повыше 80128 З 78 З Д 1 ние быстродействия устройства засчет автоматизации процесса раскраски графа в заданное число цветов.Устройство содержит генератор импульсов, элемент И, двоичные счетчики, схемы сравнения, блок заданияисходных данных, группу элементов И,элемент ИЛИ-НЕ, два триггера, элемент НЕ. Работа устройства основанана енерации вариантов раскраскивершин графа и проверке требованийпо раскраске графа в заданное количество цветов. Устройство позволяетавтоматизировать процесс раскраскиграфа в заданное количество цветови может найти применение при решениилогико-комбинаторных задач в специализированных вычислительных устройствах, а также в качестве аппаратнойреализации макрокоманды раскраскинеориентированного графа в специализированных процессорах. 3 ил.12837Изобретение относится к автоматике и вычислительной технике, предназначено для автоматизации решения логико-комбинаторных задач и может бытьиспользовано в специализированныхвычислительных устройствах, а такжев качестве аппаратной реализации макрокоманды раскраски неориентированного графа в специализированных процессорах.10Цель изобретения - повышение бы".стродействия устройства за счет автоматизации процесса, раскраски графав заданное число цветов.. На Фиг. 1 представлена функциональная схема устройства для раскраски графов; на Фиг. 2 - схема двоичного счетчика; на фиг. 3 - конструкция схемы сравненияУстройство для раскраски графовсодержит генератор 1 тактовых импульсов, элемент И 2, двоичные счетчики З,-З, выход индикации окончания процесса поиска раскраски вершин графа 4, схемы 5,.-5 сравнения,2блок задания 6 исходных данных, группу элементов И 7, -7, элемент ИЛИ-НЕ8, группу информационных входов 9устройства, вход 10 сброса устройства, триггер 11, элемент НЕ 12,вход 13 запуска устройства, информационный выход 14 устройства, выход 15 индикации существования раскраски графа в заданное число цветов, триггер 16.35На фиг, 2 обозначены установочныйвход 9, вход сброса 10, счетный, вход 17, выход 18 переноса, информационный выход 19,.триггеры со счетным входом 20,-20 , элемент ИЛИ 2140элементы сравнения 22 - 22 (элемен"Рты равнозначности) элемент И 23.На Фиг. 3 обозначены первая 24и вторая 25 группы входов по р разрядов в каждой, выход 26, элементы45сравнения 27, -27 Р(элементы равно-.значности), элемейт И 28.1Выходы двоичных счетчиков 3, - Зцсоединены с входами узлов 5 сравнения попарно в лексикографическомпорядке. Это означает следующее.Произволвньв тра б (Р Е) задаетсямножеством вершин р рр Чми множеством ребер Бв 1 еет, ,я 1где М - количество вершин, аколичество ребер.Вершина с номером , (д=1 М ) соответствует-й двоичный счетчик 3 83 2сбрасываюшийся в нулевое состояние при значении, равном заданному количеству цветов К, в которое необходимо раскрасить граф. Значение сигналов на выходах двоичного счетчика 3 соответствует цвету (коду цвета) -й вершины. Произвольный граф с М вершинами одновременно задается матрицей смежности, в которой элемент (б, матрицы принимает значение "1", если существует ребро, соединяющее вершины с номерамии 3. Матрица смежности неориентированного графа является симметричной относительно диагонали, образованной элементами матрицы вида (3.,) (1=1,М) . Поэтому для задания неориентированного графа достаточно задать только половину матрицы, так как вторая половина будет симметрична. Количество ребер в полном графе с М верши 2нами равно С. Обозначим значения элементов половины матрицы через В = ббе,бои расположим их последовательно в ячейках матрицы в направлении слева направо и сверху вниз. Ниже приведена матрица смежноссти неориентированного графа с обозначенными элементами матрицы.1 2 3 4яд Мр1 ам-безМ Каждому элементу множества В соответствует некоторое ребро (х,3).Поставим в соответствие каждому ребру некоторое десятичное число Н вида Н =/мин (,1)/ /макс (з/. Например, ребру(3,5) соответствует число 35, а ребру (5 р 4) - число 45. Элементам множества В таким образом поставим в соответствие элементы множества.Н, Элементы множества Н являются лексикографически упорядоченными. В12837с целью повыщеция быстродействия,за счет автоматизации процесса раскрас - ки графа в заданное число цветов, в него введены группа из М-двоичных счетчиков, группа из Сл схем сравнения, группа элементов И, элемент НЕ, элемент ИЛИ-НЕ, два триггера, элемент И, причем вход генератора тактовых импульсов является входом запуска устройства, выход генератора 10 тактовых импульсов подключен к первому входу элемента И, второй. вход которого подключен к выходу первого триггера, вход установки в "1" которого объединен с входами сброса дво ичных счетчиков группы, объединен с входом установки в "О" второго триггера и является входом сброса устройства, выход второго триггера подключен к входу элемента НЕ и явля- .20 ется выходом индикации окончания процесса поиска раскраски графа устройства, выход элемента НЕ подключен к третьему входу элемента И, выход которого подключен к счетному входу первого двоичного счетчика группь 1, выход переноса каждого -го двоич 83 6ного счетчика группы (где=1,2, ,М) подключен к счетному входу ( + 1)-го двоичного счетчика группы, выход переноса М-го двоичного счетчика группы подключен к входу установки в "1" второго триггера, информационные выходы двоичных счетчиков группы подключены к соответ - ствующим входам соответствующих схем сравнения группы и являются группой информационных выходов устройства, выход каждой схемы сравнения групп подключен к первому входу одноименного элемента И группы, второй вход каждого )-го элемента И группы подключен к )-му разряду блока зада 2 ния исходных данных (1 =1,2С) выход 1-го элемента И группы подлючен к 1-му входу элемента ИЛИ-НЕ, выход которого подключен к входу установки в "0" первого триггера, и является выходом индикации существования раскраски графа в заданное число цветов устройства, установочные входы счетчиков являются группой информационных входов устройства.1283783 71 фиг. Я Составитель Т. СапуноТехред Л.Олейник Черн дактор В. Ковтун ррект Заказ 7443 нного енин и35, Ра к ственчо-полит рафическое предприятие, г, Ужгород, ул. Проектная, 4 рон ВНИИПИ Го по делам 13035, И ираждарстизобр Подписнонтета СССРкрытыйкая наб д. 4/5