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

(56) АвторскоеУ 1015385, кл.Авторское спо заявке У 3761984. Бюл, У 6енко, В,А,8,8)свидетельство С 06 Р 15/20, идетельство С 862/24, кл. С 06 СССР1983.СРР 15/20,ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ПИСАНИЕ ИЗОБ К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(54) (57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее блок управления, который состоит из генератора импульсов, первого, второго, третьего триггеров, первого элемента задержки и элемента ИЛИ, первую и вторую модели графа, каждая из которых состоит из матрицы Бх Б (где М = К/2, К - число вершин графа) формирователей дуг, причем каждый формирователь дуги матрицы модели графа выполнен на триггере; первую, вторую, третью и четвертые группы элементов И по Н элементов в каждой, элемент ИЛИ, (В+1)-й входовый элемент И, первый и второй регистры,.блок формирования произведения, содержащий матрицу из Кх М формирователей произведений, каждый из которых состоит из М элементов И и элемента ИЛИ; третью модель графа, состоящую из матрицы Б х И формирователей признаков пути длины два, каждый из которых содержит элемент ИЛИ и триггер, причем выход каждого 3-го триггера каждой 1-й строки матрицы первой модели графа (где 1 = 1,2Н) соединен с первым входом 1-го элемента И каждого из формирователей произведений д-й строки,матрицы блока формирования произведе. ЯО 1 З 742 З 6 ний, а выход каждого -го триггера каждого 1-го столбца матрицы второй модели графа подключен к второму вхо" ду 1-го элемента И каждого из формирователей произведения 1-го столбца матрицы блока формирования произведения, третий вход 3-го элемента И каждого из формирователей произведения матрицы блока формирования произведения соединен с входом первого элемента задержки блока управления и является входом запуска устройства, выход каждого 1-го элемента И каждого из формирователей произведения матрицы блока формирования произведения подключен к 3-му входу элемента ИЛИ тогоф же формирователя произведения матрицы блока формирования произведения,выход элемента ИЛИ каждого 1-го формирователя произведения каждой -й строки матрицы блока формирования произведения соединен с входом установки в единицу триггера одноимен-ного формирователя признаков путидлины два матрицы третьей модели графа, вход установки в ноль которогоподключен к выходу элемента ИЛИ этогоже формирователя признака путем длины два, а инверсный выход триггераподключен к 1-му входу д-го элементаИ первой группы и к -му входу 1-гоэлемента И второй группы (И+1)-е входы элементов И первой и второй группы подключены к прямому выходу третьего триггера блока управления, выходд-го элемента И первой группы соединен с входом установки в единицу-го разряда первого регистра, прямойвыход которого соединен с первым входом 1-го элемента И третьей группы,выход 1-го элемента И второй группы1374236 подключен к входу установки в единицу3-го разряда второго регистра, прямойвыход которого соединен с первым входом 3-го элемента И четвертой группы,вторые входы элементов И третьей ичетвертой групп объединены и подключены к инверсному выходу третьеготриггера блока управления, выход 3-гоэлемента И четвертой группы соединенс первыми входами элементов ИЛИ формирователей признаков пути длины дваодноименной строки матрицы третьеймодели графа, выход -го элемента Итретьей группы подключен к вторымвходам элементов ИЛИ формирователейпризнаков пути длины два одноименныхстолбца матрицы третьей модели графа, выход элемента ИЛИ блока управления подключен к входу запрета генератора импульсов, выход которого подключен к счетному входу третьеготриггера блока управления, а вход запуска подключен к выходу первогоэлемента задержки блока управления,выход (И+1)-го входового элемента Иподключен к входу установки в единицу второго триггера блока управленияи к первому входу элемента ИЛИ блокауправления, второй вход которогообъединен с входом установки в единицу первого триггера блока управления,о т л и ч а ю щ е е с я тем, что, сцелью повышения быстродействия устройства, в блок управления введены 1Изобретение относится к вычислительной технике и может быть использовано при создании устройства длярешения задач на графах и как составная часть вычислительных устройств.Цель изобретения - повышение быстродейсФвия устройства за счет того,.что исследование графа производитсяпо гибкому циклу, длительность которого определяется максимальной длинойцепочек, образуемых вершинами,не, участвующими в циклах,Яа фиг. 1 приведена структурнаясхема устройства; на фиг. 2 - струкчетвертый триггер, второй элемент задержки и элемент И, причем прямойвыход д-го разряда первого регистрасоединен с 1-м входом (И+1)-го входового элемента И, (И+1)-й вход которого соединен с инверсным выходомтретьего триггера блока управления,инверсный выход -го разряда первогорегистра соединен с третьим .входом1-го (.=3) элемента И четвертойгруппы, а инверсный выход 1-го разряда второго регистра соединен с третьим входом д-го элемента И третьейгруппы, выходы элементов И третьейи четвертой группи (И+1)-го входового элемента И соединены с соответствующими входами элемента ИЛИ,выход,которого соединен с входом установкив ноль четвертого триггера блока управления, вход установки в единицукоторого соединен с прямым выходом .третьего триггера блока управления,прямой выход четвертого триггера блока управления подключен к первомувходу элемента И блока управления,выход которого подключен к входуустановки в единицу первого триггераблока управления, а второй вход элемента И блока управления соединен свыходом ,второго элемента задержкиблока управления, вход которого подключен к инверсному выходу третьеготриггера блока управления,2турная схема блока управления; нафиг. 3 - структурные схемы первой ивторой моделей графа и блока формирования произведения,Устройство содержит блок 1 управ-ления, первую 2 и вторую 3 моделиграфа, первую 4, вторую 5, третью 6и четвертую 7 группы, из М элементовК1 ОИ (Н = в , К - число вершин графа),(2 Н+1)-й входовый элемент ИЛИ 8,,13742третью модель 13 графа, состоящую изИх Н формирователей 14 признаков путидлины два, каждый из которых содержитэлемент ИЛИ 15 и триггер 16, Блок 1управления содержит генератор 17 импульсов, первый 18, второй 19, третий 20 и четвертый 21 триггеры, первый 22 и второй 23 элементы задержки,элемент ИЛИ 24, элемент И 25. Первая2 и вторая 3 модели графа состоят изИх Н формирователей дуг, каждый изкоторых содержит триггеры 26 и 27 соответственно, Блок 12 формированияпроизведения содержит М х М формирователей 28 произведений, каждый изкоторых состоит из И элементов И 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 М-разрядные регистры,первый 18, второй 19 третий 20 ичетвертый 21 триггеры блока 1 управления устанавливаются в нулевое состояние, в первую 2 и вторую 3 моделиграфа заносится информация о топологии исследуемого графа, При этомтриггеры 26 и 27, моделирующие дугиграфа, устанавливаются в единичноесостояние. Соответствующий триггер45определяется пересечением строки сномером, равным номеру начальной"свершины дуги, и столбца с номером,равным номеру конечной вершины дуги.С поступлением пускового сигналана вход 3 1 устройства на первом выходе 34 блока управления вырабатывается сигнал, который через первыйвход 37 блока 12, элементы И 29,30 и 30 ш, формирователей 2828 произведений обеспечивает формирование значений элементов матрицыпроизведения и через группу выходов 36442 блока 12 занесение их в триггеры 16 16формирователей 14, 14 признаков пути длины два третьей модели 13 графа, Через первый 22 элемент задержки блока управления пусковой сигнал поступает на запускающий вход генератора 17 импульсов.Работа устройства по обнаружению циклов в двудольном ориентированном графе и выделению вершин графа, образующих циклы, основана на сокращении матрицы произведения и завершается в тот момент, когда дальнейшее сокра- щение матрицы произведения невозможно. Цикл работы устройства складывается из тактов, каждый из которых определяется парой выходных импульсов генератора 17, поступающих на счетный вход третьего триггера 20 блока управления. Нечетный импульс генератора 17 (например, первый) устанавливает триггер 20 в единичное состояние. Сигнал с прямого выхода триггера 20 устанавливает в единичное состояние четвертый триггер 21 блока управления и через второйфвыход 35 блока управления поступает на (Я+1)-е входы всех (И+1)-х входовых элементов И первой 4 и второй 5 групп из Н элементов И, на остальные И входов которых поступают потенциальные сигналы с нулевых выходов триггеров 16 формирователей 14 признаков пути длины два соответствующей строки (для элементов И первой группы 4 элементов И) или столбца (для элементов И второй группы 5 элементов И). Сигнал с выхода элемента И, соответствующего строке третьей модели 13 графа, все триггеры 16 которой находятся в нулевом состоянии (в первой группе 4 элементов И), устанавливает в единичное состояние соответствующий разряд первого регистра 10, сигнал с выхода элемента И, отвечающего столбцу третьей 13 модели графа, все триггеры 16 которого находятся в нулевом состоянии (во второй 5 группе элементов И), устанавливает в единичное состояние соответствующий разряд регистра 11. Четный импульс генератора 17 (например, второй) устанавливает третий триггер 20 блока управления в нулевое состояние. Сигнал с нулевого выхода триггера 20 поступает на вход второго элемента 23 задержки блока управления, а также через третий выход 36 блока управления поступает на(И+1)-й вход элемента И 9 и на вторые входы всех трехвходовых элементов И третьей 6 и четвертой 7 групп, первые входы которых соединены с единичными выходами соответствующих разрядов первого 10 и второго 11 регистров, а третьи входы - с нулевыми выходами соответствующих разрядов второго 11 и первого 10 регистров. Такое под ключение входов элементов И третьей 6 и четвертой 7 групп обеспечивает выработку выходных сигналов для обнуления только тех ненулевых строк (столбцов) третьей модели графа 13, 15 которым соответствуют нулевые столбцы (строки) этой же модели графа,т,е. обнуление каждой строки (столбца) про. изводится однократно. Сигнал с выхода 1-го элемента И третьей 6 группы 20 поступает на соответствующий вход элемента .ИЛИ 8 и на вторые входы всех элементов ИЛИ 15 формирователей 14 признаков пути длины два -го столбца третьей модели графа и устанавли вает соответствующие триггеры 16 в нулевое состояние. Сигнал с выхода 3-го элемента И четвертой группы 7 поступает на первые входы всех элементов ИЛИ 15 формирователей 14 приз иаков пути длины два 1-й строки третьей модели графа и устанавливает соответствующие триггеры 16 в нулевое состояние, Сигнал на выходе элемента И 9 вырабатывается по импульсу с тре 35 тьего 36 выхода блока управления в том случае, если все разряды первого регистра 10 установлены в .единичное состояние (все триггеры 16 третьей модели графа находятся в нулевом сос тоянии) . Сигнал с выхода элемента И 9 поступает на (2 И+1)-й вход элемента ИЛИ 8 и третий вход 33 блока управления, где устанавливает в единичное состояние второй триггер 19 блока управления и через первый элемент ИЛИ 24 поступает на запрещающий вход генератора 17 импульсов. Сигналвыхода элемента ИЛИ 8 поступает на второй вход 32 блока управления, гдеустанавливает в нулевое состояниечетвертый триггер 21. Установкой внулевое состояние четвертого триггера 21 сигнал с выхода элемента ИЛИ8 запрещает выработку сигнала на выходе элемента И 25 блока управленияЕсли сигнал на выходе элемента ИЛИ8 в данном такте не вырабатывается(нет сигналов на обнуление строк илистолбцов третьей модели графа и нетсигнала с выхода элемента И 9), четвертый триггер 21 блока управленияостается в единичном состоянии, сигнал с нулевого выхода триггера 20,задержанный вторым 23 элементом задержки, поступает на второй вход элемента И 25, на выходе которого вырабатывается сигнал, который устанавливает в единичное состояние триггер18 и через элемент ИЛИ 24 поступаетна запрещающий вход генератора 17 импульсов,1Работа устройства по обнаружению циклов в двудольном ориентированном . графе и выделению вершин графа,образующих цикл, заканчивается с остановкой генератора 17 импульсов, при,этом по состоянию триггеров 18 и 19 можно установить, имеются ли в исследуемом графе циклы, а по состоянию разрядов регистра 10 (11) однозначно определяются номера вершин графа, образующих циклыЕсли триггер 19 находится в единичном состоянии, то в исследуемом графе циклов нет. Если триггер 18 находится в единичном состоянии, то в исследуемом графе имеется не менее одного цикла и номера вершин первого подмножества вершин графа, образующих циклы, равны номерам разрядов регистра 10 (11), которые" находятся в нулевом состоянии.1374236 Составитель Т. СапуноТехред Л, Сердюкова Заказ 604 Подписное ВНИИПИ 11303 оизвадственно-полиграфиче предприятие актор Е.Копча Тираж осударстве ам изобрет сква, Жого комитета СССРий и открытийРаушская наб., д. Корректор Н.Король