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

нами, в каждую модель вершины дополнительно введены пять элементов И, три элемента ИЛИ, третий формировдтель одиночных иыпульсов, третий триггер, три сдвиговьк регистра и второй элемент НЕ, блок управления содержит шесть элементов И, три триггера, счетчик импульсов, генератор импульсов и элемент ИЛИ, причем в каждой модели вершины первый вход шестого элемента И модели вершины соединен с входным информационным полю сом модели вершины, первый вход седьмого элемента И подключен к выходному информационному полюсу модели вершины, вторые входы шестого и седьмого элементов И модели вершины и первый вход третьего элемента ИЛИ соединены с единичным выходом третьего триггера, нулевой выход которого подключен к первым входам восьмого и де.витого элементов И,объединенные вторые входы которых являются пятым управляющим входом модели вершины и соединены со входом второго элемента НЕ и первым входом десятого элемента И, третьи входы восьмого и девятого . элементов И объединены и подключены к четвертому управляющему входу модели вершины, выходы шестого и седьмого элементов И соединены соответственно с информационными входами первого и второго сдвиговых регистров, сдвиговые входы которых объединены и подключены к выходу десятого эле мента И, второй вход которого является шестым управляющим входом модедш вершины, выход второго элемента НЕ . соединен стретьими входами первого, второго, третьего и пятого элементов И модели вершины, четвертый вход «третьего элемента И соединен с nep-sJ вьм управляющим входом модели вершины, четвертый вход пятого элемента И модели вершины соединен со вторьм управляющим входом модели вершины, выходы восьмого и девятого элементов . И подключены соответственно к входному и выходному информационным полюсам модели вершины, вход первого элемента НЕ модели вершимы соединен

:С выходом третьего элемента ИЛИ, второй вход которого Подключен к выходу четвертого элемента И и входу третьего формирователя одиночных импульсов, выход которого соединен с первым входом четв ертого элемента ИЛИ, второй вход которого подключен к единичному

входу третьего триггера, выходу третьего сдвигового регистра и первому входу уэла индакации, второй и трети входы которого соединены с выходами соответственно первого и второго сдвговых регистров, выход четвертого элемента ИЛИ подключен к информационному входу третьего сдвигового регистра, сдвиговый вход которого является третьим управляющим входом модели вершины, единичный вход первого триггера блока управления является входом блока управления и соединен с первыми входами первого и второго элементов И блока управления, единичный выход первого триггера блока управления соединен со вторыми йходами первого и второго и первым входом . третьего элементов И блока управления, выход первого элемента И блока управления череэ счетчик импульсов блока управления подключен к нулевому входу первого триггера блока управления, нулевой вькод первого триггера блока управления соединен с первыми входами четвертого, пятого и шестого элементов И блока управления, вторые входы третьего и ч.етвертого элементов И блока управления объединены и подключены к первому выходу генератора импульсов, выход третьего элемента И блока управления соединен с первым входом элемента ИЛИ блока управления, выход которого является первым выходом блока управления, выход четвертого элемента И,блока управления соединен со вторым входом элемента ИЛИ блока управления, единичным входом второго и нулевым входом третьего триггеров блока управления, единичные выходы которых являются соответственно вторым и третьим вькодами блока управления, второй выход генератора импульсов подключен ко второму вхду пятого элемента И блока управления, выход которого соединен с нулевым входом .второго и единичным входом третьего триггеров блока управления, един11чный выход второго и нудевой выход третьего триггеров блока управления подключены соответственно I ко второму и третьему входам шестого элемента И блока управления, четвертый вход которого соединен с третьим выходом г ёнератора иктульсов, выходы второго и щестого элементов ,И блока управления объединены и являются четвертым выходом блока упаравления , вого триггера единичный выход пер- является пятым выходом блока упблока управления 1134946 равления.

УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФОВ, содержащее модели вершин, ;соединенные между собой входными и ;выходнь1ми информационными полнх ами ргласно топологии исрледуемого гра:фа,блок управления,сдвиговый регистр и группу элементов И, первые входь) которых соединены с разрядными информационными выходами сдвигового регистра,1 вход и выход которого соединены соответственно с первым выходом и входом блока управления, вто-. рой, третий и четвертый выходы которого подключены соответственно к первым, вторым и третьим Управляющим входам моделей вершин, четвертые управляющие входы которых соединены с выходами соответствующих элементов И группы, вторые входы которых подключены к управляющим выходам соответствующих моделей вершин, каждая модель вершины содержит шесть эле- . ментов И, два элемента ИЛИ, два мирователя одиночных импульсов,два триггера, первый элемент НЕ и узел индикации, причем nepmite входы первого и второго элементов И являются соответственно первым и вторым управляющими входами модели вершины, вторые входы первого и второго элементов И объединены и являются четвертым управляющим входом модели верщины, выходы первого и второго элементов И соединены с первыми входами соответственно первого и в орого элементов ШШ, выходы которых подключены к единичным входам первого и второго триггеров, второй вход первого элемента ИЛИ соединен с выходом третьего элемента И, первый вход которого соединен с нулевым выходом второго триггера, единичный выход первого триггера соединен с первым входом четвертого элемента И, входом первого формирователя одиноч.ных импульсов и первьм входом пятого элемента И, выход которого подключен iко второму входу второго элемента ИЛИ, выход первого формирователя одиночных импульсов я яется выходным информационным полюсом модели вер шяиы и соединен со вторьм входом пятого элемента И, единичный вы:«э ход второго триггера подключен к второму входу четвертого элемента И и входу второго фop вIpoвaтeля одиночных импульсов, выход которого яв9 ляется входным информа1щонш 1м полюсом модели вершины и соединен со вторым входом третьего элемента И, выход первого элeмeнta НЕ является управляющим выходом модели вершины, офличающееся тем, что, с целью расширения функциональных возможностей устройства эа счет опреде:Ления входных и выходных вершин максимальных сильно связных подграфов и дуг, связываю1цих их с другими верши

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

Известно устройство для исследования графов, содержащее модели вершин, соединенные между собой согласно 5 топологии исследуемого графа,регистр, вход и первый выход которого подключены к первому выходу и входу блока управления, второй, третий и четверр 10 тый выходы которого соединены соот ветственно с первым, вторым и третьим входами моделей вершин, информационные выходы регистра соединены с первыми входами элементов И группы, второй вход каждого из которых под- 5 ключен к первому выходу соответствующей модели вершины, выходы элементов И группы подключены соответственно к четвертым входам моделей вершин, каждая из которых содержит первый 0 триггер, первый элемент ИЛИ, первый элемент И ij . Однако такое .устройство не позволяет произвести разложение графа на максимальные сильно связные подграфы.

Наиболее близким по технической . сущности к данному изобретению является устройство, содержащее модели вершин, число которых соответствует числу вершин исследуемого графа блок 30 управления, сдвиговый регистр, вход и выход которого соответственно соединены с первым и вторым полюсами блока управления, а выход каждого разряда сдвигового регистра соединен с 35 первым входом соответствукяцего первого элемента И, число которых равно числу моделей вершин, второй вход каадого элемента И соединен с третьим входом соответствующей ему моде- 40 ли вершины, у которой четвертый и пятый входы соответственно подключе|1ы к третьему и четвертому выходам блока управления, пятый выход которого соединен с шестыми входами всех 45 моделей вершин, причем модели вершин первым и вторым своими полюсами соедннены между собой в соответствии с топологией исследуемого графа, а седьмой вход каждой модели вершины соединей с выходом соответствующего ей первого элемента И, при этом седьмой вход в каждой модели вершины образован соединением первых входов второго и третьего элементов И, у которых вторые входы соответственно являются четвертым и пятым входами модели вершинь, а выходы второго и третьего элементов И соединены с первыми входами соответственно первого и второго элементов ШШ, при этом вторые входы этих элементов ИЛИ соединены с выходами соответственно четвертого и пятого элементов И, причем выход первого элемента ИЛИ соединен с входом первого триггера, единичный выход которого соединен с входом первого формирователя одиночного импульса, выход Которого соединен с первым входом пятого элемента И и является вторым полюсом модели вершины, с вторым входом пятого элемента И, третий вход которого подключен к пятому входу модели вершины, и первым входом шестого элемента И, второй вход которого соединен с входом шестого элемента И, второй вход которого соединен с входом второго формирователя одиночного импульса, выход которого соединен с яервьп4 входом четвертого элемента И, второй вход которого подклйчен к четвертому,входу модели вершины, и является первым полюсом модели вершины, и с единичным выходом вто рого триггера, у которого нулевой выход и единичный вход соответственно соединены с третьим входом чет вертого элемента Икс выходом; второго элемента ШШ, причем каждая модель вершины содержит схему индикации, а третьим входом; этой модели является выход первого элемента НЕ 2.

