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

 

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

СОЮЗ СОЮЕТСНИХ

Э

РЕСПУБЛИК (3Е (И) 4(51 G 06 F 15/20

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

И ЬВ ТЕЛ СИ СЕЛУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОЧНРЬПЪЙ (21) 3577774/24-24 (22) 1.5.04.83 (46) 15.01.85. Бюп. У 2 (72) Г.В.Бондаренко, Л.ОВМакогонюк ,й Н.В.Федотов (71) Институт проблем моделирования в энергетике АН УССР ,(53) 681.333(088.8) (56) 1. Авторское свидетельство СССР к 408312, кл. G 06 F 15/20, 1971.

2. Авторское свидетельство СССР ,У 643880, кл. G 06 F 15/20, 1975 (прототип) .. (54) (57) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ, содержащее модели вершин, соединенные между собой входными и

:выходными информационными полюсами согласно топологии исследуемого графа,блок управления,сдвиговый регистр и группу элементов И, первые входь1 которых соединены с разрядными информацнонньвы выходами сдвигового

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

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

I элеменга И, выход которого подключен

; ко второму входу второго элемента

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

И и входу второго формирователя одиночных импульсов, выход которого является входным информационным полюсом модели вершины и соединен со вторым входом третьего элемента И, выход первого элемента НЕ является уп- а, равляющим выходом модели вершины, о Ф л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства sa счет определения входных и выходных вершин максимальных сильно связных подграфов и дуг, связывающих их с другими верши34946

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

НЕ и первым входом десятого элемента

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

И модели вершины, четвертый вход третьего элемента И соединен с пер= вым управляющим входом модели вершины, четвертый вход пятого элемента И модели вершины соединен со вторым уйравляющим входом модели вершины, выходы восьмого и девятого элементов

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

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

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

Известно устройство для исследования графов, содержащее модели вер- . шин соединенные между собой согласно

Э топологии исследуемого графа,-регистр J вход и первый выход которого подключены к первому выходу и входу блока управления, второй, третий и четвер I0 тый выходы которого соединены соответственно с первым, вторым и третьим входами моделей вершин, информационные выходы регистра соединены с первыми входами элементов И группы, второй вход каждого из которых под15 ключен к первому выходу соответст вующей модели вершины, выходы элементов И группы подключены соответственно к четвертым входам моделей вершин, каждая из которых содержит первый триггер, первый элемент ИЛИ, первый элемент И f1) .

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

Наиболее близким по технической. сущности к данному изобретению является устройство, содержащее модели вершин, число которых соответствует числу вершин исследуемого графа, блок управления, сдвиговый регистр, вход и выход которого соответственно соединены с первым и вторым полюсами блока управления, а выход каждого раз-. ряда сдвигового регистра соединен с первым входом соответствующего первого элемента И, число которых равно числу моделей вершин, второй вход каждого элемента И соединен с третьим входом соответствующей ему моде- 40 ли вершины, у которой четвертый и пятый входы соответственно подключены к третьему и четвертому выходам блока управления, пятый выход которого соединен с шестыьы входами всех, 45 моделей вершин, причем модели вершин первым и вторым своими полюсами соеди

I иены между собой в соответствии с топологией исследуемого графа, а седьмой вход каждой модели вершины .соединей с выходом соответствующего ей первого элемента И, при этом седь|мой вход в каждой модели вершины образован соединением первых входов второго и третьего элементов И, у которых вторые входы соответственно являются четвертым и пятым входами модели вершинь1, .а выходы второго и третьего элементов И соединены с первыми входами соответственно первого и второго элементов ИЛИ, при этом вторые вхо) ы этих элементов ИЛИ соединены с выходами соответственно четвертого и пятого элементов И, причем выход первого элемента ИЛИ соединен с входом первого триггера, единичный выход которого соединен с входом первого формирователя одиноч-. ного импульса; выход которого соединен с первым входом пятого элемента

