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

СОЮЗ СОНЕТСКИХС О Э ВМР И ес и ипРЕСПУБЛИК А 6 Г 15/20 УДАРСТНЕННЫЙ КОМИТЕТ СССРДЕЛАМ ИЗОБРЕТЕНИЙ И ОЧНРЫТЮПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМ онюк вания тво СС1971,о СССР1975(71) Институт проблем моделив энергетике АН УССР. (54) (57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее моДели вершин, соединенные между собой входными и :выходными информационными полюсами согласно топологии исследуемого графа,блок управления,сдвиговый регистр и группу элементов И, первые входь 1 которых соединены с разрядными информацнонньзя выходами сдвиговогодрегистра, вход и выход которого соединены соответственно с первым выхо- дом и входом блока управления, вто- . рой, третий и четвертый выходы которого подключены соответственно к первым, вторым и третьим унравпяющим входам моделей вершин, четвертые уп-" равляющие входы которых соединены с выходами соответствующих элементов И группы, вторые входы которых под.ключены к управляющим выходам соответствующих моделей вершин, каждая модель вершины содержит шесть элементов И, два элемента ИЛИ, два фор мирователя одиночных импульсов,два .триггера, первый элемент НЕ и узел индикации, причем первые входы первого и второго элементов И являются соответственно первым и вторым управляющими входами модели вершины, вторые входы первого и второго элементов И объединены и являются четвертым управляющим входом модели вершины, выходы первого и второго элементов И соединены с первыми вхо- дами соответственно первого и вто" рого элементов ИЛИ, выходы которых подключены к единичным входам первого и второго триггеров, второй вход первого элемента ИЛИ соединен с выходом третьего элемента И, первый вход которого соединен с нулевым выходом второго триггера, единичный выход, первого триггера соединен с первымвходом четвертого элемента И, входом первого формирователя одиноч.,ных импульсов и первым входом пятогоэлемента И, выход которого подключен ,ко второму входу второго элементаИЛИ, выход первого формирователя оди-ночных импульсов янляется выходным информационным полюсом модели вер шины и соединен со вторым входом пятого элемента И, единичный выход второго триггера. подключен к второму входу четвертого элемента . И и входу второго формирователя одиночных импульсов, выход которого является входным информационным полюсом модели вершины и соединен со вторым входом третьего элемента И, выход первого элемента НЕ является уп-, з, равляющим выходом модели вершины, о Ф л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет определения входных и выходных вершин максимальных сильно связных подграфов и дуг, связывающих их с другими верши-.1134946 Подписноета СССРьн ийнаб., д. 4/5 Заказ 10091/ Тираа 710 дарственного комит изобретений и откр ква, Ж, Раушская по делам113035, Ио Укгород, ул, Проектная, 4 Патен Составитель С.Назаров34946 11 нами, в каждую модель вершины дополнительно введены пять элементов И, три элемента ИЛИ, третий формирователь одиночных импульсов, третийтриггер, три сдвиговых регистра и второй элемент НЕ, блок управления содержит шесть элементов И, три триггера, счетчик импульсов, генератор импульсов и элемент ИЛИ, причем в каждой модели вершины первый вход шестого элемента И модели вершины соединен с входным информационным полю- сом модели вершины, первый вход седьмого элемента И подключен к выходному информационному полюсу модели вершины, вторые входы шестого и седьмого.элементов И модели вершины и первый вход третьего элемента ИЛИ соединены с единичным выходом третьего триггера, нулевой выход которого подключен к первым входам восьмого и де,вятого элементов И,объединенные вторые входы которых являются пятым управляющим входом модели вершины и соединены со входом второго элемента НЕ и первым входом десятого элемента И, третьи входы восьмого и девятого . элементов И объединены и подключены к четвертому управляющему входу модели вершины, выходы шестого и седьмого элементов И соединены соответст-. венно с информационными входами первого и второго сдвиговых регистров, сдвиговые входы которых объединены и подключены к выходу десятого эле- мента И, второй вход которого являет" ся шестым управляющим входом модели вершины, выход второго элемента НЕ соединен с третьчми входами первого, второго, третьего и пятого элементов И модели вершины, четвертый вход третьего элемента И соединен с пер=вым управляющим входом модели вершины, четвертый вход пятого элемента Имодели вершины соединен со вторым уйравляющим входом модели вершины, выходы восьмого и девятого элементов И подключены соответственно к вход- ному и выходному информационным полюсам модели вершины, вход первого элемента НЕ модели вершщны соединен с выходом третьего элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И и входу третье- го формирователя одиночньюс импульсов, вьасод которого соединен с первым входом четвертого элемента ИЛИ, второй вход которого подключен к единичному входу третьего триггера, выходу третьего сдвигового регистра и первомувходу узла индикации, второй и третийвходы которого соединены с выходамисоответственно первого и второго сдвиговых регистров, выход четвертогоэлемента ИЛИ подключен к информационному входу третьего сдвигового регистра, сдвиговый вход которого является третьим управляющим входом модели вершины, единичный вход первоготриггера блока управления являетсявходом блока управления и соединен спервыми входами первого и второгоэлементов И блока управления, единичный выход первого триггера блока управления соединен со вторыми входамипервого и второго и первым входом,третьего элементов И блока управления, выход первого элемента И блокауправления через счетчик импульсовблока управления подключен к нулевому входу первого триггера блокауправнения, нулевой выход первоготриггера блока управления соединен спервыми входами четвертого, пятогои шестого элементов И блока управления, вторые входы третьего и чет-.вертого элементов И блока управленияобъединены и подключены к первомувыходу генератора импульсов, выходтретьего элемента И блока управления соединен с первым входом элемен-та ИПИ блока управления, выход которого является первым выходом блока управления, высод четвертого эле- .мента И.блока управления соединенсо вторым входом элемента ИЛИ блокауправления, единичным входом второго и нулевым входом третьего тригГеров блока управления, единичныевыходы которьпс являются соответственно вторым и третьим выходами блокауправления, второй выход генератора импульсов подключен ко второму входу пятого элемента И блока управления, выход которого соединен с нулевым входом, второго и единичным входом третьего триггеров блока управления, единичный выход второго и нулевой выход третьего триггеров блока 1управления подключены соответственно,ко второму и третьему входам шестогоэлемента И блока управления, четвертый вход которого соединен с третьим выходом генератора импульсов,выходы второго и шестого элементов И блока управления объединены и являются четвертым выходом блока уп1134946равления , а единичный выход пер- является пятым выходом блока упвого триггера блока управления равления.Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах.Известно устройство для исследования графов, содержащее модели вершин соединенные между собой согласноЭтопологии исследуемого графа,-регистр, вход и первый выход которого подключены к первому выходу и входу блока управления, второй, третий и четвер 10 тый выходы которого соединены соответственно с первым, вторым и третьим входами моделей вершин, информационные выходы регистра соединены с первыми входами элементов И группы, второй вход каждого из которых под 15 ключен к первому выходу соответствующей модели вершины, выходы элементов И группы подключены соответственно к четвертым входам моделей вершин, каждая из которых содержит первый триггер, первый элемент ИЛИ, первый элемент И 1.Однако такое .устройство не позволяет произвести разложение графа на максимальные сильно связные подграфы.Наиболее. близким по технической, сущности к данному изобретению является устройство, содержащее модели вершин, число которых соответствует числу вершин исследуемого графаблок З 0 управпения, сдвиговый регистр, вход и выход которого соответственно соединены с первым и вторым полюсами блока управления, а выход каждого раз-. ряда сдвигового регистра соединен с 31 первым входом соответствующего первого элемента И, число которых равно числу моделей вершин, второй вход каждого элемента И соединен с третьим входом соответствующей ему моде ли вершины, у которой четвертый и пятый входы соответственно подключены к третьему и четвертому выходам блока управления, пятый выход которого соединен с шестыьы входами всех ;45 моделей вершин, причем модели вершин первым и вторым своими полюсами соедииены между собой в соответствии с топологией исследуемого графа, а седьмой вход каждой модели вершины .соединей с выходом соответствующего ей первого элемента И, при этом седь" мой вход в каждой модели вершины образован соединением первых входов второго и третьего элементов И, у которых вторые входы соответственно являются четвертым и пятым входами модели вершинь 1, .а выходы второго и третьего элементов И соединены с первыми входами соответственно первого и второго элементов ИЛИ, при этом вторые вхо)ы этих элементов ИЛИ соединены с выходами соответственно четвертого и пятого элементов И, причем выход первого элемента ИЛИ соединен с входом первого триггера, единичный выход которого соединен с входом первого формирователя одиночного импульса; выход которого соединен с первым входом пятого элемента И и является вторым полюсом модели вершины, с вторым входом пятого элемента И, третий вход которого подключен к пятому входу модели вершины, и первым входом шестого элемента И, второй вход которого соединен с входом шестого элемента И, второй вход которого соединен с входом второго формирователя одиночного импульса, выход которого соединен с жервым входом четвертого элемента И, второй вход которого подключен к четвертому, входу модели вершины, и является первым полюсом модейи вершины, и с единичным выходом вто рого триггера, у которого нулевой выход и единичный вход соответственно соединены с третьим входом четверто. го элемента И и с выходом второго элемента ИЛИ, причем каждая модель вершины содержит схему индикации, а третьим входом этой модели является выход первого элемента НК 123 .Устройство позволяет выделить все максимальные сильно связанные под Э 11349 графы в графе. Однако устройство не позволяет определить входные и выходные вершины каждого максимально сильно связанного подграфа, а также, дуги, которые связывают эти входные и выходные,вершины с другими вершинами графа, т.е, дуги, которые входят в направленный разрез. Под направленным разрезом понимают такой разрез графа, удаление дуг которого 10 поивопит гоаб к несвязным попгоайам.Белью изобретения является расширение функциональных возможностей устройства дня исследования графов, а именно обеспечение дополнительной 15 возможности определения входных и выходньк вершин максимальньк сильно связных подграфов и дуг связыУвающих их с другими вершинами.20Эта цель достигается тем, что в . устройство для исследования графов, содержащее модели вершин, соединенные между собой входными и выходными инфОрмационными полюсами согласно ,.топологии исследуемого графа, блокуправления, сдвиговый регистр и груп-" пу элементов И, первые входы которых соединены с разрядными информацион-, ными выходами сдвигового регистра, вход и выход которого соединены соот-З 0 ветственно с первым выходом и входой блока управления, второй, третий и четвертый выходы которого подключены соответственно к первым, вторым и третьим управляющим входам моделей 35 вершин, четвертые управляющие входы которых соединены с выходами соответствующих элементов И группы, вторые входы которых подключены к управляющим вьпсодам соответствующих моделей 40 вершин, каждая модель вершины содержит шесть элементов И, два элемента ИЛИ, два формирователя одиночных им 1 пульсов, два триггера, первый элемент НЕ и узел индикации, причем первые 45 входы первого и второго элементов И являются соответственно первым и втоРым упРавляющими входами модели вер-. шины, вторые входы первого и второго элементов И объединены и являются 50 четвертым управляющим входом модели вершины, выходы первого и второго эле- ментов И соединены спервьпки входами соответственно первого и второго эле- ментов И 31 И, выходы которьк подкпючены к единичным входам первого и второго триггеров, второй вход первого элемента ИЛИ соединен с выходом тре 46 4тьего элемента И, первый вход кото-рого соединен с нулевым вькодом второго триггера, единичный вькод первого триггера соединен с первым входомчетвертого элемента И, входом первого формирователя одиночных импульсов и первым входом пятого элементаИ, выход которого подключен ко второму входу второго элемента ИЛИ, вькодпервого формирователя одиночных импульсов является выходным информационным полюсом модели вершины и соеди"нен со вторым входом пятого элементаИ, единичный выход второго триггераподключен ко второму входу четвертого элемента И и входу второго формирователя одиночных импульсов, выходкоторого является входным информационным полюсом модели вершины и соединенсо вторым входом третьего элементаИ, выход первого элемента НЕ является управляющим выходом модели вершины,в каждую модель вершины дополнительно введены пять элементов И, триэлемента ИЛИ, третий формировательодиночньк импульсов, третий триггер,три сдвиговых регистра и второй элемент НЕ, блок управления содержитшесть элементов И, три триггера, счетчик импульсов, генератор импульсови элемент ИЛИ, причем в каждой модели вершины первый вход шестого эле-,мента И модели вершины соединен свходным информационным полюсом моделивершины, первый вход седьмого элемента И подключен к выходному информационному полюсу модели вершины, вторые входы шестого и седьмого элементов Имодели вершины и первый вход третьего элемента ИЛИ соединены с единичным вькодом третьего триггера,нулевой. выход которого подключен кпервым входам восьмого и девятогоэлементов И, объединенные вторые входы которых являются пятым управляющим входом модели вершины и соединены со входом второго элемента. НЕ ипервым входом десятого элемента И,третьи. входы восьмого и девятогоэлементов И объединены и подключены к четвертому управляющему. входумодели вершины, вькоды шестого иседьмого элементов И соединены соответственно с информационньпси входамипервого и второго сдвиговых регистров, сдвиговые входы которьк объединены и подключены к выходу десятогоэлемента И, второй вход которого является шестым управляющим входом мо113494 3дели вершины, выход второго элемента НЕ соединен с третьими входами первого, второго, третьего и пятого элементов И модели вершины, четвертый вход третьего элемента И соединен с первым управляющим входом модели вершины, четвертый вход пятого элемента И модели вершины соединен со вторым управгяющим входом модели .вершины, выходы восьмого и девятого 10 элементов И подключены соответственно к входному и выходному информационным полюсам модели вершины, вход первого элемента НЕ модели вершины соединен с выходом третьего элемента 15 ИЛИ, второй вход которого подключен к выходу четвертого элемента И и вхо" ду третьего формирователя одиночных импульсов, выход которого соединен с первым входом четвертого элемента ИЛИ 20 второй вход которого подключен к единичному входу третьего триггера, вы- . ходу третьего сдвигового регистра .и первому входу узла индикации, второй и третий входы которого соединены с 25 выходами соответственно первого и второго сдвиговых регистров, выход четвертого элемента ИЛИ подключен к информационному входу третьего сдви-, гового регистра, сдвиговый вход ко- ЗО торого является третьим управляющим . входом модели вершины, единичный вход первого триггера блока,.управления является входом блока управления и сое,динен с первыми входами первого и второго элементов И блока управления, единичный вькод первого триггера блока управления соединен со вторыми входами первого и второго и первым входом третьего элементов И блока управления, выход первого элемента И блока управления через счетчик импульсов блока управления подключен к нулевому входу первого триггера блока управления, нулевой выход первого. ф, З триггера блока управления соединен с ,первыми входами четвертого, пятого и шестого элементов И блока управления,вторые входы третьего и четвертого- элементов И блокауправления объ- у единенци подключенык первому выходу генератора импульсов,выход третьего элемента И блока управления соединен,с первым входом элемента ИЛИ блока управлейия, выход которого является первыму вькодом блока управления, вькод четвер-,.того элемента И блока управления сое-.динен сб вторым входом элемента ИЛИ 6 6блока управления, единичным входомвторого и нулевым входом третьеготриггеров блока управления, единичные выходы которых являются соответ-,ственно вторым и третьим выходамиблока управления, второй вькод генератора импульсов подключен ко второму входу пятого элемента И блокауправления, вьмод которого соединенс нулевым входом второго и. единичным входом третьего триггеров блокауправления, единичный выход второгои нулевой выход третьего триггеровблока управления подключены соответственно ко второму и третьему входамшестого элемента И блока управлениячетвертый вход которого соединен стретьим выходом генератора импульсов,выходы второго и шестого элементовИ блока управления объединены и являются четвертым выходом блока управления, а единичный вьмод первого триггера блока управления является пятымвыходом блока управления,На фиг. 1 показана функциональнаясхема устройства и функциональнаяохема модели вершиныф на фиг. 2 -функциональная схема блока управления.Устройство дпя исследования. графов содержит модели (1)-1(Ь) вершин исследуемого графа (здесь и вдальнейшем цифрами в скобках обозначены порядковые номера одинаковых посвоему техническому иснопнению блоков,узлов и элементов), блок 2 управления; сдвиговой регистр 3, элементыИ 4(1)-4(й)Каждая модель вершины 1(1)-1(п)содержит триггеры 5-7, элементы И8-17, элементы ИЛИ 18-21, элементы,НЕ 22 и 23, сдвиговые регистры 24-26,формирователи 27-29 одиночного импульса, схему 30 индикации.Блок уйравления 2 (фиг. 2) содержит триггеры 31-33, элементы И 34-,39,.генератор 42 синхронизирующих импульсов входной -информационный полюс43 модели вершины, выходной информа-ционный полюс 44 модели вершины,первый выход 45 блока управления, вто.рой выход 46 блока управления, первыиуправляющий вход 47 модели вершины,четвертый управляющий вход 48 модели вершины, третий выход 49 блока управления, второй управляющий вход50 модели вершины, первый управляю-:щий выход 51 модели вершины, чегвер 7 11349 тый выход 52 блока управления, тре тий управляющий вход 53 модели вершины, вход 54 блока управления, пятый выход 55 блока управления, пятый уп-, равляющий вход 56 модели вершины, ше-. 5 стой управляющий вход 57 модели вершиныеИсходными данными задачи определения входных и выходных вершин максимальных сильно связанных подгра О фов являются результаты решения задачи разложения графа на максимапьные сипьно связанные подграфы. Суть решения задачи:разложения заключается й определении множества вершин Г + х, графа, достигаемых из некоторой вершины х и в определении множества вершин Г х, из которых может быть достигнута вершина х, . При этом множество вершин с(х;), принадлежащих максимальному сильно связанному подграфу, отвечает условиюА, . Ас(х;) =Г х, ПГ х;25Эти исходные данные находятся следующим образом,Первоначально посредством входных43 и выходных 44 информационных полюсов модели вершин 1(1) -1(п) ком-мутируются между собой в соответствии с топологией. исследуемого графа.Сдвиговые регистры 3, 24, 25 26и счетчик 41 обнуляются, Триггеры 5,б, 7, 31, 32, 33 устанавливаются в35нулевое состояние. Установочныешины на Фиг. 1 и фиг. 2 не показаны.Число разрядов всех сдвиговых регистров и счетчика определяется числом, вершин исследуемого графа.Первоначально определяется в граФе множество вершин Гф х достижимых из произвольно выбранной регист"ром 3 вершины х 1. Дляэтого.генератор 42 импульсов выдает импульс ГИ 45на вход элемента И 36. Пройдя его,он поступает через элемент ИЛИ 40 навыход 45 и на вход триггера 31, который устанавливается в единичноесостояние. Единичное состояние триг-.50гера 31 выдает разрешение на полюс46. Это разрешение с полюса 46 блока .управления 2 поступает на входы 47всех моделей, вершин 1(1)-1(п),С выхода 45 блока управления иьпульс ГИ, поступает на вход сдвиго -вого регистра 3. В результате на.первом выходе регистра 43 появляется 46 8разрешение, которое, пройдя элементИ 4( 1), поступает на вход 48 модели вершины,- соецнненной с выходом этого элемента И. Таким образом выбирается вершина хПостроение множества Г х; осуществляется распространением разрешения, поступившего на вход 48 выбранноймодели вершины, по графу. Эторазрешение;в модели вершины с входа48 через элементы И 15 и ИЛИ 21 поступает на вход триггера 7 и устанавливает его в единичное состояние. Единичное состояние триггера 7 выдаетразрешение на входы элементов И 11и И 12 и на вход Формирователя 28 одй-.ночного импульса. Формирователь 28одиночного импульса по этому разрешению формирует одиночный импульс, ко".торый поступает на информационныйполюс 44 модели вершины. Далее иьпульс появляется на информационнЬмполюсе 43 моделей вершин, связанныхс полюсом 44 выбранной модели. Вэтих моделях импульс с полюса 43 через элементы И 13 и ИЛИ,21 поступаетна вход триггера 7 и устанавливаетего в единичное состояние. Таким образом, распространяясь по графу,этот импульс Формирует множествоГ х о чем свидетельствует единичное состояние триггеров 7 моделейвершин,После этого определяется множест.во вершин Г х, Генератор импульсов 42 выдает импульс ГИ, сдвинутыйотносительно импульсов ГИ и ГИ , навход элемента,И 37. Этот импульс ГИ 5,пройдя элемент И 37, устанавливаеттриггер 32 в единичное состояние итриггер 31 - в нулевое. В результатес выхода 46 блока управления 2 разрешение будет снято и, как следствие,оно будет снято с входов 47 всех моделей вершин 1(1)-1(И) . Единичное состояние триггера 32 выдает разрешениена выход 49 блока управления 2. Разрешение с выхода 49 блока управления2 поступает на входы 50 всех моделейвершин 1(1) -1(п),В выбранной ранее модели вершиныс входа 50 разрешение через элементИ 14.и ИЛИ 20 поступает на вход триггера 6 н устанавливает его в единич-ное состояние, которое выдает разре-шение на входы элемента И 1 1 и формирователя 29 одиночного импульса. Поразрешению, поступившему на вход фор11 1134Сигнал с входа 54 в блоке управления 2 поступает на вход триггера33 и устанавливает его в единичное состояние. Единичное состояние триггера 33 снимает разрешение с входов элементов И 36 и 37 и выдает разрешение на вход элементов И 35, 38, 39.Кроме этого,разрешение появляется на выходе 55 блока упрвления 2. Разрешение с выхода 55 блока управления 2 поступает на входы 56 всех моделей вершин 1(1)-1(О) .В процессе метки максимальных сильно связных подграфов производится сдвиг информации, содержащейся в ре-, 15 гистрах 24 сдвига моделей вершин. В, результате на выходе регистров 24 сдвига, принадлежащих моделям вершин, которые вошли в первый подграф, имертся сигнал. Этот сигнал поступает На вход триггера 5, что приводит к установлению его в единичное состоя" ., ние.Сигнал с единичного выхода тригге-, ра 5 поступает на вход элементов И25 8, 9 и ИЛИ 18. С выхода элемента ИЛИ 18сигнал поступает на вход элемента НЕ 22. Этот сигнал инвертируется элемен,том НЕ 22 и поступает на выход 51, .который соединен с входом соответст-.З 0 вующнх элементов И 4(1)-4(сс). Тем самым блокируются входы тех элементов И 4(1)-4(Я), которые соответствуют моделям вершин, принадлежащим первому максимальному сильно связа.- ному подграфу, Это. соответствует опре 35 делению множества вершин Ц С(х),Одновременно с появлением разрешения на выходах 46, 49 и 55 блока управления.2 генератор 42 импульсов 40 выдает импульсы ГИ через элементы И 38 и ИПИ 40 на выход 45 блока управления 2. Импульсы с выхода 45 блока управления 2 поступают на вход сдвигового регистра 3 и на входы 57всех моделей вершин 1(1)-1(с 1).45В моделях вершин импульсы ГИ 1 с .входа 57 через элемент И 10 поступают на сдвиговый вход регистров 25 и, 26 сдвига. При этом разрешение по"ф 50 ступившее из блока управления 2 на вход 56, блокирует входы элементов И 12-15 и разрешает прохождение сигналов через элементы И 10, 16, 17.Импульсы ГИ, поступившие .на вход 5 сдвигового регистра 3, последовательно выдают разрешение на его разряд:ных выходах. Далее разрешение про- . 946 12 ходит через элементы И 4(1)-4 (й) на входы 48 моделей вершин, которые не заблокировали свои элементы И 4(1) 4(й).С входа 48 в каждой модели вершины разрешение поступает на входы элементов И 16 и 17 и проходит через них соответственно на полюса 44 и 43 по мере опроса регистром сдвига 3 всех моделей вершин 1(1)-1(о), что соответствует выполнению условий Г Ц С(х;)ДС(х 1) и Г СС(х,)О С(х). Исключение составляют модели вершин, триггер 5 которьпс находится в единичном состоянии. У них на входах 48 разрешение не появляется и, следовательно, оно не появляется на полюсах 43 и 44.С полюса 44 опрошенной регистром сдвига 3 модели вершины разрешение поступает на полюса 43 моделей вершин связанных с ней. Аналогично разрешение поступает с полюса 43 опрошенной модели вершины на полюса 44 дру-. гих моделей. Если при этом окажется, что опрошенная вершина непосредсгвенно связана с вершиной, в которой триггер 5 нисодился в единичном состоянии, то разрешение с полюса 43 поступает через элемент И 9 на уста новочный вход регистра 26 сдвига, где в соответствующий разряд записывается единица. Этот разряд соот"- ветствует номеру модели вершины, опрошенной сдвиговым регистром 3,Аналогичный процесс происходит, если разрешение поступает с полюса 44, В данном случае оно проходит элемент И 8 и поступает на установоч- ный вход регистра 25 сдвига, где в соответствующий разряд записывается единица;ФЙаличие единицы хогь в одном раз ряде сдвиговьй:регистров 25 или 26 свидетельствуфт. о том, что данная модель вершйвы является входом или выходом максимапьного сильно связ-, ного подграфа. Номера разрядов реги.стров 25 или 26, в которых находится единица, и номер модели вершины, к которым относятся данные регистры,определяюг входные и выходные дугимаксимального,.сильно связного подграфа, т.е. овределяют дуги направленного разреза. -.Процесс определения входных и выходных вершин данного максимального сильно связного подграфа оканчивается13 1134946 ,14 в тот момент когда на выходе сдвиго- обеспечивается выбор вершков нового вого регистра 3 появляется импульс, максимального сильно связного подграЭтот импульс поступает на вход 54 бло- фа. Для устранения потери информации ка управления 2, по которому послед- в сдвиговых регистрах 24 содержимое выний устанавливает триггер 5 моделей ходного разряда через элемент ИЛИ 195. вершин выбранного максимального силь- переносится в первый разряд. но связного подграфа в нулевое сос- В дальнейшем процесс повторяется тояние. аналогично описанному.Далее, блок управления 2 выбирает - Решение задачи оканчивается тогда новый максимальный сильно связный 1 О когда определены все входы и выходы подграф, что осуществляется нмпуль- всех максимальных сильно связных сом, который поступает на вход 54 .подграфов. Об этом свидетельствует блока управления 2. С выхода 49 им- импульс переполнения, который появля. пульс поступает навход;элементов И ется на выходе счетчика 41, который в 35 и 39. Пройдя элемент И 39, он по блокеуправления 2 устанавливает триг.- ступает на вход счетчика 41 и фикси- гер 33 в нулевое состояние. руется в нем. Пройдя элемент И 35, Информация о решении задачи, отоимпульс поступает на выход 52 блока бражаемая схемами 30 индикации моде- управления 2. С выхода 52 блока уп-лей вершин 1(1)-1(О), включает в себяравпения 2 он поступает на входы 53 2 О номера максимальных сильно связных всех моделей вершин 1(1)-1(й) и да- подграфов, к которым относится та или лее - на сдвиговый вход сдвиговых ре- иная модель вершины, номера вершин, гистров 24, что обеспечивает сдвиг из которых выходят или в которые вхона один разряд их содержимого. Этим дят связываюшде дуги.