Устройство для анализа параметров графа

 

Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов. Целью изобретения является расширение функциональных возможностей устройства путем проверки бихроматичности графа Устройство содержит блок 38 задания матрицы смежности, блок 39 определения концевых вершин дуг, накапливающие блоки 40 и 41 логического сложения, блок 42 синхронизации, блок 43 поразрядного сравнения, вход 44 пуска устройства , вход 45 признака окончания работы устройства, выходы 47 группы блока 42 синхронизации и его выходы 48-51. Перед началом работы в блок 38 задания матрицы смежности заносят информацию о топологии графа, а в блок 41 - информацию о вершинах , которыми заканчиваются дуги, исходящие из первой вершины графа. На вход 44 пуска подают импульсный сигнал уровня 1. При этом блок 42 синхронизации формирует последовательность сигналов, под управлением которой производится проверка бихроматичности графз. 4 ил.

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

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

РЕСПУБЛИК (si)s 6 06 F 15/419

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4473463/24 (22) 15.08.88 (46) 30.09.91, Бюл. 3Ф 36 (72) В.А,Несмелов, С.Ф.Тюрин, В.И.Назин и A.B,ßêoàëåB (53) 681.333 (088.8) (56) Авторское свидетельство СССР

М 1280380, кл. G 06 Е 15/20, 1984.

Авторское свидетельство СССР

N. 1587535, кл. G 06 F 15/20, 26,04.88. (54) УСТРОЙСТВО ДЛЯ АНАЛИЗА ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для анализа связности графов. Целью изобретения является расширение функциональных возможностей устройства путем проверки бихроматичности графа, Устройство содер„;, Ж„„1681312 А1 жит блок 38 задания матрицы смежности, блок 39 определения концевых вершин дуг, накапливающие блоки 40 и 41 логического сложения, блок 42 синхронизации, блок 43 поразрядного сравнения, вход 44 пуска устройства, вход 45 признака окончания рабаты устройства, выходы 47 группы блока 42 синхронизации и его выходы 48 — 51. Перед началом работы s блок 38 задания матрицы смежности заносят информацию о топологии графа, а в блок 41 — информацию о вершинах, которыми заканчиваются дуги, исходящие из первой вершины графа. На вход 44 пуска подают импульсный сигнал уровня "1", При этом блок 42 синхронизации формирует последовательность сигналов, под управлением которой производится проверка бихроматичности графа. 4 ил.

1681312

30

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

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

Устройство (фиг.1) содержит блок 1 памяти, мультиплексор 2, счетчик 3, имеющий выходы 3. 1, 3.2 и 3.3, три регистра 4-6, триггер 7, генератор 8, группу элемейтов И 9.19.8, где 8 — количество вершин в графе, четыре элемента И 10-13, шесть элементов

ИЛИ 14-19, пять элементов 20-24 задержки, одновибратор 25, адресные входы 26, управляющий вход 27 адресации, вход 28 сброса, информационные выходы 29, выход

30, вход 31 пуска, информационные входы

32, вход 33 записи и управляющий выход 34, Регистр 5 (фиг.2) выполнен на сдвиговом регистре 35, элементе 36 задержки и элементе ИЛ И-Н Е 37.

На фиг.3 обозначены: 38 — блок задания матрицы смежности; 39 — блок определения концевых вершин дуг; 40 и 41 — накапливающие блоки логического сложения; 42— блок синхронизации; 43 — блок поразрядного сравнения; 44 — вход пуска устройства;

45 — выход признака окончания работы устройства; 46 — выход када небихроматичности устройства; 47 — выходы группы блока

42 синхронизации; 48-51 — выходы блока 42 синхронизации.

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

Перед началом работы на вход 27 подается сигнал "0", по которому к адресным входам блока 1 памяти подключаются ад ресные входы 26. На информационные входы 32 поступает информация, кодирующая строки матрицы смежности исследуемого графа, причем "1" соответствует единичному элементу матрицы, а "0" — нулевому элементу, При записи каждой строки матрицы в блок 1 на управляющий вход 33 поступает импульс записи. Каждой строке матрицы соответствует свой адрес, выставляемый на входах 26.

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

По окончании в блоке 1 памяти будет запйсана матрица смежности исследуемого графа. Затем на входе 33 устанавливается напряжение "0", соответствующее режиму считывания информации(вход выборки кристалла блока 1 подключен к шине минус источника питания). На управляющем входе

