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

подключен к входу установки в единицу j-ro разряда второго регистра, прямой выход которого соединен с первым входом j-ro элемента И четвертой группы, вторые входы элементов И третьей и четвертой групп объединены и подключены к инверсному выходу.третьего триггера блока управления, выход j-ro элемента И четвертой группы соединен с первыми входами элементов ИЛИ формирователей признаков пути длины два одноименной строки матрицы третьей модели графа, выход i-ro элемента И третьей группы подключен к вторым входам элементов ИЛИ формирователей признаков пути длины два одноименных столбца матрицы третьей модели графа, выход элемента ИЛИ блока управления подключён к входу запрета генера- тора импульсов, выход которого подключен к счетному входу третьего триггера блока управления, а вход запуска подключен к выходу первого элемента задержки блока управления, выход (N+1)-ro входового элемента И подключен к входу установки в единицу второго триггера блока управления и к первому входу элемента ИЛИ блока управления, второй вход которого объединен с входом установки в единицу первого триггера блока управления, отличающееся тем, что, с целью повышения быстродействия устройства, в блок управления введены

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

1 :

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

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

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

Устройство содержит блок 1 управ- -ления, первую 2 и вторую 3 модели графа, первую 4, вторую 5, третью 6 и четвертую 7 группы, из N элементов

К И (N у, К - число вершин графа),

.(2Ы-И)-й входовый элемент ИЛИ 8, -(К+1)-й входовый элемент И 9, первый 10 и второй 11 N-разрядные регистры, блок 12 формирования произведения.

третью модель 13 графа, состоящую из NxN формирователей 14 признаков пути длины два, каждый из которых содержит элемент ИЛИ 15 и триггер 16. Блок 1 управления содержит генератор 17 импульсов, первый 18, второй 19, третий 20 и четвертый 21 триггеры, первый 22 и второй 23 элементы задержки, элемент ИЛИ 24, элемент И 25. Первая 2 и вторая 3 модели графа состоят из NxN формирователей дуг, каждый из которых содержит триггеры 26 и 27 соответственно. Блок 12 формирования

произведения содержит NxN формирователей 28 произведений, каждый из которых состоит из N элементов И 29 и одного элемента ИЛИ 30. На структурных схемах обозначены первый 31, второй 32 и третий 33 входы блока 1 управления, первый 34, второй 35 и третий 36 выходы блока 1 управления, вход 37 блока 12 формирования произведения, группа 38 выходов первой модели 2 графа, группа 39 выходов второй модели 3 графа, первая 40 и вторая 41 группы входов блока 12 формирования произведения, группа 42 выходов блока 12 формирования произведения.

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

Первоначально триггеры 16 формирователей t признаков пути длины два третьей модели 13 графа, первьш 10 и второй 11 N-разрядные регистры, первый 18, второй 19. третий 20 и четвертый 21 триггеры блока 1 управления устанавливаются в нулевое состояние, в первую 2 и вторую 3 модели графа заносится информация о топологии исследуемого графа. При этом триггеры 26 и 27, моделирующие дуги графа, устанавливаются в единичное состояние. Соответствующий триггер

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

С поступлением пускового сигнала на вход 31 устройства на первом вы- ходе 34 блока управления вьфабатывается сигнал.

который

вход 37 блока 12,

через первьй И

11

29f|N,

ЗЧ,н,

29/,,

элементы

.., 29, элементы формирователей 28

ИЛИ

и

произведений обеспечивает формирование значений элементов матрицы произведения и через группу выходов

и т ,

10

15

20

25

42 блока 12 занесение их в триггеры 16,,,..., 16,„ формирователей 14,..., 14..U признаков пути длины два третьей

ftn

м.одели 13 графа. Через первый 22 элемент задержки блока управления пусковой сигнал поступает на запускающий вход генератора 17 импульсов.

Работа устройства по обнаружению циклов в двудольном ориентированном графе и выделению вершин графа, образующих циклы, основана на сокращении матрицы произведения и завершается в тот момент, когда дальнейшее сокра щение матрицы произведения невозможно. Цикл работы устройства складывается из тактов, каждый из которых определяется парой выходных импульсов генератора 17, поступающих на счетный вход третьего триггера 20 блока управления. Нечетный импульс генератора 17 (например, первый) устанавливает триггер 20 в единичное состояние. Сигнал с прямого выхода триггера 20 устанавливает в единичное состояние четвертый триггер 21 блока управления и через второй выход 35 блока управления поступает на (N+l)-e входы всех (N+l)-x входовых элементов 30 И первой 4 и второй 5 групп из N элементов И, на остальные N входов которых поступают потенциальные сигналы с нулевых выходов триггеров 16 формирователей 14 признаков пути длины два соответствующей строки (для элементов И первой группы 4 элементов И) или столбца (для элементов И второй группы 5 элементов И). Сигнал с выхода элемента И, соответствующего строке третьей модели 13 графа, все триггеры 16 которой находятся в нулевом Состоянии (в первой группе 4 элементов И), устанавливает в единичное состояние соответствующий разряд первого регистра 10, сигнал с выхода элемента И, отвечающего столбцу третьей 13 модели графа, все триггеры 16 которого находятся в нулевом состоянии (во второй 5 группе элементов И), устанавливает в единичное состояние соответствующий разряд регистра 11. Четный импульс генератора 17 (например, второй) устанавливает третий триггер 20 блока управления в нулевое состояние. Сигнал с нулевого выхода триггера 20 поступает на вход второго элемента 23 задержки блока управления, а также через третий выход 36 блока управления поступает на

