(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНЫХ СЕЧЕНИЙ ГРАФА
Устройство относится к вычислительной технике и может быть исполь зовано для определения сечений различных размерностей при исследовании надежности систем, описываемых графами. Известно устройство для определения характеристик связности графа р}, содержащее элемент И, запоми накнцие триггеры вершин и ветвей, управляемое ключевые схемы схемы отображения графа. В известном устройстве оценка надежности проводится по минимальному числу ветвей, разъединяющих пути меж ду парой узлов, что ограничивает область его использования. Наиболее близким к данному техническому решению является устройство для выбора сети связи 2, содержащее блок управления, блок задания сети, коммутатор, логический блок, триггеры, регистры, блоки сравнения, счетчики. Прототип не позволяет определять число минимальных сечений графа каждой размерности. Целью изобретения является расширение функциональных возможностей устройства за счет учета числа ми нимальных сечений казедой размерности. Поставленная цель достигается , тем, что в устройство, содержащее группу счетчиков, первый распределитель и коммутатор, дополнительно введены первый и второй блоки формирования топологии графа, второй распределитель, два шифратора, элемент ИЛИ, rpjmna элементов И, группа триггеров, две группы элементов ИЛИ, регистры сдвига и блок управления, причем i-тый (,2,N-1 выход первого распределителя соединен с -1-тым входом первой группы первого блока формирования топологии графа, з-тый вход второй группы которого подключён к -j -тому выходу коммутатора и к i-тому входу первого 3 шифратора (,1 1 ,2, . ., ,N-1) , К-тый выход которого соединен с первым вхо дом элемента И группы, второй вход которого подключен к К -том выходу второго шифратора (К 1,2,.. N-2/, i-тый вход которого соединен с выходом 1 -того элемента ИЛИ первой группы, вькод 1-того элемента И группы подключен к | -тому входу элемента ИЛИ, выход которого соединен с входом блока управления и первым выходом регистра сдвига, первый вход которого подключен к первом выходу блока управления и входу коммутатора, Л -тый вьпсод которого соединен с -l-TbiM входом первой группы второго блока формирователя топологии графа (,2,...,M-0, К-тый вход второй группы которого подключен к -f+1-МУ выходу коммутатора (1 1,2,... вход которого соединен с первыми входами триггеров группы, выход -того триггера подключен к j -тому входу группы второго распре делителя ( ,2,. , ,/И), выход которо го соединен со вторым входом регистра сдвига, вход Y -ного счетчика гру пы соединен с выходом регистра сдвига (и 1 , . M-N+l), i-тый вход j -той группы первого блока фор мирования топологии графа подключен 1 -тому входу J гтого элемента ИЛИ второй группы, выход которого соединен со вторым входом л -того тригге группы. (,2, .. ,,N-1 ,5 1,2, ,. ., вход первого распределителя подключен ко второму выходу блока управле ния, третий выход которого соединен со входом второго распределителя, ХИ-ный выход К-той группы второго блока формирования топологии графа подключен к )т -ному входу К -того элемента ИЛИ первой группы (1 1,2,...N-2, ,2,...N-l-k}. Блок управления содержит генератор тактовых импульсов, два триггера, четыре элемента И, счетчик и дешифратор, причем выход генератора тактовых импульсов соединен с первыми входами элементов И, выходы пе вого, второго и третьего элементов И являются соответственно первым, вторым и третьим выходами блока, выход четвертого элемента И подключен к первому входу счетчика, выходы которого соединены с соответствующими вхоламм дешифратора, первый выход которого подключен к первому . .4 входу первого триггера и второму входу счетчика, третий вход которого соединен с выходом первого элемента И, второй вход которого подключен к вторым входам второго и четвертого элементов И и выходу второго триггера, первый вход которого является входом блока второй вход второго триггера соединен со вторым входом третьего элемента И, вторым выходом дешифратора и вторым входом первого триггера, выход которого соединен с третьими входами второго и третьего элементов И. Первый блок формирования топологии графа содержит N-1 группу элементов И, причем первые входы элементов И -i-той (l,2,...,N-l} группы объединены и являются 1 -тым входом первой группы блока, вторые входы элементов И I -той группы объединены и являются 1 -тым входом второй группы блока, выход -того элемента И f-той (j 1 , 2,.. . ,/И)группы является 1-тым выходом -той i-руппы блока. Второй блок формирования топологии графа содержит N-2 группы элементов И, причем первые входы всех элементов И -{-той ( i 1, 2,.. . ,) группы объединены и являются i -тым входом первой группы блока, вторые входы j-тых элементов И всех групп объединены и явл5нотся -тым входом второй группы блока, выход 1 -того элемента И -той группы является ;) -ТЫМ ВЫХОДОМ ( j 1 , 2 , . . . , N- 1 - 1 ) 4 -той группы блока. На фиг. 1 представлена схема устройства; на фиг. 2 - схема первого блока формирования топологии; на фиг. 3 - схема блока управления; на фиг. 4 - схема второго блока формирования топологии. Устройство содержит распределители 1,2, блок управления 3- коммутатор 4, блоки формирования топологии графа 5 и 6, пшфраторы 7 и 8, триггеры , регистр сдвига 10, счетчики 1Ц-11дд |ди элементы ИЛИ ЗГ% Прямой блок формирования топологии содержит элементы И 15 -15,, -l- 6M J7 -17/w, . Блок управления содержит генератор тактовых импульсов 19, элементы И 20-23, триггеры 24, 25, счетчик 26, дешифратор 27. Второй блок формирования топологии содержнт элементы И: .. „ , , ЗЦ . В работе устройства следует вьще литель два этапа - этап задания ст.р туры графа и этап вычисления числа минимальных сечений одинаковой размерности. Рассмотрим этап задания структур графа. Основой для задания графа в уст;ройстве является граф, имеющий в&уашп и М ребер, в котором все эйемей-ш иронунерованы. Йрй зщ&няк структуры графа на блоке ф зр «|роВ ния топологии 5 подrOT&sHtHsaeeTCR цепи срабатывания эле ментов И й строке (строка соответствует определенной вершине) KOTOpiae соо гвететауют ребрам, идентичйми да«ной ве|мййне (всего элемен тов и в строке блока 5 столько, сколько ребер в графе). На блоке фо мирования топологий в каждой строке подготавливаются цепи срабатывания элементов И тех верйин, с которыми данной (соответствзч1эщая строке) вер ншна неп средств вййо связана. Первйй ёйока 6 соответствует пе вой вершийе, строив поля второй в-ерйн й ё,... последняя строка - N-2-ой верЮйНе графа. В то же время перй И первой строки соответствует второй вершине, 3JleMeHT - третьей,..., поел еянйй -N-1-й . Аналогично первый ( левый) элемент второй строки соответствует третьей вершине, второй - четвертойj..., после ней - N-f-ёой верйяне графа. Для остальных строк блока формирования тешологии 6 назначение элементов И подовно вьшюизложеннсжу. Йа этапе вычисления числа минимальных сечений устройство работает под действием импульсов, поступающих от блока управления 3. Первьй импульс от генератора так товых и «1ульсов 19 воэбуяздает первый выход блока управления. Сигнал с этого выхода сйрасывает в нуль триггеры 9л -9дд и считывает информацию ИЗ регистра 10. В то же время С нал, поступая на вход коммутатора 4, возбуждает его первый и второй выходы. Сигналы с выходов коммутатор поступают на блоки формирования топологии 5, 6 и шифратор 8. Шифратор 8 при наличии сигнала н любых двух входах возбуждает первый выход, на любых трех - второй,..., на N-1-вых входах - потенциал на N-2-BOM выходе. Если номера возбужденных выходов коммутатора соответствуют вершинам, непосредственно связанным между собой, то через блок 6 будет возбуждено число входов шифратора 7 на один меньше, чем возбуждено выходов коммутатор 4. Шифратор 7, если возбужден один его вход, формирует сигнал на выходе 1, если два входа на выходе 2,..., если возбуждены все N-2 входа - сигнал на N-2-м выходе. Таким образом, если первая и вторая вершины графа связаны между собой, будут возбуждены одноименные выходы шифраторов 7 и 8. Тогда сигнал поступит на элемент И 15. и да- .лее на элемент ИЛИ 14. ; С элемента ИЛИ 14 сигнал будет подан на вход блока управления 3 и запишет единицу в нулевой разряд регистра 10. Если на входе блока управления есть сигнал, последующие fvj-l импульсов будут поданы на второй выход, следующие ДЛ импульсов - на третий вшсод и после прохождения К 1 и ЛА и№1ульсов будет снова возбужден вькод 1 блока управления, иначе (если нет сигнала на входе 2) второй импульс опять возбудит первый выход н заставит перейти коммутатор 4 в следующее положение. №етульсы с выхода 2 блока управления N-J, поступшощие на вход распределителя 1, возбуждают поочередно 1, 2, 3,..., N-1-BbBi выходы. Так как возбуждены выходы 1 и 2 коммутатора 4, то при подаче сигнала на второй вькод распределителя сигнал снимается с тех элементов И первой строки, цепи срабатывания которых подготовлены при задании структуры графа аналогично будет при подаче сигнала на второй выход раепределителя . С элементов И строк блока формирования топологии 5 через элементы ШЖ 13 сигналы поступят на единичные входы соответствующих триггеров и переведут их в единичное состояние. Если подготовлены цепи срабатывания однЬименных элементов И двух строк блока формирования топологии 5, соответствующий триггер перейдет сначала в единичное состояние, а затем вернется в нулевое. Следующие АЛ импульсов поступают на выход 3 блока управления и далее на вход О распределителя 2. Распределитель 2 при поступлении на его вход импульсов опрашивает триггеры -9 и при наличии единичного состояния триггера формирует импульс сдвига в параллельный регистр 10. Таким образом, сколько триггеров будет находиться в единичном состоянии, до такого разряда будет сдвинута { влево ) единица в параллельном регистре 10. Последутопдай импульс поступит опят на первый выход блока управления и с него - на вход Сб триггеров 9х-9дд, вход Сч регистра 10, вход коммутатора 4, который, перейдя в последующее положение, подаст сигналы на выходы 1 и 3. С поступлением третьего импульса на вход коммутатора 4 возбуждаются выходы 1 и 4, далее 1 и 5, 1 и 6... 1 и , затем 2 и 3, 2 и 4,...2 nN-i,3H4,..., М-2и N-I, в да нейшем 1,2 и 3; 1,2 и 4;... и т.д. до 1,2,3, ..., N -1. После обработки цикла с возбужденными 1,2,3,..., N-1 выходами коммутатора 4, коммутатор примет исходное состояние, и устройство закончит подсчет минимальных сечени графа.. Показания счетчиков ны числу минимальных сечений, разме ность сечения совпадает с номером счетчика. Устройство позволяет упростить процесс выделения минимальных сечений графа при исследовании надежности систем. Формула изобретения 1. Устройство для определения ми нимальных сечений .графа, содержащее группу счетчиков, первый распределитель и коммутатор, отличающееся тем, что, с целью расширения функциональных возможностей за счет учета числа минимальных сечений каждой размерности, в него до полнительно введены первый и второй блоки формирования топологии графа второй распределитель, два шифратор элемент ИЛИ, группа элементов И, группа триггеров, две группы элементов ИЛИ, регистры сдвига и блок управления, причем 1-тый (,2,... N-I) выход первого распределителя соединен с -тым входом первой группы первого блока формирования топологии графа, -i -тый вход второй группы которого подключен к л-тому выходу коммутатора и к -i -тому входу первого шифратора (l 1 ,2, . . ./-1) , К -тый выход которого соединен с первым входом К-того элемента И группы, второй вход которого подключен к К-тому вы- . ходу второго шифратора (К 1, 2, . . .jN-2) i -тый вход которого соединен с выходом i -того элемента ИЛИ первой группы, выход -1 -того элемента И группы подключен к 1-тому входу элемента ИЛИ, выход которого соединен с входом блока управления и первым выходом регистра сдвига, первый вход которого подключен к первому выходу блока управления и входу коммутатора, i -тый выход которого соединен с i -тым входом первой группы второго блока формирователя топологии графа ( 1,2,..,, N-1), К-тый вход второй группы которого подключен к выходу коммутатора ,2,..., N-2), вход которого соединен с первыми входами триггеров группы, выход -j -того триггера подключен к -j -тому входу группы второго распределителя ( 1,2,...,, выход которого соединен со вторым входом регистра сдвига, вход И-ного счетчика группы соединен с VI + 1-м выходом регистра сдвига (и 1 , . .., M-N +1 , { -тый выход -j -той группы первого блока формирования топологии графа подключен к i-тому входу -того элемента ИЛИ второй группы, выход которого соеди нен со вторым входом -того триггера группы ( 1,2, . ., N-1 г} 1,2,..., М) вход первого распределителя подключен ко второму блока управления, третий выход которого соединен со входом второго распределителя, М-нь1Й выход К-той группы второго блока формирования топологий графа подключен к VV -ному входу К-того элемента ИЛИ первой группы (К 1,2, ..., N-2, ,2,..., N1-К). 2. Устройство по п. 1 , о т л и чающеес я тем, что блок управления содержит генератор тактовых импульсов, два триггера, четыре элемента и, счетчик и дешифратор, причем вы ход генератора тактовых импульсов соединен с первыми входами элементов И, выходы первого, второго и третьего элементов И являются соот ветственно первьм, вторым и третьи выходами блока, выход четвертого элемента И подключен к первому вход счетчика, выходы которого соединены с соответствующими входами дешифратора, первьй выход которого подключен к первому входу первого триггера и второму входу счетчика, третий вход которого соединен с выходом первого элемента И, второй вход которого подкгаочен к вторым входам второго и четвертого элементов И и выходу второго 14 йггера, первый вход которого является входом блока, второй вход второго триг гера соединен со вторым входом третьего элемента И, вторым выходом дешифратора и вторьм входом первого триггера, выход которого соединен с третьими входами второго и третье го э 1ементов И. 3. Устройство по п, , отли чающееся тем, что первый блок формирования топологии графа с держит N-I группу элементов И, при 4. 10 чем первые входы элементов И -1 -той ( i 1, 2N-I группы объединены и являются -тым входом первой группы блока, вторые входы элементов И i -той группы объединены и являются -i -тым входом второй группы блока, выход j -того элемента И -i-той (-} 1,2, ...,М) группы является - -тым выходом -той группы блока. 4. Устройство по п. 1, отличающееся тем, что второй блок формирования топологии графа содержит 1 -2 группы элементов И, причем первые входы всех элементов И i -той (-1 1 ,2, .,., Н-2/ группы объединены и являются -тым входом первой группы блока, вторые входы л -тых элементов И всех групп объединены и являются j -тым входом второй группы блока, выход -j -того элемента И j -той группы является -тым выходом ( j 1,2, . .., N -1- а ) i группы блока. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР № 468244, кл. G 06 F 15/36, 1971. 2.Авторское свидетельство СССР по заявке № 2414862/18-24, кл. G 06 F 15/36, 1976 (прототип).
,//
Т/
т
/.
г
if
От4
/ry/- /y
y.
От K0f(fff ffff7fffrff
d 11
St Iff
ГТК ГЗ
9m il/iff-ff
fwi.3
15
Т /j