27 устанавливается напряжение "1", по которому к адресным входам блока 1 происходит подключение выходов счетчика 3, причем предварительный сброс счетчика 3, регистров 4, 5 и б и триггера 7 осуществляется по входу 28 сброса, На вход 31 поступает импульс запуска, по переднему фронту которого в регистр 4 через элемент ИЛИ 19 записывается информация, соответствующая первой строке матрицы смежности, записанной в блок 1 памяти по нулевому адресу. Через элемент ИЛИ 17 задним фронтом импульса пуска происходит перезапись информации из регистра 4 в регистр

5. Далее с задержкой, определяемой элементом 21 задержки, через элемент ИЛИ 18 обнуляется регистр 4. Затем с задержкой, определяемой элементом 24 задержки, устанавливается триггер 7 и запускается генератор 8. В дальнейшем работа устройства происходит под управлением импульсов, формируемых генератором 8. В том случае, если на.выходе 5.1 регистра 5 устанавливается "1" (этого не может быть в случае, когда в регистре 5 записана первая строка матрицы смежности, так как первая вершина не инцидентна себе самой — граф без петель), открывается элемент И 13 и передним фронтом импульса через элемент ИЛИ 19 в регистр 4 записывается информация иэ ячейки блока 1 памяти, адрес которой определяется состоянием выходов 3.1 счетчика 3, Задним фронтом тактового импульса циклически вправо сдвигается информация, записанная в регистре 5. Переключение регистра 5 из режима параллельной записи в режим циклического сдвига вправо обеспечивается следующим образом (фиг.2), При сдвиге информации циклически вправо импульс сдвига поступает от генератора 8 на вход сдвига и с него на второй вход элемента ИЛИ-НЕ 37, Так как вход синхронизации (параллельной записи) от элемента ИЛИ 17 обнулен (нет пускового импульса и нет переполнения счетчика 3), регистр 35 находится в режиме сдвига вправо. Действительно. его второй вход разрешения Е2 находится в состоянии "1", так как подключен к шине

+58 через ограничительный резистор (не показан). Первый вход разрешения Е1 обнулен в связи с отсутствием импульса выхода элемента ИЛИ 17.

Поэтому с каждым импульсом генератора 8 информация в регистре 35 сдвигается вправо, причем последние разряды инфор1681312

10

25 20

40

55 мации, установленные на его выходах, последовательно поступают на информационный вход для сдвига вправо регистра 35. По последнему (В-му) импульсу на выходах регистра 35 устанавливается первоначальная информация. При поступлении импульса на вход синхронизации регистра 5 (фиг.1) регистр 35 (фиг.2) настраивается на параллельную запись информации. Это происходит следующим образом. Элемент

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

36 импульсом синхронизации с блока 17 (фиг.1).

Таким образом, регистр 5 (фиг.1) работает как в режиме параллельной записи по входу С (задним фронтом), так и в режиме циклического сдвига вправо (по входу SH— задним фронтом).

Таким образом, в регистр 4 передним фронтом тактового импульса генератора 8 записывается информация из соответствующей состоянию счетчика 3 ячейки блока 1 в том случае, если по заднему фронту предыдущего импульса на выходе 5,1 регистра 5 формируется "1", Следовательно, в регистре 4, представляющем собой набор триггеров, накапливается информация о единичных элементах строк матрицы смежности. номера которых соответствуют номерам позиций, имеющих единичные: элементы, в информации, записа н ной в регистре 5.

Па В-му импульсу счетчик 3 устанавливается в состояние и-1 (последнее состояние) и на его выходе 3.3 переполнения формируется сигнал "1". По (В+1)-му импульсу счетчик 3 обнуляется, в регистре 5 заканчивается циклический сдвиг, снимается сигнал "1" с выхода 3,3 и формируется сигнал "1" на выходе 3.2. Задний фронт сигнала на выходе 3.3 счетчика 3, задержанный на элементе 23 задержки, записывает в регистр 5 информацию из регистра 5. Затем через интервал времени, формируемый элементам 22 задержки, задний фронт сигнала переполнения на выходе 3,3 поступает на второй вход элемента И 12, первый вход которого активираван сигналом "0" на выходе 30 устройства. В том случае, если хотя бы один из элементов группы элементов И 9.19.В формирует на своем выходе сигнал "1" (признак небихраматичнасти графа по К-й вершине), та элемент И 12 блокирован "1" на выходе 30, Следовательно, в регистр 5 из регистра

