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

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

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

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

Устройство для раскраски графов содержит генератор 1 тактовых импульсов, элемент И 2, двоичные счет- выход индикации окончачики 3,-3„,

ния процесса поиска раскраски верл

шин графа 4, схемы 5,. сравнения, блок задания 6 исходных данных, груп

пу элементов И 7, -7.. элемент ИЛИ-НЕ

1 С

о, группу информационных входов.9 устройства, вход 10 сброса устройства, триггер II, элемент НЕ 12, . вход 13 запуска устройства, информационный выход 14 устройства, выход 15 индикации существования раскраски графа в заданное число цветов, триггер 16.

На фиг. 2 обозначены установочны вход 9, вход сброса 10, счетный .вход 17, выход 18 переноса, информационный выход 19,.триггеры со счетным входом 20,-20р, элемент ИЛИ 2 элементы сравнения 22,- 22р(элементы равнозначности) элемент И 23.

На фиг. 3 обозначены первая 24 и вторая 25 группы входов по р разрядов в каждой,- выход 26, элементы сравнения 27,-27р(элементы равнозначности), элемент И 28.

Выходы двоичных счетчиков

3,соединены с входами узлов 5 сравнения попарно в лексикографическом порядке. Это означает следующее. Произвольный граф G (V, Е) задается

,4.

,е,

t I V, ,V ,..

и множеством ребер Е Ге, ,е ,. где М - количество вершин, а q количество ребер.

Вершина с номером 1, ( ) соответствует i -и двоичный счетчик 3;,

5

сбрасываюшшся в нулевое состояние при значении, равном заданному количеству цветов К, в которое необходимо раскрасить граф. Значение сигналов на выходах двоичного счетчика 3 соответствует цвету (коду цвета) i-й вершины. Произвольный граф с М вершинами одновременно задается матрицей смежности, в которой элемент (i, j) матрицы принимает значение 1, если существует ребро, соединяющее вершины с номерами i и j. Матрица смежности неориентированного графа является симметричной относительно диагонали, образованной элементами матрицы вида (i, i) (,M), Поэтому для задания неориентированного графа достаточно задать только половину матрицы, так как вторая по- 0 ловина будет симметрична. Количество ребер в полном графе с М вершинами равно С„. Обозначим значения

л.

элементов половины матрицы через В ъ, jbji ,.. .Ъ, Яи расположим их последовательно в ячейках матрицы в направлении слева направо и сверху вниз. Ниже приведена матрица смежнос- сти неориентированного графа с обозначенными элементами матрицы. 0

5

М-2

М-1

,

М

Каждому элементу множества В соответствует некоторое ребро (i,j). Поставим в соответствие каждому ребру некоторое десятичное число К вида Н /мин (i,j)/ /макс (i,j)/. Например, ребру(3,5) соответствует число 35, а ребру (5,4) - число 45. Элементам множества В таким образом поставим в соответствие элементы множества Н. Элементы множества Н являются лексикографически упорядоченными. В

