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

 

Изобретение относится к вычислительной технике и может быть использовано для раскраски вершин графа в заданное количество цветов. Целью изобретения является повышение быстродействия устройства за счет исключения выполнения заведомо непригодных шагов алгоритма раскраски. Блок 5 перечисления множеств устройства содержит тактовый вход 10, узел 11 синхронизации , многоканальный узел 12 счета, узел 13 сдвига, узел 14 проверки связности вершин, вход 15 режима работы (разрешения выполнения прямых шагов алгоритма перечисления) блока 5, выходы 16 значений элементов блока 5, выход 17 признака назначения класса элементов (признака исчерпания прямых шагов алгоритма перечисления) блока 5 и выход 18 признака возврата к пустому множеству (признак исчерпания обратных шагов алгоритма перечисления ) блока 5. Идея повышения быстродействия устройства основана на том, что перед изменением цвета какой-либо из уже раскрашенных вершин графа проверяют связность этой вершины с той вершиной, раскраска которой ни в один из заданных цветов невозможна. 2 ил. у Ё

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

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

РЕСПУБЛИК

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

10 (61) 1645970 (21) 4701160/24 (22) 06.06.89 (46) 07.02.92. Бюл. ¹ 5 (71) Таганрогский радиотехнический институт им, В.Д,Калмыкова (72) В.М.Глушань, В.П.Карелин, В.М.Курейчик и Н.Н.Рябец (53) 681.333(088.8) (56) Авторское свидетельство СССР № 1645970, кл, G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ РАСКРАСКИ ГРАФОВ (57) Изобретение относится к вычислительной технике и может быть использовано для раскраски вершин графа в заданное количество цветов, Целью изобретения является повышение быстродействия устройства за счет исключения выполнения заведомо непригодных шагов алгоритма раскраски.

„„Я „„1711189 А2 (51)5 G 06 F 15/419

Блок 5 перечисления множеств устройства содержит тактовый вход 10, узел 11 синхронизации, многоканальный узел 12 счета, узел 13 сдвига, узел 14 проверки связности вершин, вход 15 режима работы (разрешения выполнения прямых шагов алгоритма перечисления) блока 5, выходы 16 значений элементов блока 5, выход 17 признака назначения класса элементов (признака исчерпания прямых шагов алгоритма перечисления) блока 5 и выход 18 признака возврата к пустому множеству (признак исчерпания обратных шагов алгоритма перечисления) блока 5. Идея повышения быстродействия устройства основана на том, что перед изменением цвета какой-либо из уже раскрашенных вершин графа проверяют связность этой вершины с той вершиной, раскраска которой ни в один из заданных цветов невозможна.2 ил.

1711189

Изобретение относится к вычислительной технике, может быть использовано для раскраски вершин графа в заданное количество цветов и является усовершенствованием устройства по авт.св. М 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,.„,В; М-1,.;.,В, где  — количество вершин в графе), формирует на своем (К,М)-м выходе признака попарного равенства потенциал уровня логической единицы (это означает, что К-я и М-я вершины имеют одинаковую окраску). Одновременно блок 6 сравнения формирует потенциал уровня логической единицы на тех своих выходах, для которых значения информационных сигна5 лов на соответствующем информационном входе не равны нулю (т.е. соответствующая которым вершина раскрашена). В том случае, если ни одна из вершин, заданная блоком 6, не связана с другими, заданными

10 блоком 2, на выходе блока 3 проверки связности сохраняется потенциал уровня логической единицы и устройство работает аналогично. В противном случае (если одинаковую раскраску имеют связные верши15 ны) потенциал уровня логической единицы снимается с выхода блока 3 и блок 5 изменяет режим формирования комбинаций, Работа устройства продолжается аналогично до тех пор, пока на одном из выходов 8

20 или 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

55 левые разряды кода, узел 13 сдвига сохраняет на своем выходе признака переноса влево потенциал уровня логической единицы.

Одновременно узел 14 проверяет связность вершин, заданных сигналами уровня логической единицы по входам опроса первой группы, с вершинами, задан ными сигналами уровня логической единицы по входам оп роса второй груп и ы.

В том случае, если хотя.бы одна из вершин первой (второй) группы связана с одной из вершин второй (первой) группы, узел

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

В том случае, если ни одна из вершин первой (второй) группы не связана ни с одной из вершин второй (первой) группы узел

14 сохраняет на своем выходе признака связности потенциал уровня логического нуля.

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

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

Устройство для раскраски графов по а вт.св. М 1645970, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия устройства путем исключения выполнения за ведомо непригодных шагов алгоритма раскраски, блок перечисления множеств содержит узел синхронизации, многоканальный узел счета, регистр сдвига и узел проверки связности вершин, причем тактовый вход блока перечисления множеств подключен к входу пуска узла синхронизации, первый выход которого подключен к тактовому входу многоканального узла счета, выход признака переполнения К-го канала которого (К=1...„B,  — количество вершин в графе) подключен к входу опроса

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

35

45

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

Редактор С.Патрушева Техред M.Ìoðãåíòàï Корректор Л.Патай

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

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101 чия переполнений которого подключен к своему входу режима работы и к входам блокировки сдвига вправо и разрешения сдвига влево регистра сдвига, К-й разряд информационного выхода которого подключен к входу опроса К-й вершины второй группы узла проверки связности вершин и к входу признака выбора -ro канала многоканального узла счета, информационный выход -ro канала которого является выходом значения К-го элемента блока перечисления множеств, вход режима работы которого подключен к входу разрешения сдвига вправо регистра сдвига, выход признака переноса вправо за разрядную сетку которого является выходом признака на5 значения класса элементов блока перечисления множеств, второй выход узла синхронизации подключен к тактовому входу регистра сдвига, выход признака переноса за разрядную сетку влево которого

10 является выходом признака возврата к пустому множеству блока перечисления множеств.