4 записывается информация задним фронтом импульса переполнения на выходе 3.3 в том случае, если на выходе 30 не формируются сигналы 1

Дальше устройство работает аналогично: передним фронтом каждого тактового импульса, если возбужден выход 5.1 регистра 5, в котором уже записана новая информация, в регистр 4 записываются "1" иэ новых строк матрицы смежности, намерз которых соответствуют номерам позиций, имеющих единичные элементы в информации.

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

Поэтому возникает сигнал "1" на выходе элемента И 10, который через элемент ИЛИ

15 и 15 обнуляет триггер 7, который останавливает генератор 8. На управляющем выходе

34 формируется сигнал "1", свидетельствующий об окончании анализа графа.

Кроме того, задним фронтом импульса на выходе элемента 22 задержки в регистр

5 переписывается информация с регистра 4, затем импульсом с выхода аднав:;братара

25 обнуляется регистр 4, В .общем случае работа устройства (фиг,3) может быть представлена следующим образам.

Перед началам работы в блок 38 задания матрицы смежности заносят инфармацию а топологии графа, а в накапливающий блок 41 логического сложения — инфармацию о концевых вершинах дуг, исходящих из первой вершины графа, На вход пуска устройства подают импульс уровня "1". При этом блок 42 синхронизации формирует посл еда вател ьность им пул ьсов, и редус матренную временной диаграммой его работы (фиг,4), Сигнал уровня "1" появляется на третьем выходе 49 б- ка 42. При этом блок

40 устанавливается в "0", Через время, достаточное для установки в "О" блаха 40, блок

42 синхронизации снимает сигнал с выхода

49 и .формирует потенциал уровня "1" на первом выходе 47 группы. При этом (если опрос первой вершины графа разрешсн сигналом уровня "1" с первого разряда инфармационного выхода блока 41) блок 39 формирует на своем выходе мзссив кснцевых вершин дуг, исходящих из первой вершины графа. Через время. достаточное для определения массива ка - цевых вершин, 1681312

20

40 блок 42 формирует сигнал уровня "I" на своем первом выходе 48. При этом блок 40 накапливает (по ИЛИ) состав концевых вершин через время, достаточное для выполнения операции логического сложения (дизъюнкции), блок 42 снимает потенциалы с первого выхода 47 группы и выхода 48 и формирует потенциал уровня "1" на своем четвертом выходе 51, Блок 43 производит поразрядное сравнение кодов, накопленных блоками 40 и 41, и при совпадении хотя бы одного разряда останавливает блок 42 синхронизации. При этом на выходе 46 устройства будет сформирован код небихроматичности (позиция совпавших разрядов). В противном случае (при отсутствии совпадения разрядов) работа устройства повторяется для всех последующих вершин (потенциалы появля отся на втором, третьем, ..., В-м выходах 47 группы блока 42).

После того, как все вершины просмотрены, блок 42 формирует потенциал уровня "I" на своем выходе 50, При этом информация, накопленная блоком 40, накапливается (по

ИЛИ) в блоке 41. Через время, достаточное для выполнения операции логического сложения в блоке 41, блок 42 снимает потенциап с выхода 50 и формирует потенциал уровня "1" на своем выходе 49, При этом блок 40 обнуляется. Устройство аналогично работает до тех пор, пока не будет обнаружена небихроматичность графа или пока не заполнится единицами разрядная сетка блока 41 {при этом на выходе 45 устройства появляется потенциал уровня "1").

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

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

К-му разряду второго информационного входа блока поразрядного сравнения, выход признака наличия совпадений которого подключен к входу останова блока синхронизации, третий выход которого подключен к входу установки в "0" первого накапливающего блока логического сложения, четвертый выход блока синхронизации подключен к входу опроса блока поразрядного сравнения, информационный выход которого является выходом кода небихроматичности устройства, выход признака окончания работы которого является выходом признака заполнения разрядной сетки второго накапливающего блока логического сложения.

1681312

1681312 е е °

Р ° 4

° ° е

Редактор А.Лежнина

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

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

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

Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

OI7l 1 дж8

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

Техред М.Моргентал Корректор О.Кравцова