Устройство позволяет вьщеяить все максимальные сильно связанные подграфы в графе. Однако устройство не позволяет определить входные и выходные верпшны каждого максимально сильно связанного подграфа, а также дуги, которые связывают эти входные и выходные,вершины с другими вершинами графа, т.е. дуги, которые входят в направленный разрез. Под напра ленным разрезом понимают такой разрез графа, удаление дуг которого поивопит граф к несвязным попгоаАам Целью изобретения является расширение функциональных возможностей устройства для исследования графов, а имеино обеспечение дополнительной возможности определения входных и выходных вершин максимальных сильно связных подграфов и дуг. связывающих юс с другими вершинами. Эта цель достигается тем, что в устройство для исследования графов, содержащее модели вершин, соединенные между собой входными и выходными информационными полюсами согласно , Т.ОПОЛОГИИ исследуемого графа, блок... управления, сдвиговый регистр и груп пу элементов И, первые входы которых соединены с разрядными информационными выходами сдвигового регистра, вход и выход которого соединены соот ветственно с первым выходом и входой блока управления, второй, третий и четвертый выходы которого подключены соответственно к первым, вторым и третьим управляющим входам моделей вершин, четвертые управляющие входы которых соединены с выходами соответ ствующих элементов-И группы, вторые входы которых подключены к управляющим выходам соответствующих моделей верпшн, каждая модель вершины содержит шесть элементов И, два элемента ИЛИ, два формирователя одиночных импульсов, два триггера, первый элемен НЕ и узел индикации, причем первые входы первого и BTOpioro элементов И являются соответственно первым и вто рым управляющими входами модели вер шины, вторые входы первого и второго элементов И объединены и являются четвертым управляющим входом модели вершины, выходы первого и второго эя ментов И соединены с первыми входами соответственно первого и второго эле ментов ШШ, выходы которых подкпю11ены к единичным входам первого и второго триггеров второй вх.од первого элемента ШШ соединен с выходом третьего элемента И, первый вход которого соединен с нулевым выходом второго триггера, единичный выход первого триггера соединен с первым входом четвертого элемента И, входом первого формирователя одиночных импульсов и первым входом пятого элемента И, выход которого подключён ко второму входу второго элемента ИЛИ, выход первого формирователя одиночных импульсов является выходным информационным полюсом модели вершины и соединен со вторым входом пятого элемента И, единичный выход второго триггера подключен ко второму входу четвер- того элемента И и входу второго формирователя одиночных импульсов, выход которого является входным информационным полюсом модели вершины и соединен со вторым входом третьего элемента. И, выход первого элемента НЕ является управляющим выходом модели вершины, в каждую модель вершины дополнительно введены пять элементов И, три элемента ИЛИ, третий формирователь одиночных импульсов, третий триггер, три сдвиговых регистра и второй элемент НЕ, блок управлений Ьодержит шесть элементов И, три триггера, счетчик импульсов, генератор импульсов и элемент ИЛИ, причем в каждой модели вершины первьй вход шестого эле- мента И модели вершины соединен с входньм информационным полюсом модели вершины, первый вход седьмого элемента И подключен к выходному информационному полюсу модели вершины, вторые входы шестого и седьмого элементов И модели вершины и первый вход третьего элемента ИЛИ соединены с единичным выходом третьего триггера. Нулевой выход которого подкпючен к первым входам восьмого и девятого элементов И, объединенные вторые входы которых являются пятым управляющим входом модели вершины и соединены со входом второго элемента НЕ и первым входом десятого элемента И, третьи.входы восьмого и девятого элементов И объединены и подключены к четвертому управлякяцему .входу модели верпшны, выходы шестого и седьмого элементов И соединены соответственно с информационньвш входами первого и второго сдвиговых регист ров, сдвиговые входы которых объединены и подключены к выходу десятого элемента И, второй вход которого является шестым управляющим входом модели вершины, выход второго элемента НЕ соединен с третьими входами первого, второго, третьего и пятого элементов И модели вершины, четвертый вход третьего элемента И соединен с первым управляющим входом модели вершины, четвертьй вход пятого элемента И модели вершины соединен со .вторым управляющим входом модели вершины, выходы восьмого и девятого элементов И подключены соответственно к входному и выходному информационным полюсам модели вершины, вхоД первого элемента НЕ модели вершины соединен с выходом третьего элемента ИЛИ, второй вход которого подключен к выходу четвертого элемента И и входу третьего формирователя одиночных импульсов, выход которого соединен с первым входом четвертого элемента ИПИ второй вход которого подключен к единичному входу третьего триггера, выходу третьего сдвигового регистра .и первому входу узла индикации, второй и третий входы которого соединены с выходами соответственно первого и второго сдвиговых регистров, выход . четвертого элемента ИЛИ подключен к информационному входу третьего сдвит Гового регистра, сдвиговый вход ко-: торого является третьим управляющим входом модели вершины, единичный вход первого триггера блока,управления является входом блока управления и сое:динен с первыми входами первого и второго элементов И блока управления единичный выход первого триггера блока управления соединен со вторыми входами первого и второго и первым входом третьего элементов И блока управления, выход первого элемента И блока управления через счетчик импульсов блока управления подключен к нулевому входу первого триггера блока управления, нулевой выход первого., :триггера блока управления соединен с первыми входами четвертого, пятого . и шестого элементов И блока управлеНИЛ,вторые входы третьего и четвертого элементов И блока управления объединены и подключены к первому выходу генератора иыпульсов;выход третьего элемента И блока упр авления соединен ,с первым входом элемента ИЛИ блока управлеЬия, выход которого является пербым выходом блока управления, выход четвер:того элемента И б,пока управления соединен с d вторым входом элемента ИЛИ