35

40

45

50

55

10

(N+l)-ft вход элемента И 9 и на вторые входы всех трехвходовых элементов И третьей 6 и четвертой 7 групп, первые входы которых соединены с единичными выходами соответствующих разрядов

первого 10 и второго 11 регистров, а третьи входы - с нулевыми В1 1ходами

. соответствующих разрядов второго 11 и первого 10 регистров. Такое подключение входов элементов И третьей 6 и четвертой 7 групп обеспечивает выработку выходных сигналов для обнуления только тех ненулевых строк (столбцов) третьей модели графа 13, |5 которым соответствуют нулевые столбцы (строки) этой же модели графа,т.е. обнуление каждой строки (столбца) производится однократно. Сигнал с вы- . хода i-ro элемента И третьей 6 группы 20 поступает на соответствующий вход элемента .ИЛИ 8 и на вторые входы всех элементов ИЛИ 15 формирователей 14 признаков пути длины два i-ro столбца: третьей модели графа и устанавливает соответствующие триггеры 16 в ; нулевое состояние. Сигнал с выхода j-ro элемента И четвертой группы 7 поступает на первые входы всех элегенератора 17 импульсов. Сигнал г выхода элемента ИЛИ 8 поступает на второй вход 32 блока управления, где устанавливает в нулевое состояние четвертый триггер 21. Установкой в нулевое состояние четвертого триггера 21 сигнал с выхода элемента ИЛИ 8 запрещает выработку сигнала на выходе элемента И 25 блока управления. Если сигнал на выходе элемента ИЛИ 8 в данном такте не выра:батывается (нет сигналов на обнуление строк или столбцов третьей модели графа и нет сигнала с выхода элемента И 9), четвертый триггер 21 блока управления остается в единичном состоянии, сигнал с нулевого выхода триггера 20, задержанный вторым 23 элементом задержки поступает на второй вход элемента И 25, на выходе которого вырабатывается сигнал, который устанавливает в единичное состояние триггер 18 и через элемент ИЛИ 24 поступает на запрещающий вход генератора 17 импульсов.

25

Работа устройства по обнаружению циклов в двудольном ориентированном .

ментов ИЛИ 15 формирователей 14 приз-зо вьщелению вершин графа, обранаков пути длины два j-й строки третьей модели графа и устанавливает соответствующие триггеры 16 в нулевое состояние. Сигнал на выходе элемента И 9 вырабатывается по импульсу с третьего 36 выхода бл ока управления в том случае, если все разряды первого регистра 10 установлены в единичное состояние (все триггеры 16 третьей

35

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

модели графа находятся в нулевом исследуемом графе циклов нет. Если

тоянии). Сигнал с выхода элемента И 9 поступает на (2 Ы+1)-й вход элемента ИЛИ 8 и третий вход 33 блока управления, где устанавливает в единичное состояние второй триггер 19 блока ., управления и через первый элемент ИЛИ 24 поступает на запрещающий вход

триггер 18 находится в единичном состоянии, то в исследуемом графе Имеется не менее одного цикла и номера вершин первого подмножества вершин графа, образующих циклы, равны номерам разрядов регистра 10 (11), которые находятся в нулевом состоянии.

10

|520 42366

генератора 17 импульсов. Сигнал г выхода элемента ИЛИ 8 поступает на второй вход 32 блока управления, где устанавливает в нулевое состояние четвертый триггер 21. Установкой в нулевое состояние четвертого триггера 21 сигнал с выхода элемента ИЛИ 8 запрещает выработку сигнала на выходе элемента И 25 блока управления. Если сигнал на выходе элемента ИЛИ 8 в данном такте не выра:батывается (нет сигналов на обнуление строк или столбцов третьей модели графа и нет сигнала с выхода элемента И 9), четвертый триггер 21 блока управления остается в единичном состоянии, сигнал с нулевого выхода триггера 20, задержанный вторым 23 элементом задержки поступает на второй вход элемента И 25, на выходе которого вырабатывается сигнал, который устанавливает в единичное состояние триггер 18 и через элемент ИЛИ 24 поступает на запрещающий вход генератора 17 импульсов.

25

Работа устройства по обнаружению циклов в двудольном ориентированном .

5

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

исследуемом графе циклов нет. Если

триггер 18 находится в единичном состоянии, то в исследуемом графе Имеется не менее одного цикла и номера вершин первого подмножества вершин графа, образующих циклы, равны номерам разрядов регистра 10 (11), которые находятся в нулевом состоянии.

г

г.

Фи&.1