Устройство для раскраски графов
Похожие патенты | МПК / Метки | Текст | Заявка | Код ссылки
Текст
(19) 1)5 6 06 Р 15/419 ИСАНИЕ ИЗОБРЕТЕНИавальааай ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Таганрогский радиотехнический институт им, В.Д,Калмыкова(56) Авторское свидетельство СССРМ 1645970, кл, 6 06 Р 15/20, 1988.(54) УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано дляраскраски вершин графа в заданное количество цветов, Целью изобретения являетсяповышение быстродействия устройства засчет исключения выполнения заведомо непригодных шагов алгоритма раскраски,Блок 5 перечисления множеств устройства содержит тактовый вход 10, узел 11 синхронизации, многоканальный узел 12 счета, узел 13 сдвига, узел 14 проверки связности вершин, вход 15 режима работы (разрешения выполнения прямых шагов алгоритма перечисления) блока 5, выходы 16 значений элементов блока 5, выход 17 признака назначения класса элементов (признака исчерпания прямых шагов алгоритма перечисления) блока 5 и выход 18 признака возврата к пустому множеству (признак исчерпания обратных шагов алгоритма перечисления) блока 5. Идея повышения быстродействия устройства основана на том, что перед изменением цвета какой-либо из уже раскрашенных вершин графа проверяют связность этой вершины с той вершиной, раскраска которой ни в один из заданных цветов невозможна.2 ил.Изобретение относится к вычислительной технике, может быть использовано дляраскраски вершин графа в заданное количество цветов и является усовершенствованием устройства по авт,св. М 1645970.Цель изобретения - повышение быстродействия устройства за счет исключения выполнения заведомо непригодных шаговалгоритма раскраски.На фиг,1 представлена функциональнаясхема устройства; на фиг.2 - функциональная схема блока перечисления множеств,Устройство содержит блок 1 заданияматрицы смежности, первый блок 2 сравнения, блок 3 проверки связности вершин,блок 4 синхронизации, блок 5 перечислениямножеств, блок 6 сравнения, вход 7 пускаустройства, выход 8 признака окончания работы устройства и выход 9 признака отсутствия раскраски устройства.Блок 5 перечисления множеств содержит тактовый вход 10, узел 11 синхронизации, многоканальный узел 12 счета, регистр13 сдвига, узел 14 проверки связности вершин, вход 15 режима работы (разрешениявыполнения прямых шагов алгоритма перечисления) блока 5, выходы 16 значений элементов блока 5, выход 17 признаканазначения класса элементов (признака исчерпания прямых шагов алгоритма перечисления) блока 5 и выход 18 признака возвратак пустому множеству (признак исчерпанияобратных шагов алгоритма перечисления)блока 5.Устройство работает следующим образом,Перед началом работы устанавливают висходное состояние блок 5 перечислениямножеств, в блок 1 задания матрицы смежности заносят информацию о топологииграфа.На вход 7 пуска устройства подаютимпульсный сигнал уровня логическойединицы. При этом олок 4 синхронизацииформирует на своем выходе последовательность тактовых импульсов уровня логической единицы. По каждому импульсу на еготактовом входе блок 5 перечисления множеств формирует на своих выходах комбинацию чисел, соответствующую текущейраскраске вершин графа. При этом блок 2сравнивает попарно значения, поступившие на его информационные входы, и присовпадении значений, поступивших, например, на его К-й и М-й информационныевходы К=1,.,В; М,.;.,В, где В - количествовершин в графе), формирует на своем (К,М)-мвыходе признака попарного равенства потенциал уровня логической единицы (это означает, что К-я и М-я вершины имеют одинаковую окраску). Одновременно блок 6сравнения формирует потенциал уровня логической единицы на тех своих выходах, длякоторых значения информационных сигна 5 лов на соответствующем информационномвходе не равны нулю (т.е. соответствующаякоторым вершина раскрашена). В том случае, если ни одна из вершин, заданная блоком 6, не связана с другими, заданными10 блоком 2, на выходе блока 3 проверки связности сохраняется потенциал уровня логической единицы и устройство работаетаналогично. В противном случае (если одинаковую раскраску имеют связные верши 15 ны) потенциал уровня логической единицыснимается с выхода блока 3 и блок 5 изменяет режим формирования комбинаций,Работа устройства продолжается аналогично до тех пор, пока на одном из выходов 820 или 9 устройства не появится потенциалуровня логической единицы. При этом останавливается блок 4 синхронизации, а информация на выходах значений элементовблока 5 перечисления множеств (при нали 25 чии сигнала на выходе 8) соответствует заданной раскраске вершин графа.Блок 5 перечисления множеств работает следующим образом,Перед началом работы емкость каждого30 канала узла 12 счета устанавливают равнойтому количеству цветов, в которые допускается раСкрасить вершины графа, начальныезначения в его каналах устанавливают равными нулю, а в первый канал заносят еди 35 ницу(тем самым первая вершина считаетсяраскрашенной в первый цвет) и задают режим счета, разряды узла 12 сдвига устанавливают в ноль, а в первый разряд заносятединицу (тем самым предполагается, что40 раскраска первой вершины графа осуществлена) узел 14 настраивают на топологиюзаданного графа.При поступлении на тактовый вход 10блока 5 перечисления множеств импульса45 уровня логической единицы узел 11 синхронизации формирует на своих выходах последовательность сигналов, предусмотреннуювременной диаграммой его работы.Узел 11 синхронизации формирует им 50 пульс уровня логической единицы на своемвтором выходе, При этом при отсутствииединичного потенциала на его выходе блокировки и наличии потенциала уровня логической единицы на его входе разрешения55 сдвига вправо, узел 13 сдвигает значениехранимого им двоичного кода на один разряд вправо. При этом его крайние разряды слева заполняются нулями,В том случае, если единичные разрядыего кода выходят за разрядную сетку спра 1711189ва, регистр 13 сдвига формирует сигнал уровня логической единицы на своем выходе признака переноса вправо за разрядную сетку(это означает, что вершины графа раскрашены в заданное количество цветов). В том случае, если за разрядную сетку вправо выходят нулевые разряды кода, регистр 13 сохраняет на своем выходе признака переноса вправо за разрядную сетку потенциал уровня. логической единицы.Через время, достаточное для выполнения указанной операции, узел 11 синхронизации формирует импульс уровня логической единицы на своем первом выходе, При этом в счетном режиме работы все каналы узла 12, работа которых разрешена потенциалом уровня логической единицы на соответствующем входе признака выбора канала, увеличивают значение, накопленное в предыдущих тактах работы на единицу (тем самым соответствующие им вершины перекрашиваются в очередной допустимый цвет).В том случае, если значения, накопленные каналами узла 12 счета, превысят их емкость, то сами такие каналы обнуляются, а на соответствующих этим каналам выходах признаков наличия переполнения и на своем выходе признака наличия переполнений узел 12 счета формирует сигналы уровня логической единицы (тем самым предполагается, что вершины, соответствующие номерам таким каналов при заданной раскраске других вершин не могут быть раскрашены ни в один из допустимых цветов), При этом узел 12 счета переходит в режим обнуления признаков переполнения и разрешается сдвиг влево узла 13 сдвига,При поступлении на тактовый вход 10 блока 5 очередного импульса уровня логической единицы узел 11 синхронизации формирует последовательность сигналов, предусмотренную временной диаграммой его работы.Узел 11 синхронизации формирует импульс уровня логической единицы на своем втором выходе. При этом при наличии единичного потенциала на его входе разрешения сдвига влево узел 13 сдвигает значение хранимого им двоичного кода на один разряд влево, При этом его крайние разряды справа заполняются нулями, В том случае, если единичные разряды его кода выходят за разрядную сетку влево, узел. 13 сдвига формирует сигнал уровня логической единицы на своем выходе признака переноса влево за разрядную сетку(это означает, что данный граф не может быть окрашен в заданное количество цветов). В том случае, если за разрядную сетку влево выходят ну 5 10 15 20 25 30 35 40 45 50 55 левые разряды кода, узел 13 сдвига сохраняет на своем выходе признака переноса влево потенциал уровня логической единицы.Одновременно узел 14 проверяет связность вершин, заданных сигналами уровня логической единицы по входам опроса первой группы, с вершинами, заданными сигналами уровня логической единицы по входам опроса второй группы.В том случае, если хотя.бы одна из вершин первой (второй) группы связана с одной из вершин второй(первой) группы, узел 14 формирует сигнал уровня логической единицы на своем выходе признака связности. При этом в режиме обнуления признаков переполнения узел 12 счета устанавливает в ноль потенциалы уровня логической единицы на выходах признаков переполнения тех своих каналов, которые выбраны сигналами уровня логической единицы на соответствующих им входах выбора, и на своем выходе признака наличия переполнений (тем самым отменяется раскраска вершин, соответствующих этим каналам), и переходит в счетный режим работы.В том случае, если ни одна из вершин первой (второй) группы не связана ни с одной из вершин второй (первой) группы узел 14 сохраняет на своем выходе признака связности потенциал уровня логического нуля,Через время, достаточное для выполнения указанных операций, узел 11 синхронизации формирует импульс уровня логической единицы на своем первом выходе. При этом работа блока 5 повторяется.Формула изобретения Устройство для раскраски графов по а вт,св. М 1645970, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства путем исключения выполнения за- ведомо непригодных шагов алгоритма раскраски, блок перечисления множеств содержит узел синхронизации, многоканальный узел счета, регистр сдвига и узел проверки связности вершин, причем тактовый вход блока перечисления множеств подключен к входу пуска узла синхронизации, первый выход которого подключен к тактовому входу многоканального узла счета, выход признака переполнения К-го канала которого (К=1,.,В, В - количество вершин в графе) подключен к входу опроса К-й вершины первой группы узла проверки связности вершин, выход признака связности которого подключен к входу обнуления признаков переполнения каналов многоканального узла счета, выход признака налиЗаказ 342 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5 Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 чия переполнений которого подключен к своему входу режима работы и к входам блокировки сдвига вправо и разрешения сдвига влево регистра сдвига, К-й разряд информационного выхода которого подключен к входу опроса К-й вершины второй группы узла проверки связности вершин и к входу признака выбора К-го канала многоканального узла счета, информационный выход К-го канала которого является выходом значения К-го элемента блока перечисления множеств, вход режима работы которого подключен к входу разрешения сдвига вправо регистра сдвига, выход признака переноса вправо за разрядную сетку которого является выходом признака на значения класса элементов блока перечисления множеств, второй выход узла синхронизации подключен к тактовому входу регистра сдвига, выход признака переноса за разрядную сетку влево которого 10 является выходом признака возврата к пустому множеству блока перечисления множеств,
СмотретьЗаявка
4701160, 06.06.1989
ТАГАНРОГСКИЙ РАДИОТЕХНИЧЕСКИЙ ИНСТИТУТ ИМ. В. Д. КАЛМЫКОВА
ГЛУШАНЬ ВАЛЕНТИН МИХАЙЛОВИЧ, КАРЕЛИН ВЛАДИМИР ПЕТРОВИЧ, КУРЕЙЧИК ВИКТОР МИХАЙЛОВИЧ, РЯБЕЦ НИКОЛАЙ НИКОЛАЕВИЧ
МПК / Метки
МПК: G06F 15/419
Опубликовано: 07.02.1992
Код ссылки
<a href="https://patents.su/4-1711189-ustrojjstvo-dlya-raskraski-grafov.html" target="_blank" rel="follow" title="База патентов СССР">Устройство для раскраски графов</a>
Предыдущий патент: Устройство для решения задач на графах
Следующий патент: Устройство для моделирования сетей петри
Случайный патент: Струговый комплекс