блока управления, единичным входом второго и нулевым входом третьего триггеров блока управления, единичные выходы которых являются соответ-. ственно вторым и третьим выходами блока управления, второй выход генератора импульсов подключен ко второму входу пятого элемента И блока управления, выход которого соединен с нулевым входом второго и единичным входом третьего триггеров блока управления, единичный выход второго и нулевой выход третьего триггеров блока управления подключены соответ ственно ко второму и третьему входам шестого элемента И блока управления четвертый вход которого соединен с третьим выходом генератора импульсов, выходы второго и шестого элементов И блока управления объединены и являются четвертым выходом блока управления, а единичный выход первого триггера блока управления является пятым выходом блЬка управления.

На фиг. 1 noKiaaaHa функциональная схема устройства и функциональная

: схема модели вершины, на фиг. 2 функциональная схема блька управления

Устройство дпя исследования графов содержит модели i(1)-1{t)) вершин исследуемого графа (здесь и в дальнейшем цифрами в скобках обозначены порядковые номера одинаковых по своему техническому исполнению блоков

узлов и элементов)J блок 2 управления, сдвиговой регистр 3, элементы И 4(1)-4(h).

Каждая модель вершины 1(1)-1(п) содержит триггеры 5-7, элементы И 8-17, элементы ИЛИ 18-21, элементы ,

НЕ 22 и 23, сдвиговые регистры 24-26, формирователи 27-29 одиночного импуль са, схему. 30 индикации. .

