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

 

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

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

РЕСПУБЛИК

„,SU„„1374236 др 4 С 06 F 15/20

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

К А ВТОРСКОМ,Ф СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3874281/24-24 (22) 26.03.85 (46) 15.02.88. Бюл. Р 6 (72) А.С. Омельченко, В.А. Батраков и В.И. Сущев (53) 681.333(088.8) (56) Авторское свидетельство СССР

11р 1015385, кл. G 06 F 15/20, 1983, Авторское свидетельство СССР по заявке Ф 3761862/24,кл.G 06 F 15/20, 1984. (54) (57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ, содержащее блок управления, который состоит из генератора импульсов, первого, второго, третьего триггеров, первого элемента задержки и элемента ИЛИ, первую и вторую модели графа, каждая из которых состоит из матрицы N x N (где N = K/2, К— число вершин графа) формирователей дуг, причем каждый формирователь дуги матрицы модели графа выполнен на триггере; первую, вторую, третью и четвертые группы элементов И no N элементов в каждой, элемент ИЛИ, (N+1)-й входовый элемент И, первый и второй регистры,.блок формирования произведения, содержащий матрицу из

Nx N формирователей произведений, каждый из которых состоит из N элементов И и элемента ИЛИ; третью модель графа, состоящую из матрицы N x N формирователей признаков пути длины два, каждый из которых содержит элемент ИЛИ и триггер, причем выход каждого 3-го триггера каждой 3-й строки матрицы первой модели графа (где

j = 1,2р...рН) соединен с пеРвым входом j-го элемента И каждого из формирователей произведений i-й строки, \ матрицы блока формирования произведений, а выход каждого i-го триггера каждого j-го столбца матрицы второй модели графа подключен к второму входу i-го элемента И каждого из формирователей произведения j-го столбца матрицы блока формирования произведения, третий вход j-го элемента И каждого из формирователей произведения матрицы блока формирования произведения соединен с входом первого элемента задержки блока управления и является входом запуска устройства, выход каждого j-го элемента И каждого из формирователей произведения матрицы блока формирования произведения подключен к j-му входу элемента ИЛИ того ф же формирователя произведения матрицы блока формирования проиввадания,вы- Я ход элемента ИЛИ каждого j-го формирователя произведения каждой i-й строки матрицы блока формирования произведения соединен с входом установки в единицу триггера одноимен- ного формирователя признаков пути длины два матрицы третьей модели графа, вход установки в ноль которого подключен к выходу элемента ИЛИ этого же формирователя признака путем длины два, а инверсный выход триггера подключен к j-му входу i-го элемента

И первой группы и к i-му входу j-го элемента И второй группы (N+1)-е входы элементов И первой и второй группы подключены к прямому выходу треть- ф

его триггера блока управления, выход

i-го элемента И первой группы соединен с входом установки в единицу

i-го разряда первого регистра, прямой выход которого соединен с первым входом i-ro элемента И третьей группы, выход j-ro элемента И второй группы

1374236 подключен к входу установки в единицу

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

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

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

Иа фиг. 1 приведена структурная схема устройства; на фиг. 2 — струкчетвертый триггер, второй элемент задержки и элемент И, причем прямой выход i-ro разряда первого регистра соединен с i-м входом (N+i)-го входового элемента И, (N+1)-й вход которого соединен с инверсным выходом третьего триггера блока управления, инверсный выход i-ro разряда первого регистра соединен с третьим .входом

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

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

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

К

10 И (N = 2, К вЂ” число вершин графа), (2Н+1)-й входовый элемент ИЛИ 8, -(N+1) é входовый элемент И 9, первый

10 и второй 11 N-разрядные регистры, блок 12 формирования произведения, 25

3

°,13742 третью модель 13 графа, состоящую из

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

2 и вторая 3 модели графа состоят из

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

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

45 определяется пересечением строки с номером, равным номеру начальной

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

С поступлением пускового сигнала на вход 3 1 устройства на первом выходе 34 блока управления вырабатывается сигнал, который через первый вход 37 блока 12, элементы И 29, ..

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

36

42 блока 12 занесение их в триггеры

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

Работа устройства по обнаружению циклов в двудольном ориентированном графе и выделению вершин графа, образующих циклы, основана на сокращении матрицы произведения и завершается в тот момент, когда дальнейшее сокра- щение матрицы произведения невозможно. Цикл работы устройства складывается из тактов, каждый из которых определяется парой выходных импульсов генератора 17, поступающих на счетный вход третьего триггера 20 блока управления. Нечетный импульс генератора 17 (например, первый) устанавливает триггер 20 в единичное состояние. Сигнал с прямого выхода триггера 20 устанавливает в единичное состояние четвертый триггер 21 блока управления и через второй выход 35 блока управления поступает на (N+1)-е входы всех (N+l)-х входовых элементов

И первой 4 и второй 5 групп из N элементов И, на остальные N входов которых поступают потенциальные сигналы с нулевых выходов триггеров 16 формирователей 14 признаков пути длины два соответствующей строки (для элементов

И первой группы 4 элементов И) или столбца (для элементов И второй группы 5 элементов И). Сигнал с выхода элемента И, соответствующего строке третьей модели 13 графа, все триггеры 16 которой находятся в нулевом состоянии (в первой группе 4 элементов И), устанавливает в единичное состояние соответствующий разряд первого регистра 10, сигнал с выхода элемента И, отвечающего столбцу третьей 13 модели графа, все триггеры

16 которого находятся в нулевом состоянии (во второй 5 группе элементов

И), устанавливает в единичное состояние соответствующий разряд регистра 11. Четный импульс генератора 17 (например, второй) устанавливает третий триггер 20 блока управления в нулевое состояние. Сигнал с нулевого выхода триггера 20 поступает на вход второго элемента 23 задержки блока управления, а также через третий выход 36 блока управления поступает на

l 374236 (И+1)-й вход элемента И 9 и на вторые входы всех трехвходовых элементов И третьей 6 и четвертой 7 групп, первые входы которых соединены с единичными выходами соответствующих разрядов первого 10 и второго 11 регистров, а третьи входы — с нулевыми выходами собтветствующих разрядов второго 11 и первого 10 регистров. Такое под- 10 ключение входов элементов И третьей

6 и четвертой 7 групп обеспечивает выработку выходных сигналов для обнуления только тех ненулевых строк (столбцов) третьей модели графа 13, которым соответствуют нулевые столбцы (строки) этой же модели графа,т,е. обнуление каждой строки (столбца) производится однократно. Сигнал с выхода i-го элемента И третьей 6 группы 20 поступает на соответствующий вход элемента .ИЛИ 8 и на вторые входы всех элементов ИЛИ 15 формирователей 14 признаков пути длины два i-ro столбца третьей модели графа и устанавли- 25 вает соответствующие триггеры 16 в нулевое состояние. Сигнал с выхода

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

И 9 вырабатывается по импульсу с тре35 тьего 36 выхода блока управления в том случае, если все разряды первого регистра 10 установлены в .единичное состояние (все триггеры 16 третьей модели графа находятся в нулевом сос- 40 тоянии) . Сигнал с выхода элемента И 9 поступает на (2 N+1)-й вход элемента

ИЛИ 8 и третий вход 33 блока управления, где устанавливает в единичное состояние второй триггер 19 блока управления и через первый элемент

ИЛИ 24 поступает на запрещающий вход генератора 17 импульсов. Сигнал выхода элемента ИЛИ 8 поступает на второй вход 32 блока управления, где устанавливает в нулевое состояние четвертый триггер 21. Установкой в нулевое состояние четвертого триггера 21 сигнал с выхода элемента ИЛИ

8 запрещает выработку сигнала на выходе элемента И 25 блока управления„

Если сигнал на выходе элемента ИЛИ

8 в данном такте не вырабатывается (нет сигналов на обнуление строк или столбцов третьей модели графа и нет сигнала с выхода. элемента И 9), четвертый триггер 21 блока управления остается в единичном состоянии, сигнал с нулевого выхода триггера 20, задержанный вторым 23 элементом задержки, поступает на второй вход элемента И 25, на выходе которого вырабатывается сигнал, который устанавливает в единичное состояние триггер

18 и через элемент ИЛИ 24 поступает на запрещающий вход генератора 17 импульсов.

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

1374236

1 374236

Составитель Т. Сапунова

Техред Л. Сердюкова

Корректор Н.Король

Редактор Е.Копча

Заказ 604/46 Тираж 704

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

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

Подписное

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