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

О СО

«ш

со

««

ю

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

Фие.3

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

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

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

Устройство (фиг.1) содержит блок 1 памяти, мультиплексор 2, счетчик 3, имеющий выходы 3.1,3.2 и 3.3, три регистра 4-6, триггер 7, генератор 8, группу элементов И 9.1- 9.В, где В - количество вершин в графе, четыре элемента И 10-13, шесть элементов ИЛИ 14-19, пять элементов 20-24 задержки, одновибратор 25, адресные входы 26, управляющий вход 27 адресации, вход 28 сброса, информационные выходы 29, выход 30, вход 31 пуска, информационные входы 32, вход 33 записи и управляющий выход 34.

Регистр 5 (фиг.2) выполнен на сдвиговом регистре 35, элементе 36 задержки и элементе ИЛИ-НЕ 37.

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

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

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

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

По окончании в блоке 1 памяти будет записана матрица смежности исследуемого

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

источника питания). На управляющем входе 27 устанавливается напряжение 1, по которому к адресным входам блока 1 происходит подключение выходов счетчика 3, причем предварительный сброс счетчика 3,

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

0 5. Далее с задержкой, определяемой элементом 21 задержки, через элемент ИЛИ 18 обнуляется регистр 4. Затем с задержкой, определяемой элементом 24 задержки, устанавливается триггер 7 и запускается гене5 ратор 8. В дальнейшем работа устройства происходит под управлением импульсов, формируемых генератором 8. В том случае, если на выходе 5.1 регистра 5 устанавливается 1 (этого не может быть в случае, когда

0 в регистре 5 записана первая строка матрицы смежности, так как первая вершина не инцидентна себе самой - граф без петель), открывается элемент И 13 и передним фронтом импульса через элемент ИЛИ 19 в ре5 гистр 4 записывается информация из ячейки блока 1 памяти, адрес которой определяется состоянием выходов 3.1 счетчика 3.

Задним фронтом тактового импульса циклически вправо сдвигается информация,

0 записанная в регистре 5. Переключение регистра 5 из режима параллельной записи в режим циклического сдвига вправо обеспечивается следующим образом (фиг.2), При сдвиге информации циклически вправо им5 пульс сдвига поступает от генератора 8 на вход сдвига и с него на второй вход элемента ИЛИ-НЕ 37. Так как вход синхронизации (параллельной записи) от элемента ИЛИ 17 обнулен (нет пускового импульса и нет пе0 реполнения счетчика 3), регистр 35 находится в режиме сдвига вправо. Действительно, его второй вход разрешения Е2 находится в состоянии 1, так как подключен к шине +5В через ограничительный резистор (не по5 казан). Первый вход разрешения Е1 обнулен в связи с отсутствием импульса выхода элемента ИЛИ 17.

Поэтому с каждым импульсом генератора 8 информация в регистре 35 сдвигается вправо, причем последние разряды информации, установленные на его выходах, последовательно поступают на информационный вход для сдвига вправо регистра 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. Затем через интервал времени, формируемый элементом 22 задержки, задний фронт сигнала переполнения на выходе 3.3 поступает на второй вход элемента И 12, первый вход которого активирован сигналом О на выходе 30 устройства. В том случае, если хотя бы один из элементов группы элементов И 9.1- 9.В формирует на своем выходе сигнал 1 (признак небихроматичности графа по К-й вершине), то элемент И 12 блокирован 1 на выходе 30.

Следовательно, в регистр 5 из регистра

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

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

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

0 информация из регистра 5 и все выходы регистра 6 станут равными логической единице.

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

5 15 и 16 обнуляет триггер 7, который останавливает генератор 8. На управляющем выходе 34 формируется сигнал 1, свидетельствующий об окончании анализа графа.

Кроме того, задним фронтом импульса

0 на выходе элемента 22 задержки в регистр

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

В .общем случае работа устройства

5 (фиг.З) может быть представлена следующим образом.

Перед началом работы в блок. 38 задания матрицы смежности заносят информацию о топологии графа, з в накапливающий

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

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

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

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

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

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

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

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

D

32$ D

А

27

и

D

7.7 J.2

J.J

J7

л22L

8

Г

ff

2У

25

;

R

23

П У

ИГ

П

30

18

Л

Jfel

7 7

28

п

Л

,С

SH

f.1

-с

R

W

Г51

,С

Фиг.1

J4

Фиг. Z