общем виде последовательность сочетаний на множестве элементов {l,2, 3,...,м| представлена в лексикографическом порядке, если она записана в порядке возрастания получающихся чисел.

Значения подаются на выходы соответствующих разрядов блока 6 задания исходных данных (значение Ъ| на i-й шины).

Количество информационных входов в группе информационных входов устройства, триггеров 20, элементов сравнения 22, количество входов в группах входов 24 и 25 обозначено р и определяется следующим образом:

Р log (К+1)

где К - число цветов, в которые раскрашивается граф,

... - означает, что р принимает

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

Например, для , , для , и т.д.

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

В исходном состоянии на вход 10 устройства подается сигнал Сброс. При этом состояние двоичных счетчиков З,- 3м CTaiioBHTCH 0...0, триггер 11 устанавливается в состояние

О

а триггер 16 - щсостояние Г

На вход 13 устройства подается сигнал запуска, включающий генератор 1 тактовых импульсов. Поскольку сигналы на выходах элемента НЕ 12 и триггера 16 равны 1, то импульсы с выхода генератора 1 импульсов поступают на вход элемента И 2, проходят на его выход и поступают на счет

ный вход двоичного счетчика 3|, меняя его состояние. При достижении двоичным счетчиком 3, состояния, соответствующего десятичному числу К, счетчик сбрасывается в нулевое состояние. При этом, на выходе переноса формируется импульс, изменяющий с,ос- тояние следующего за ним двоичного счетчика Э-JC. Указанный процесс повторяется для всех двоичных счетчиков. При ЭТОМ , на выходах двоичных счетчи- ков формируются двоичные слова, соответствующие кодам цветов вершин. Схемы 5 сравнения производят сравнение цветов смежных вершин для всех воз837834

можных ребер и формируют сигнал . на выходе, если цвета смежных вершин одинаковы. Сигналы с выходов схем 5 сравнения поступают на входы соответ. ствующих элементов Н 7. На вторые входы элементов И 7 поступают соответствующие сигналы с выходов блока задания 6 исходных данных. Поскольку в заданном графе некоторые ребра от10 сутствуют, то информация о цветах вершин, которые не связаны ребрами, исключается из дальнейшего анализа. Если i -е ребро отсутствует, то сигнал на i -м разряде блока 6 задания

f5 исходных данных равен О и, следовательно , сигнал на выходе элемента И 7 также равен О.

Граф называется К-раскрашиваемым, если любые две смежные вершины соединенные ребром окрашены в разные цвета. Следовательно, раскраска заданного графа и заданное количество цветов будет найдена, если на- выходах всех элементов И 7 будет сигнал О. При этом, на выходе элемента ИЛИ-НЕ 8 появляется сигнал 1, поступающий на выход 15 устройства (и, следовательно, свидетельствует о том, что решение найдено) и вход установки в нуль триггера 16, сбрасывая его в состояние О. При этом закрывается элемент И 2 и сигналы с выхода генератора 1 тактовых импульсов не поступают через элемент и 2 на двоичных счетчиков и не меняют их состояние. На информационном выходе результата 14 получаем двоичные слова, соответствующие кодам вершин.

Если в процессе поиска перебраны все варианты, а рещение не найдено то на выходе переноса двоичного счетчика Зщ появляется импульс,, сбрасывающий триггер 11 в состояние 1, которое поступает на выход 4 устройства (и свидетельствует об отсутст-т ВИИ решения) и через элемент НЕ 12 на вход элемента И 2, при этом сигналы с выхода генератора 1 тактовых импульсов не передаются на входы двоичных счетчиков 3 и не меняют ик состояние.

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

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

с целый повыпгения быстродействия , за счет автоматизации процесса раскраски графа в заданное число цветов, в него введены группа из М-двоичных счетчиков, группа из С схем сравне- ния, группа элементов И, элемент НЕ элемент ИЛИ-НЕ, два триггера, элемент И, причём вход генератора тактовых -импульсов является входом запуска устройства, выход генератора тактовых импульсов подключен к первому входу элемента И, второй.вход которого подключен к выходу первого триггера, вход установки в 1 которого объединен с входами сброса дво- ичных счетчиков группы, объединен с входом установки в О второго триггера и является входом сброса устройства, выход второго триггера подключен -к входу элемента НЕ и явля- ется выходом индикации окончания процесса поиска раскраски графа устройства, выход элемента НЕ подключен к третьему входу элемента И, выход которого подключен к счетному входу первого двоичного счетчика группы, выход переноса каждого i-ro двончсчетчика группы подключен к установки в 1 второго триггера.

ного счетчика группы (где i 1,2, ...,М-1) подключен к счетному входу (i + l)-ro двоичного счетчика группы. Выход переноса М-го двоичного

входу в

информационные выходы двоичных счетчиков группы подключены к соответствующим входам соответствующих схем сравнения группы и являются группой информационных выходов устройства, выход каждой схемы сравнения групп подключен к первому входу одноименного элемента И группы, второй вход каждого j-ro элемента И группы подключен к j-му разряду блока задания исходных данных (j 1,2,...,С) выход j-ro элемента И группы под- лючен к j-му входу элемента ИЛИ-НЕ, выход которого подключен к входу установки в О первого триггера, и является выходом индикации существования раскраски графа в заданное число цветов устройства, установочные входы счетчиков являются группой информационных входов устройства.

. /

24

25

ч

Р

Редактор В. Ковтун

Состав1|тель Т. Сапунова Техред Л.Олейник

Заказ 7443/48Тираж 670 Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Ц

27,

ы

аг.З

Корректор С. Черни

Изобретение относится к области автоматики и вычислительной техники и предназначено для автоматизации решения комбинаторно-графовых задач, в частности задачи раскраски графов в заданное количество цветов. Целью изобретения является повышение быстродействия устройства за счет автоматизации процесса раскраски графа в заданное число цветов. Устройство содержит генератор импульсов, элемент И, двоичные счетчики, схемы сравнения, блок задания исходных данных, группу элементов И, элемент ИДИ-НЕ, два триггера, элемент НЕ. Работа устройства основана на 1 енерации вариантов раскраски вершин графа и проверке требований по раскраске графа в заданное количество цветов. Устройство позволяет автоматизировать процесс раскраски графа, в заданное количество цветов и может найти применение при решении логико-комбинаторных задач в специализированных вычислительных устройствах, а также в качестве аппаратной реализации макрокоманды раскраски неориентированного графа в специализированных процессорах. З Ил. (Л 1C оо САЭ 00 00