И и является вторым полюсом модели вершины, с вторым входом пятого элемента И, третий вход которого подключен к пятому входу модели вершины, и первым входом шестого элемента И, второй вход которого соединен с входом шестого элемента И, второй вход которого соединен с входом второго формирователя одиночного импульса, выход которого соединен с жервым входом четвертого элемента И, второй вход которого подключен к четвертому, входу модели верши-! ны, и является первым полюсом модейи вершины, и с единичным выходом вто рого триггера, у которого нулевой выход и единичный вход соответственно соединены с третьим входом четвертого элемента И и с выходом второго элемента KIN, причем каждая модель вершины содержит схему индикации, а третьим входом этой модели является выход первого элемента НЕ (23 .

Устройство позволяет выделить все максимальные сильно связанные подЭ 1f349 графы в графе. Однако устройство не позволяет определить входные и выходные вершины каждого максимально сильно связанного подграфа, а также . дуги, которые связывают эти входные и выходные, вершины с другими вершинами графа, т.е. дуги, которые входят в направленный разрез. Под направленным разрезом понимают такой разрез графа, удаление дуг которого f0 поивопит гоаб к несвязным попгоайам.

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

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

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

НЕ и узел индикации, причем первые 45 входы первого и второго элементов И являются соответственно первым и вторым управляющими входами модели вер- шины, вторые входы первого и второго элементов И объединены и являются 50 четвертым управляющим входом модели вершины, выходы первого и второго эле- ментов И соединены с первыми входами соответственно первого и второго эле- ментов HJIH, выходы которьк подкпюче- SS ны к единичным входам первого и второго триггеров, второй вход первого элемента ИЛИ соединен с выходом тре46 4 тьего элемента И, первый вход кото- рого соединен с нулевым вькодам второго триггера, единичный вькод первого триггера соединен с первым входом. четвертого элемента И, входом первого формирователя одиночных импульсов и первым входом пятого элемента

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

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

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

Э дели вершины, выход второго элемента

НЕ соединен с третьими входами первого, второго, третьего и пятого элементов И модели вершины, четвертый вход третьего элемента И соединен с первым управляющим входом модели вершины, четвертый вход пятого элемента И модели вершины соединен со вторым управгяющим входом модели вершины, выходы восьмого и девятого 10 элементов И подключены соответственно к входному и выходному информационным полюсам модели вершины, вход первого элемента HE модели вершины соединен с выходом третьего элемента 15

ИЛИ, второй вход которого подключен к выходу четвертого элемента И и входу третьего формирователя одиночных импульсов, выход которого соединен с первым входом четвертого элемента ИЛИ 20 второй вход которого подключен к единичному входу третьего триггера, выходу третьего сдвигового регистра .и первому входу узла индикации, второй и третий входы которого соединены с 25 выходами соответственно первого и второго сдвиговых регистров, выход четвертого элемента ИЛИ подключен к информационному входу третьего сдви-, гового регистра, сдвиговый вход ко- ЗО торого является третьим управляющим . входом модели вершины, единичный вход первого триггера блока, управления является входом блока управления и сое,динен с первыми входами пеРвого и второго элементов И блока управления, единичный выход первого триггера блока управления соединен со вторыми входами первого и второго и первым входом третьего элементов И блока правления, выход первого элемента И блока управления через счетчик импульсов блока управления подключен к нулевому входу первого триггера блока управления, нулевой выход первого, °, 45 .триггера блока управления соединен с ,первыми входами четвертого, пятого и шестого элементов И блока управления,вторые входы третьего и четвертого- элементов И блокауправления объ- S0 единеныи подключенык первому выходу генератора импульсов, выход третьего элемента И блока управления соединен,с

1 первым входом элемента ИЛИ блока управлейия, выход которого является первым выходом блока управления, выход четвер- .

:того элемента И блока управления сое-. динен cd вторым входом элемента ИЛИ

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

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

На фиг. 1 показана функциональная схема устройства и функциональная охема модели вершины, на фиг. 2— функциональная схема блока управления.

Устройство дпя исследования. графов содержит модели 1(1)-1(h) вершин исследуемого графа (здесь и в дальнейшем цифрами в скобках обозначены порядковые номера одинаковых по своему техническому исполнению блоков, . узлов и элементов), блок 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, .элемент ИЛИ 40, счетчик 41 импульсов, .генератор 42 синхронизирующих импульаов входной -информационный полюс

43 модели вершины, выходной информа- . ционный полюс 44 модели вершины, первый выход 45 блока управления, вто.Рой выход 46 блока управления, первыи управляющий вход 47 модели вершины, четвертый управляющий вход 48 моде- .. ли вершины, третий выход 49 блока управления, второй управляющий вход

50 модели вершины, первый управляю-: щий выход 51 модели вершины, чегвер7 11349 тый выход 52 блока управления, тре» тий управляющий вход 53 модели вершины, вход 54 блока управления, пятый выход 55 блока управления, пятый уп-, равляющий вход 56 модели вершины, ше-. 5 стой управляющий вход 57 модели вершины °

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

Г + х, графа, достигаемых из некоторой вершины х„,, и в определении множества вершин Г х„, из которых мажет быть достигнута вершина x; . При этом множество вершин с(х;), принадлежащих максимальному сильно связанному подграфу, отвечает условию л+ .л с(х) =Г х ПГ х;

Эти исходные данные находятся следующим образом.

Первоначально посредством входных

43 и выходных 44 информационных полюсов модели вершин 1(1) -1(n) ком- мутируются между собой в соответствии с топологией. исследуемого графа..

Сдвиговые регистры 3, 24, 25, 26 и счетчик 41 обнуляются. Триггеры 5, б,- 7, 31, 32, 33 устанавливаются в !

35 нулевое состояние. Установочные шины на фиг. 1 и фиг. 2 не показаны.

Число разрядов всех сдвиговых регистров и счетчика определяется числом

; вершин исследуемого графа.

Первоначально определяется в графе множество вершин Г» х,, достижи:мых из произвольно выбранной регистром 3 вершины х1. Для этого.генератор 42 импульсов выдает импульс ГИ на вход элемента И 36. Пройдя его, он поступает через элемент ИЛИ 40 на выход 45 и на вход триггера 31, который устанавливается в единичное состояние. Единичное состояние триг-.50 гера 31 выдает разрешение на полюс

46. Это разрешение с полюса 46 блока . управления 2 поступает на входы 47 всех моделей, вершин 1(1)-1(n).

С выхода 45 блока управления им- 55 пульс ГИ, поступает на вход сдвиго— вого регистра 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. Этот импульс ГИ пройдя элемент И 37, устанавливает триггер 32 в единичное состояние и триггер 31 — в нулевое. В результате с выхода 46 блока управления 2 разрешение будет снято и, как следствие, оно будет снято с входов 47 всех моделей вершин 1(1)-1(И) . Единичное состояние триггера 32 вьпает разрешение на выход 49 блока управления 2. Раз-. решение с выхода 49 блока управления

2 поступает на входы 50 всех моделей вершин 1(1) — 1(п) .

В выбранной ранее модели вершины с входа 50 разрешение через элемент

И 14.и ИЛИ 20 поступает на вход триггера 6 и устанавливает его в единич- ное состояние, которое выдает разре- шение на входы элемента И 11 и форми рователя 29 одиночного импульса. По разрешению, поступившему на вход фор9 ления 2 производит аналогичным образом выбор новой модели вершины и процесс формирования нового. максимального сильйо связного подграфа повторяется. При этом блок управления 2 производит сдвиг содержимого регистров 24. Это происходит по импульсу ГИ сдвинутому Относитель но ГИ,, генератора импульсов 42, который через элемент И 34 поступает на выход 52 блока управления 2 .и далее - на входы 53 всех моделей вершин 1(1)-1(n). В моделях вершин с входа 53 импульс ГИф поступает на сдвиговый вход регистра 24 модели вершины.

Процесс р.азложения графа на мак: симальные сильно связные подграфы заканчивается только в том случае, когда на выходе сдвигового регистра 3 появляется. сигнал, который поступает на вход 54 блока управления 2. Это свидетельствует о том, .что все максимальные сильно связные подграфы в графе сформированы. Номер разряда, который находится в единичном состоянии, сдвигозого регистра 24 моделей вершин 1(1)-1(И) определяет номер максимального сильно связного под. графа, к которому относится та или иная вершина графа. Эта информация служит исходныыю данньйи задачи оп- ределения нкодных и выходных вершин максимапьнык сильно связник подграфов.

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

С(х„ ), в определении Г (ЦС(х, )) и(С С(х;Ц и в пометке вершин, ; удовлетворяющих условиям

9 1134 мирователя 29 одиночного импульса, на его выходе появляется импульс, который поступает на информационный полюс 43 выбранной модели вершины.

С полюса 43 выбранной модели вершины импульс поступает на полюс 44 мрделей вершин, связанных с полюсом

43 выбранной модели. В этих моделях импульс с полюса 44 через элементй

И 12 и ИЛИ 20 поступает на вход 1р триггера 6, который устанавливает в единичное состояние. Таким обра зом, распространяясь по графу этот импульс формирует множество f х;, о чем свидетельствует единичное состояние триггеров 6 моделей вершин.

Построение множеств Г х;и Г х в моделях вершин 1(1)-1(п) триггеров

6 и 7 ° одновременно находящихся в единичном состоянии, свидетельству-, ет о том, что соответствующие им вершины графа принадлежат максимальному сильно связному подграфу, одной из вершин которого является выбранная распределителем импульсов вер-.2 шина х .

Метка сформированного максимального сильно связного подграфа осуществляется разрешением, снимаемым с.выхода элемента И 11. Это разрешение поступает на вход формирователя

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

Как только будет помечен и сформирован максимальный сильно. связный подграф, блок управления 2 снимает " разрешение с входов 50 всех модепей вершин 1(1)-1(и) и.переходит к формированию новык максимальнык сильно связнык-нодграфов. Исключение as дальнейшего рассмотрения вершин, принадлежащих уже сформированным подграфам, осуществляется.путем инвертирования элементом НК 22 сигнала, посту-, пающего с выкода элемента И 11 через элемент КПИ 18.. Этот инвертированный сигнал поступает на выход 51, снимая разрешение с выкоцов соответствующих элементов И 4(1)-И 4(й) ..

I.

В дальнейшем блок управления 2 устанавливает триггеры 6 и 7 в ну- $5 левое состояние у тех моделей вершин, которые яе принадлежат сформированному подграфу, после чего блок управ46 10

Г (Фс(хЛ3ос(х; Г $G)G(x;)gbg(x;$, Первые помеченные вершины являют ся входными вершинами максимального сильно связного поцграфа, а вторые вык од ньяи а

Процесс решения этой задачи начя. наегся с момента поступления сигнала с выхода сдвигового регистра 3 на вход 54 блока управления 2. По этому сигнапу блок ущ)авления " устанавливает все триггеры 6 и 7 всех моделей вершин и триггеры 31 и 32 в нулевое состояние.

11 1134

Сигнал с входа 54 в блоке управления 2 поступает на вход триггера

33 и устанавливает его в единичное состояние. Единичное состояние триггера 33 снимает разрешение с входов элементов И 36 и 37 и выдает разрешение на вход элементов И 35, 38, 39.

Кроме этого, разрешение появляется на выходе 55 блока упрвления 2. Разрешение с выхода 55 блока управления 10

2 поступает на входы 56 всех моделей вершин 1(1}-1(n) .

В процессе метки максимальных силь-: но связных подграфов производится сдвиг информации, содержащейся s ре-, 1S гистрах 24 сдвига моделей вершин. В . результате на выходе регистров 24 сдвига, принадлежащих моделям вершин, которые вошли в первый подграф, име» ртся сигнал. Этот сигнал поступает

ha вход триггера 5, что приводит к установлению его в единичное состоя" ., ние.

Сигнал с единичного выхода тригге-, ра 5 поступает на вход элементов И 25

8, 9 и ИЛИ 18. С выхода элемента ИЛИ 18 сигнал поступает на вход элемента НЕ .22. Этот сигнал инвертируется элемен, том НЕ 22 и поступает на выход 51, .который соединен с входом соответст- . ЗО вующнх элементов И 4(1)-4(ii.) . .Тем самым блокируются входы тех элементов И 4(1)-4(й), которые соответствуют моделям вершин, принадлежащим первому максимальному сильно связа .-. ному подграфу. Это. соответствует опре35 делению множества вершин g) С(х ).

Одновременно с появлением разрешения на выходах 46, 49 и 55 блока управления.2 генератор 42 импульсов 4 выдает импульсы ГИ через элементы

И 38 и HJIH 40 на выход 45 блока управления 2. Импульсы с выхода 45 блока управления 2 поступают на вход . сдвигового регистра 3 и на входы 57 всех моделей вершин 1{1)-1(11).

В моделях вершин импульсы ГИ1 с . входа 57 через элемент И 10 поступают на сдвиговый вход регистров 25 и, 26 сдвига. При этом разрешение по"

50 ступившее из блока управления 2 на вход 56, блокирует входы элементов

И 12-15 и разрешает прохождение сигналов через элементы И 10, 16, 17. Импульсы ГИ, поступившие .на вход SS сдвигового регистра 3, последовательно выдают разрешение на его разряд:ных выходах. Далее разрешение про- .

946 12 ходит через элементы И 4(1)-4 (й) на входы 48 моделей вершин, которые не заблокировали свои элементы И 4(1)

4(й) .

С входа 48 в каждой модели вершины разрешение поступает на входы элементов И 16 и 17 и проходит через них соответственно на полюса 44 и 43 по мере опроса регистром сдвига 3 всех моделей вершин 1(1)-1(n), что соответствует выполнению условий 1 (Ц

iC(х;)) С(х,) и Г С С(х })О С(х ).

Исключение составляют модели вершин, триггер 5 которых находится в единичном состоянии. У них на входах 48 разрешение не появляется и, следова- . тельно, оно не появляется на полюсах

43 и 44.

С полюса 44 опрошенной регистром сдвига 3 модели вершины разрешение поступает на полюса 43 моделей вершин связанных с ней. Аналогично разрешение поступает с полюса 43 опрошенной модели вершины на полюса 44 дру-. гих моделей. Если при этом окажется, что опрошенная вершина непосредственно связана с вершиной, в которой триггер 5 находился в единичном сос:,тоянии, то разрешение с полюса 43 поступает через элемент И 9 на уста новочный вход регистра 26 сдвига, где в соответствующий разряд записывается единица. Этот разряд соответствует номеру модели вершины, опрошенной сдвиговым регистром 3.

Аналогичный процесс происходит, если разрешение поступает с полюса

44. В данном случае оно проходит- . элемент И 8 и поступает на установоч- ный вход регистра 25 сдвига, где в соответствующий разряд записывается единица;

4

Йаличие единицы хоть в одном раз. ряде сдвиговйф„ :регистров 25 или 26 свидетельствуфт. о том, что данная модель вершйны является входом или выходом максимапьного сильно связ-, ного подграфа. Номера разрядов регистров 25 или 26, в которых находится единица, и номер модели вершины, к которым относятся..данные регистры, определяют входные и выходные дуги максимального.сильно связного подграфа, т.е. ойределяют дуги направленного разреза.

Процесс определения входных и выходных вершин данного максимапьного сильно связного подграфа оканчивается

13 1134946, 14 в тот момент когда на выходе сдвиго- обеспечивается выбор вершйн нового з вого регистра 3 появляется импульс. максимального сильно связного подграЭтот импульс поступает на вход 54 бло- фа. Для устранения потери информации ка управления 2, по которому послед- в сдвиговых регистрах 24 содержимое выний устанавливает триггер 5 моделей - ходного разряда через элемент ИЛИ 19

5 вершин выбранного максимального силь- переносится в первый разряд. но связного подграфа в нулевое сос- В дальнейшем процесс повторяется тояние. аналогично описанному.

Далее, блок управления 2 выбирает . .- Решение задачи оканчивается тогда новый максимальный сильно связный 1О когда определены все входы и выходы подграф, что осуществляется нмпуль- всех максимальных сильно связных сом, который поступает на вход 54,подграфов. Об этом свидетельствует блока управления 2. С выхода 49 им- импульс переполнения, который появляпульс поступает на вход;элементов И ется на выходе счетчика 41, который в

35 и 39. Пройдя элемент И 39, он по- 1 блокеуправления 2устанавливает триг ступает на вход счетчика 41 и фикси- -:.гер 33 в нулевое состояние. руется s нем. Пройдя элемент И 35, Информация о решении задачи, отоимпульс поступает на выход 52 блока бражаемая схемами 30 индикации модеуправления 2. С выхода 52 блока уп- лей вершин 1(1)-1(tl), включает в себя ° равления 2 он поступает на входы 53 2О номера максимальных сильно связных всех моделей вершин 1(1)-1(й) и да- подграфов, к которым относится та или лее — на сдвиговый вход сдвиговых ре- иная модель вершины, номера вершин, гистров 24, что обеспечивает сдвиг из которых выходят или в которые вхона один разряд их содержимого. Этим дят связываюшие дуги.

1134946

1134946

Составитель С.Назаров

Редактор С.Тимохина Техред А.Бабинец Корректор О.Тигор

Заказ 1Q091/42 Тирак 710 Подписное

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

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

Филиал ППП"Патент", r. У кгород, ул. Проектная, 4