Блок управления 2 (фиг. 2) содержит триггеры 31-33, элементы И 34т39, элемент ИЛИ 40, сч етчик 41 юшул ьс ов, генератор 42 синхронизирующих импуль|сюв, .входной-информационный полюс 43 модели вершины, выходной информа-:циояный полюс 44 модели вершины, первый выход 45 блока управления, вто:рьй выход 46 блока управления, первый управляклций вход 47 модели верлганы, четвертый управляющий вход 48 модели вершины, третий выход .49 блока управления, второй управляющий вход 50 модели вершины, первый управляющий выход 51 модели вершины, четвер71тый выход 52 блока управления, тре тий управляющий вход 53 модели верши ны, вход 54 блока управления, пятый выход 55 блока управления, пятьА управляющий вход 56 модели вершины, ше стой управляющий вход 57 модели верпшны. Исходными данньюи задачи определения входных и выходных вершин максимальных сильно связанных подграфов являются результаты решения задачи разложения графа на максимальные сильно связанные подграфы. Суть решения задачи разложения заключается и определении множества вершин Г + XJ графа, достигаемых из некоторой вершины х;, и в определении множества вершин , из которых может быть достигнута вершина xj . При этом множество вершин с(х|), принадлежащих максимальному сильно связанному подграфу, отвечает условию с(х.) Г х- ПГ X ,, Эти исходные данные находятся сле дующим образом. . Первоначально посредством входных 43 и выходных 44 информационных полюсов модели вершин 1(1)-1(п) коммутируются между собой в соответствии с топологией исследуемого графа. Сдвиговые регистры 3, 24, 25, 26 и счетчик 41 обнуляются. Триггеры 5, 6, 7, 31, 32, 33 устанавливаются внулевое состояние. Установочные шины на фиг. 1 и фиг. 2 не показаны Число разрядов всех сдвиговых регист ров и счетчика определяется числом вершин исследуемого графа. Первоначально определяется в графе множество вершин г х| , достижи,: мьк из произвольно выбранной регистром 3 вершины Xj. Для этого.генератор 42 импульсов выдает импульс ГИ на вход элемента И 36. Пройдя его, он поступает через элемент ИЛИ 40 на выход 45 и на вход триггера 31, который устанавливается в единичное состояние. Единичное состояние тригт гера 31 выдает разрешение на полюс 46. Это разрешение с полюса 46 блока угфавления 2 поступает на входы 47 всех моделей вершин 1(1)-1(п). С выхода 45 блока управления имиульс га, поступает на вход сдвигового регистра 3, В результате на первом выходе регистра 43 появляется 68 разрешение, которое, пройдя элемент И 4(1), поступает на вход 48 модели вершины,- соединенной с выходом этого элемента И. Таким образом выбирается вершина х. - д Построение множества Г х, осу-, ществляется распространением разрешения, поступившего на вход 48 выбранной модели вершины, по графу. Это разрешение;в модели вершины с входа. 48 через элементы И 15 и ИЛИ 21 поступает на вход триггера 7 и устанавливает его в единичное состояние. Единичное состояние триггера 7 вьщает разрешение на входы элементов И 11 и И 12 и на -вход формирователя 28 одйг ночного импульса. Формирователь 28 одиночного импульса по этому разрешению формирует одиночный импульс, который поступает на информационньй полюс 44 модели вершины. Далее им- ; пульс появляется на.информационнбм полюсе 43 моделей вершин, связанных с полюсом 44 выбранной модели. В , этих моделях импульс с полюса 43 через элементы И 13 и ИЛИ,21 поступает на вход триггера 7 и устанавливает его в единичное состояние. Таким образом, распространяясь по графу, тот импульс формирует множество , о чём свидетельствует единин- ное состояние триггеров 7 моделей вершин. После этого определяется множест- . .во вершин Г xj . Генератор импульсов 42 выдает импульс ГИ, сдвинутый относительно импульсов ГИ и ГИ-, на вход элемента,И 37i Этот импульс ГИ, пройдя элемент И 37, устанавливает триггер 32 в единичное состояние и триггер 31 - в нулевое. В результате с выхода 46 блока управления 2 разрешение будет синто и, как Следствие, оно будет снято с входов 47 всех моделей вершин 1(1)-1(П). Единичное состояние триггера 32 вцдает разрешение на выход 49 блока управления 2. Разрешение с выхода 49 блока управления 2 поступает на входы 50 всех моделей вершин 1(1)-1(п). В выбранной ранее модели вершины с входа 50 разрешение через элемент И 14 и ИЛИ 20 поступает на вход триггера 6 и устанавливает его в единичное состояние которое выдает разрешение на входы элемента И 11 и формирователя 29 одиночного импульса. По разрешению, поступившему на вход фор9113мирователя 29 одиночного импульса, на его выходе пояйляется импульс, ко1торый поступает на информационный ( полих: 43 выбранной модели вершины. С полюса 43 выбранной модели вершины импульс поступает на полюс 44 мрделей вершин, связанных с полюсом 43 выбранной модели. В этих моделях импульс с полюса 44 через злементы И 12 и ИЛИ 20 поступает на вход триггера 6, который устанавливает в единичное состояние. Таким образом j распространяясь по графу этот импульс формирует множество Г х; о чем свидетельствует единичное состояние триггеров 6 м оделей 1рершин, Построение множеств Г Г . xj в моделях вершин Кt)-1(n) триггеров 6 и 7, одновременно находящихся в единичном состоянии, свидетельству-, ет о том, что соответствующие им вершины графа принадлежат максимальному сильно связному подграфу, одной из вершин которого является выбранная распределителем импульсов верт шина XJ. Метка сформированного максималь-. ного сильно связного подграфа осуществляетря разрешением, снимаемым . с выхода элемента И 11. Это разреше-, ние поступает на вход формирователя

