Устройство для раскраски графов Советский патент 1992 года по МПК G06F15/419 

00

о

К)

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

$/г.2

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

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

На фиг. 1 представлена функциональная схема устройства; на фиг.2 - функциональная схема блока перечисления множеств.

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

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

Устройство работает следующим обра- зом.

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

На вход 7 пуска устройства подают импульсный сигнал уровня логической единицы. При этом блок 4 синхронизации формирует на своем выходе последователь- ность тактовых импульсов уровня логической единицы. По каждому импульсу на его тактовом входе блок 5 перечисления множеств формирует на своих выходах комбинацию чисел, соответствующую текущей раскраске вершин графа. При этом блок 2 сравнивает попарно значения, поступившие на его информационные входы, и при совпадении значений, поступивших, например, на его К-й и М-й информационные входы ,...,В; М-1,...,В, где В - количество вершин в графе), формирует на своем (К,М)-м выходе .признака попарного равенства потенциал уровня логической единицы (это оз- начает, что К-я и М-я вершины имеют

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

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

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

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

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

В том случае, если единичные разряды его кода выходят за разрядную сетку справа, регистр 13 сдвига формирует сигнал уровня логической единицы на своем выходе признака переноса вправо за разрядную сетку (это означает, что вершины графа раскрашены в заданное количество цветов). В том случае, если за разрядную сетку вправо выходят нулевые разряды кода, регистр 13 сохраняет на своем выходе признака переноса вправо за разрядную сетку потенциал уровня .логической единицы.

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

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

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

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

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

0 опроса второй группы.

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

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

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

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

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

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

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

0 подключен к входу пуска узла синхронизации, первый выход которого подключен к тактовому входу многоканального узла счета, выход признака переполнения К-то канала которого (,...,В, В - количество

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

0

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