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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 80 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ Е ИЗОБРЕТЕНВИДЕТЕЛЬСТВУ1 АВТОРСК 1862/24-206,8412,85, Б,33 (088,8)овьев Э,В, и к ситуаций пр Об ружениедействии вза числи вычис информационных процессо ытельных сетях, - Автома илительная техника, 1981, В 3,с. 11-17.Авторское свидетельствоВ 991434, кл, С 06 Р 15/20, 1981.(54)(57) УСТРОЙСТВО ДЛЯ ИССЛГДОВАНИЯГРАФОВ, содержащее четыре группыэлементов И, элемент ИЛИ, два й -разрядных регистра, блок управления идве модели графа, каждая из которых состоит из матрицы М М формирова..телей дуг, выполненных в виде триггеров, причем блок управления содержит счетчик, генератор импульсови два триггера, о т л и ч а ю щ ее с. я тем, что, с целью повьлдениябыстродействия, в него введены элемент И, блок формирования произве-дения и третья модель графа, состоящая из Н й формирователей признаков,каждый из которых содержит элемент ИЛИи триггер, блок формирования произя содержит матрицу К М формилей произведений, каждый изсостоит из й элементов И иИЛИ, в блок управления вве-мент задержки, первый илементы ИЛИ и третий тригочем выход 1-го (1=1,2 М)1-й (4 =1,2К) строки левойу к о ведени ровате которых ичным входо стра, выход динен с первого азряда о соег элемента дены эле второй э гер, при триггера оторо элдподк мендинен рвым входомей группы, вых второй групп му входу 1-го та И тре элемента к единич о Н а ОПИ САНИ первой модели графа соединен с первым входом -го элемента И каждогоформирователя произведения -й строки матрицы блока формирования произведения, выход 1-го триггера 1-гостолбца второй модели графа подключен к второму входу 1-го элемента И каждого формирователя произведения -го столбца матрицы блокаформирования произведения, третийвход 1-го элемента И каждого формирователя произведения соединен свходом элемента задержки блока управления и является входом устройства, выход -го элемента И каждогоформирователя произведения подключен к 1-у входу элемента ИЛИ соответствующего формирователя произведения,выход элемента,ИЛИ 1-го формирователя произведения 1-й строки матрицыблока формирования произведения соединен с единичным входом триггера 1-го формирователя признака 1-йстроки третьей модели графа, нувход которого подключен к выходэлемента ИЛИ этого формирователяпризнака, а нулевой выход - к 1-увходу- го элемента И первой группь-у входу -го элемента И второй груп9+ 1)-е входы элементов И первой ивторой групп соединены со счетнымвходом счетчика блока управления иподключены к прямому выходу третьетриггера блока управления, выход1-го элемента И первой группы сое1196891 второго регистра, выход которого соединен с первым входом 1-го элемей та И четвертой группы, вторые входы элементов И третьей и четвертой групп подключены к инверсному выходу третьего триггера блока управления, выход 1-го элемента И четвертой группы соединен с первыми входами элементов ИЛИ формирователей признаков одноименной строки третьей модели. графа, выход 1-го элемента И третьей группы подключен к вторым входам элементов ИЛИ формирователей признаков одноименного столбца третьей модели графа и 1 -му входу эле.мента И, выход которого соединен с входами второго триггера и первого элемента ИЛИ блока управления, выИзобретение относится к вычислительной технике и может бытьиспользовано при создании устройств длярешения задач на графах и как сос-.тавная часть вычислительных устройств. 5Цель изобретения - повышениебыстродействия,На фиг, 1 показана структурнаясхема устройства; на Фиг,2 - то же;блока управления; на Фиг.3 - струк Отурные схемы первой и второй матричной модели графа и блока формирования произведения.Устройство содержит блок 1 управления, первую 2 и вторую 3 модели 15графа, первую 4, вторую 5, третью 6и четвертую 7 группы из й элементов И (М= -К - число вершин граффа), элемент ИЛИ 8, элемент И 9, 20первый 10 и второй 11 Ю разрядныерегистры, блок 12 формирования произведения, третью модель графа 13,состоящую из йфй формирователей 14признаков пути длины два, каждый из 25которых содержит элемент ИЛИ 15 итриггер 16,Блок 1 управления содержит счетчик 17 по модулю М -1, генератор 18импульсов, первый 19, второй 20 итретий 21 триггеры, элемент 22 задержки, первый 23 и второй 24 элементы ИЛИ. Первая 2 и вторая 3 мо-дели графа состоят из НМ формироход первого элемента ИЛИ блока управления подключен к запрещающему входугенератора импульсов, выходи запускающий вход которого соединены соответственно со счетным входом третьего триггера и выходом элемента задержки блокауправления, выход счетчика подключен к вторым входам первого и второго элементов ИЛИ блока управления,выход второго элемента ИЛИ блока управления соединен с входом первоготриггера блока управления, первыйвход второго элемента ИЛИ подключен квыходу элемента ИЛИ, -й вход которогосоединен с выходом элементаИЛИ -гоформирователя произведения с -й строкматрицы блокаформирования произведения. вателей дуг, каждая из которых содержит триггеры 25 и 26 соответственно, Блок 12 содержит МИ формирователей 27 произведений, каждый нзкоторых состоит из Й элементов И 28и одного элемента ИЛИ 29,На структурных схемах обозначеныфпервый 30 и второй 31 входы блока управления, первый вход 32 блока 12,первый выход 33 блока управления,второй 34 и третий 35 выходы блокауправления, третий вход 36 блока управления, группа выходов 37 первоймодели графа, группа выходов 38 второй модели графа, первая 39 и вторая 40 группы входов блока 12 и груп.па выходов 41 блока 12,Устройство работает следующим образом,Первоначально триггеры 16 формирователей 14 признаков, регистры 10 и 11 счетчик 2, триггеры 19-21 устанавливаются в нулевое состояние, в первую.2 и вторую 3 модели графа заносится информация о топологии исследуемого графа. При этом триггеры 25 и 26, моделирующие дуги граФа, устанавливаются в единичное состояние, Соответствующий триггер определяется пересечением строки с номером, равным номеру начальной вершины дуги, и стол 5 ца с номером, рав" ным номеру конечной вершины дуги,3 11При поступлении пускового сигнала на вход устройства 30 на выходе 33 блока 1 управления появляется сигнал, который через вход 32 блока 12, элементы И 28 282828,нн элементы ИЛИ 29, 29 формирователей 27 27 ц гроизведений обуславливает формирование значений элементов матрицы произведения и через группу выходов 4 1 занесение их в тРиггеРы 16 116 яя АоРмиРователей 14, 14 цц признаков, Через элемент 22 задержки пусковой сигнал поступает на запускающий вход генератора 18 импульсов, Если на выходе одного из формирователей 27 произведений главной диагонали блока 12 вырабатывается единичный сигнал, то он, кроме третьей модели графа 13, через элемент ИЛИ Я, вход 31 блока 1 управления, элемент ИЛИ 24 устанавливает в единичное состояние триггер 19, что свидетельствует о наличии в графе хотя бы одного цикла,Работа устройства по обнаружению циклов в двухдольном ориентированном графе и выделению вершин графа, образующих циклы, основана на сокращении матрицы произведения и завершается не более чем за (й) тактов, Каждый такт работы устройства определяется парой выходных импульсов генератора 18,поступающих на счетный вход триггера 21,Нечетньв импульс генератора 18 (например, первый) устанавливает триггер 21 в единичное состояние, и сигнал с его прямого выхода поступает на счетный вход счетчика 17 и, кроме того, через выход 34 блока 1 управления поступает на (И+1)-е входы всех элементов И 4 и 5, на остальные М входов которых поступают потенциальные сигналы с нулевых выходов триггеров 16 формирователей 14 признаков соответствующей строки (для элемента И 4) или столбца (для элементов И 5). Сигнал с выхода элемента И, соответствующего строке третьей модели графа 13, все триггеры 16 которой находятся в нулевом состоянии (в группе элементов И 4), устанавливает в единичное состояние соответствующий разряд регистра 1 О, сигнал с выхода элемента И, отвечающего столбцу третьей модели графа 13, все триггеры 16 которого находятся в нулевом состоянии (в группе элементов И 5),устанавливает в единичное состояние соответствующий разряд96891 4 5 35 40 45 50 55 10 15 20 25 30 регистра 11, Четный импульс генератора 18 (например, второй) устанавливает триггер 21 в нулевое состояние, Сигнал с нулевого выхода триг-гера 21 через выход 35 блока управления поступает на вторые входы всехэлементов И 6 и 7, первые входы которых соединены с единичными выходами соответствующих разрядов регистров 10 и 11, Сигнал с выхода,1,-го элемента И 6 поступает на вторые входы всех элементов ИЛИ 15 формирователей 14 признаков 1-го столбца третьей модели графа 13 и устанавливает соответствующие триггеры 16в нулевое состояние,Сигнал с выхода -го элемента И 7поступает на первые входы всех элементов ИЛИ 15 формирователей 14 признаков 1-ой строки третьей моделиграфа 13 и устанавливает соответствующие триггеры 16 в нулевое состояние, Кроме того, выходные сигналывсех элементов И 6 поступают на входы элементов И 9, В случае совпадения сигналов на входах элемента И 9(все триггеры 16 третьей модели графа 13 находятся в нулевом состоянии,все разряды регистра 10 установленыв единичное состояние) на его выходевырабатывается импульс, который поступает на вход 36 блока 1 управления, устанавливает в единичное состояние триггер 20 и через элемент ИЛИ 23 поступает на запрещающий вход генератора 18 импульсов, останавливая работу устройства, которая завершается не более чем за М -1 тактов.В (И)-ом такте на выходе переполнения счетчика 17 вырабатывается сигнал, который через элемент ИЛИ 24 устанавливает в единичное состояниетриггер 19 и через элемент ИЛИ 23поступает на запрещающий вход генератора 18 импульсов, останавливая работу устройства,Работа устройства по обнаружению циклов в двудольном ориентированном графе и выделению вершин графа, образующих циклы, заканчивается с остановкой работы генератора 18 импульсов, при этом по состоянию триггеров 19 и 20 можно установить, име" ются ли в исследуемом графе циклы, а по состоянию разрядов регистра 10 (11) однозначно определяются вершины графа, образующие циклы, Если триггер 20 находится в единичном состоянии, то в исследуемом графе циклов3 1196891 Ьнет, Если триггер 19 находится в еди- ва вершин графа, обраэующих циклы, ничном состоянии, то в исследуемом равны номерам раэрядов регистра 10 графе имеется не.менее одного цикла, (11), которые находятся в нулевом и номера вершин первого подмножест- состоянии,119689 ставитель АЛеренкхред ЛЛратяшова едак Ландо Подписноемитета СССРоткрытийя наб., д, 4/5 Заказ 756 о й ск атент ф , Ужгород ул, Пр,49 Тираж 709ВНИИПИ Государственнпо делам иэобрете 113035, Москва, Ж, Р орректор Е.Рошко,