27 одиночного импульса, который формирует одиночный импульс. Этот импульс поступает на установочный вход сдвигового регистра 24. В первом разряде сдвигового регистра 24 записывается единица.

: Как только будет помечен и сфор.мирован максимальный сильно связный подграф, блок управления 2 снимает разрешение с входов 50 всех моделей вершин 1(1)-1(п) и переходит к формированню новых максимальных сильно связных подграфов. Искл очение из дальнейшего рассмотрения вершин, принадлежащих уже сфор рованн пoдSa .фам, осуществляется.путем- инвертирования элементом НЕ 22 сигнала, поступающего с выхода злемента И 11 чере элемент ИЛИ 18. Этот инвертированный сигнал nocTynaet на выход 51, снимая разрешение с выходов соответствующих элементов И 4(Т)-И 4(п). В д1альнейшем блок управления 2 устанавливает триггеры 6 и 7 в нулевое состояние у тех моделей верпнн, которые не принадлежат сформированному подграфу, после чего блок управ

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

Суть решения задачи определения входных и выходных вершин максимальных сильно связных подграфов заключается в выборекакого-либо макси- ; 610 . ления 2 производит аналогичным образом выбор новой модели вершины и процесс формирования нового-максимального сильно связного подграфа повторяется. При этом блок управления 2 производит сдвиг содержимого регистров 24. Это происходит по импульсу FHj, сдвинутому относительно ГИ, генератора импульсов 42, который через элемент И 34 поступает на выход 52 блока управления 2 .и далее - на входы 53 всех моделей вершин 1(1)-1(п). В моделях вершин с входа 53 импульс ГИ поступает на сдвиговый вход регистра 24 модели вершины. Процесс разложения графа на максимальные сильно связные подграфы заканчивается только в том случае, когда на выходе сдвигового регистра 3 появляется сигнал, который поступает на вход 54 блока управления 2. Это свидетельствует о том, что все максимальные сильно связные подграфы в графе сформированы. Номер разряда, который, находится в единичном состоянии, сдвигового регистра 24 моделей вершин 1(1)-1(п) определяет номер максимального сильно связного подграфа, к которому относится та или иная вершина графа. Эта информация мального сильно связного подграфа C(xi), в определении (x, Л и, С(х)7 и в пометке вершин, удовлетворяющих услош1ям г-Гл / п,«( ..+Р i , -« « Г (х01осиО. Первыепомеченные вершины являют ся входными вершинами максимального сильно связного подграфа, а вторые выходными Процесс решения этой задачи паякнается с момента поступления сигнала с выхода сдвигового регистра 3 на вход 54 блока управления 2. По этому сигналу блок управления 2 устанавливает все триггеры 6 и 7 всех моделей вервия и триггеры 31 и ЗЙ в нулевое состояние. 1 Сигнал с входа 54 в блоке управлеяия 2 поступает на вход триггера 33 и устанавливает его в единичное состояние. Единичное состояние триггера 33 снимает разрешение с входов эленентов И 36 и 37 и выдает разреше ние на вход элементов И 35, 38, 39. Кроне этого, разрешение появляется на выходе 55 блока упрвления 2 Разрешение с выхода 55 блока управления 2 поступает на входы 56 всех моделей вершин 1(1)-1(п). В процессе метки максимальных сил но связных подграфов производится сдвиг информации, содержащейся в регистрах 24 сдвига моделей вершин. В результате на выходе регистров 24 сдвига, принадлежащих моделям верямн которые вошли в первый подграф, имеется сигнал. Этот сигнал поступает ha вход триггера 5, что приводит к установлению его в единичное состояние, . Сигнал с единичного выхода трйгге ра 5 поступает на вход элементов И 8, 9 и ИЛИ 18. С выхода элемента ИЛИ 18. сигнал поступает на вход элемента НЕ 22, Этот сигнал инвертируемся элемен . том НЕ 22 и поступает на выход 51, который соединен с входом соответствующих элементов И 4(1)-4(Ю. Тем самым блокируются входы тех элементов И 4(1)-4(п), которые соответствуют моделям вершин, принадлежащем первому максимальному сильно связагному подграфу. Это.соответствует определению множества верпЁнн С(х), Одновременно с появлением разрешения на выходах 46, 49 и 55 блока управления 2 генератор 42 импульсов выдает импульсы ГИ через элементы И 38 и ИЛИ 40 на выход 45 блока управления 2, Импульсы с выхода 45 блока управления 2 поступают на вход сдвигового регистра 3 и на входы 57 всех моделей вершин 1(1)-1(Н). В моделях вершин импульсы ГИ с :входа 57 через элемент И 10 поступают на сдвиговьй вход регистров 25 26 сдвига. При этом разрешение, поступившее из блока управления 2 на вход 56, блокирует входы элементов И 12-15 и разрешает прохождение сигналов через элементы И 10, 16, 17. Штульсы ГИ, поступившие. на вход сдвигового регистра 3, последователь но выдают разрешение на его разряд. ных выходах. Далее разрешение про6ходит через элементы И 4(1)-4 (п) на шсоды 48 моделей вершин, которые не заблокировали свои элементы И 4(1) С входа 48 в каждой модели вершины разрешение поступает на входы элементов И 16 и 17 и проходит через них соответственно на полюса 44 и 43 по мере опроса регистром сдвига 3 всех моделей вершин 1(1)-1(п), что соответствует выполнению условий С(х;)лС(хр и Г (x|)n С(хр . Исключение составляют модели вершин, триггер 5 которых находится в единич о состоянии. У них на входах 48 разрешение не появляется и, следовательно, оно не появляется на полюсах 43 и 44. С полюса 44 опрошенной регистром сдвига 3 модели вершины разрешение поступает на полюса 43 моделей вершин связанных с ней. Аналогично разрешение поступает с полюса 43 опрошен ной модели вершины на йолюса 44 дру-г ; модблей. Если при этом окажется что опрошенная вершина непосредственно связана с вершиной, в которой триггер 5 наз одился в единичном срс;тоянии, то разрешение с полюса 43 через элемент И 9 на установочный вход регистра 26 сдвига, где в соответствующий разряд записывается единица. Этот разряд соот- ; ветствует номеру модели вершины, опошенной сдвиг овым регис тром 3, Аналогичный процесс происходит, если разрешение поступает с полюса 44. В данном слзчае оно/прохрдйт . элемент И 8 и поступает на установочный вход регистра 25 сдвига, где в соответствую1Я нй разряд записывается единица ; аличие единицы хоть в одном разт ряде сдвиговый регистров 25 или 26 свидетельству о том, что данная модель вершины является входом или выходом максимального сильно связного подграфа. Номера разрядов регистров 25 или 26, в которых находится единица, и номер модели вершины, к которым относятся.данные регистры, . определяют оаные и выходные дуги максимального сильио связного подграфа, т.е. о%.еделяют дуги направленного раЬреза.. (г Процесс определения входных и выходных вершин данного максимального сильно связного подграфа оканчивается в тот момент, когда на выходе сдвиго вого регистра 3 появляется иьтульс. Этот импульс поступает на вход 54 бл ка управления 2, по которому последний устанавливает триггер 5 моделей вершин выбранного максимального силь но связного подграфа в нулевое сос-тояние , Далее, блок управления 2 выбирает новый максимальный сильно связный подграф, что осуществляется импульсом, который поступает на вход 54 блока управления 2. С выхода 49 импульс поступает на вход .элементов И 35 и 39. Пройдя элемент И 39, он поступает на вход счетчика 41 и фиксируется в нем. Пройдя элемент И 35, импульс поступает на выкод 52 блока управления 2. С выхода 52 блока управления 2 он поступает на входы 53 всех моделей вершин 1(1)-1(п) и далее - на сдвиговый вход сдвиговых ре гистров 24, что обеспечивает сдвиг HIL один разряд их содержимого. Этим 1 46 . . обеспечивается выбор вершин нового максимального сильно связного подграфа. Для устранения потери информации в сдвиговых регистрах 24 содержимое выходного разряда через элемент ИЛИ 19 переносится в первый разряд. В дальнейшем процесс повторяется аналогично описанному. Решение задачи оканчивается тогда когда определены всё входы и выходы всех максимальных сильно связных .подграфов. Об этом свидетельствует импульс переполнения, который появляется на выходе счетчика 41, который в |блокё управления 2 устанавливает тригг тер 33 в нулевое состояние. Информа1Шя о решении задачи, отображаемая схемами 30 индикации моделей вершин 1(1)-1(П), включает в себя номера максимальных сильно связных подграфов, к которым относится та или иная модель вершины номера вершин, из которых выходят или в которые входят связывающие дуги.

5S 9

s

и

Чв

36

i Sj f

ЙОЕ

54

0J

(Put. 2