Устройство для определения минимальных сечений графа

ц 888134 Союз СоветскиаСоцнапистическнкРеспубики ОП ИСАНИЕИЗОВРЕТВН ИЯК АВТОРСКОМУ СВИДВТЕЛЬСТВУ(5 )М. Кд. О 06 Г 15/36 3 Ъаударетаееьй квиатвт ссер 10 Мелам азабретвааа и открытия(54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНЬИ СЕЧЕНИЙ ГРАФА Устройство относится к вычислительной технике и может быть использовано для определения сечений различных размерностей при исследовании надежности систем, описываемых графами.Известно устройство для определения характеристик связности графа 1, содержащее элемент И, запоминающие триггеры вершин и ветвей, управляемые ключевые схемысхемы отображения графа.В известном устройстве оценка надежности проводится по минимальному числу ветвей, разъединяющих пути между парой узлов, что ограничивает область его использования.Наиболее близким к данному техническому решению является устройство для выбора сети связи 12, содержащее блок управления, блок задания сети, коммутатор, логический блок, триггеры, регистры, блоки сравнения, счетчики. Прототип не позволяет определять число минимальных сечений графа каждой размерности.Целью изобретения является расширение Функциональных возможностей устройства за счет учета числа минимальных сечений каждой размерности.Поставленная цель достигается тем, что в устройство, содержащее группу счетчиков, первый распределитель и коммутатор, дополнительно введены первый и второй блоки формирования топологии графа, второй распределитель, два шифратора, элемент ИЛИ, группа элементов И, группа триггеров, две группы элементов ИЛИ, регистры сдвига и блок управления, причем 1-тый ( 1 =1,2 Йвыход первого распределителя соединен с 1-тым входом первой группы первого блока Формирования топологии граФа, т -тыйвход второй группы которого подключен к 1 -тому выходу коммутатора и к 1-тому входу первого25 шифратора ( 1 =1,2, ,И), К -тый выход которого соединен с первым входом К-того элемента И группы, второй вход которого подключен к К -тому выходу второго шифратора (К =1,2, 11-2, 1 -тый вход которого соединен с выходом 1 -того элемента ИЛИ первой группы, выход 1 -того элемента И группы подключен к 1 -тому входу элемента ИЛИ, выход которого соединен с входом блока управления и первым выходом регистра сдвига, первый вход которого подключен к первому выходу блока управления и входу коммутатора, 1 -тый выход которого соединен с 1-тым входом первой группы второго блока формирователя топологии графа (1 =1,28-1), К -тый вход второй группы которого подключен к 1 +1-му выходу коммутатора (И= =1,2,8-2), вход которого соединен,. с первыми входами триггеров группы, выход 1 -того триггера подключен к-тому входу группы второго распределителя (1 =1,2,М), выход которого соединен со вторым входом регистра сдвига, вход И -ного счетчика группы соединен с И +1-м выходом регистра сдвига (11=1 М+1), 1-тый вход ) -той группы первого блока формирования топологии графа подключен к 1 -тому входув .того элемента ИЛИ второй группы, выход которого соединен со вторым входом-того триггерагруппы (1=1,2,1 М, =1,2Й) вход первого распределителя подключен ко второму выходу блока управления, третий выход которого соединен со входом второго распределителя, ИЧ-ный выход К-той группы второго блока формирования топологии графа подключен к М-ному входу К -того элемента ИЛИ первой группы Ф ==1,2,8-2, щ=1,2,8-1-К). Блок управления содержит генератор тактовых импульсов, два триггера, четыре элемента И, счетчик и дешиФратор, причем выход генератора тактовых импульсов соединен с первыми входами элементов И, выходы первого, второго и третьего элементов И являются соответственно первым, вторым и третьим выходами блока, выход четвертого элемента И подключен к первому входу счетчика, выходы которого соединены с соответст- вуюи 1 ими входами дещаЬратара, первый выход которого подключен к первому 1 О 15 20 30 35 40 45 входу первого триггера и второму входу счетчика, третий вход которого соединен с выходом первого элемента И,второй вход которого подключен к вторым входам второго и четвертого элементов И и выходу второго триггера,первый вход которого является входом блока, второй вход второго триггера соединен со вторым входом третьего элемента И, вторым выходомдешиАратора и вторым входом первоготриггера, выход которого соединенс третьими входами второго и третьего элементов И.Первый блок формирования топологии графа содержит Мгруппу элементов И, причем первые входы элементов И 1 -той (1 =1,2, . й 1-1)группы объединены и являются 1 -тымвходом первой группы блока, вторыевходы элементов И 1 -той группы объединены и являются 1 -тым входомвторой группы блока, выход-тогоэлемента И 1-той ( =1,2И)группы является 1 -тым выходом-тойгруппы блока.Второй блок формирования топологии графа содержит Йгруппы элементов И, причем первые входы всехэлементов И 1 -той ( 1 =1, 2, 18-2)группы объединены и являются 1 -тымвходом первой группы блока, вторыевходы-тых элементов И всех группобъединены и являются 1 -тым входомвторой группы блока, выход 1 -тогоэлемента И ) -той группы является9 -тым выходом ( =1,2Мв 1)1 -той группы блока,На Фиг. 1 представлена схема устройства, на фиг, 2 - схема первогоблока формирования топологии; нафиг. 3 - схема блока управления; нафиг. 4 - схема второго блока формирования топологии,Устройство содержит-распределители 1,2, блок управления 3 коммутатор 4, блоки формирования топологии графа 5 и 6, шифраторы 7 и 8,триггеры 91-9 щ, регистр сдвига 1 О,счетчики 11 А -11 М 1 1, элементыИЛИ 12,1 - 12 Й 2, 131 - 1 ЗМ 14,Прямой блок формирования топологии содержит элементы И 151 -151,161 16 М 174 17 М 181 1 89 Блок управления содержит генератор тактовых импульсов 19, элементы И 20-23, триггеры 24, 25, счетчик 26, дешифратор 27.888134 40 Второй блок формирования топаловгни содер ит элементы И: 281 -28 М д.29-29 Д , 30,1-30 д, 311В работе устройства следует выделитель два этапа - этап задания струк-туры графа и этап вычисления числаминимальных сечений одинаковой размерности.Рассмотрим этап задания структурыграфа. Основой для задания графа в 10устройстве является граф, имеющийЯ вершки и М ребер, в котором всеэлементы пронуяероваиы.Буй эданйи структуры графа наблоке фориироМнйя топологии 5 под- юготаюФиеМтся ценя срабатывания элементов Н в каЖдой строке (строкассютветствует Определенной вершине)котарме соатветствуют ребрам, идентичимм дайной верйине (всего элементов И в строке блока 5 столько,сколько ребер в граФе). На блоке формирования топологии в каждой строкеподготавливаются цепи срабатыванияэлементов И тех вераин, с которыми 2данная (соответствующая строке) вершикв иепосрадственно связана. Нервам строка баокЭ 6 соответствует первой верйийе, Вторая строка полявторой ве 9 пвщФ последняя стра- Зфка - М-ой аершине граФа. В то жевремя первый элемект И первой строки соответствует второй вершине,второй элемент - третьей по"следний - И-й ьерййце, Аналогич 3но первыйлевый) элемент второйстуокн соответствует третьей вершина, второй - четвертой последний - И-вой вершине граФа. Дляостальных строк блока формированиятопологии б назначение элементовИ подобно вышеизложенному.Яа этапе вычисления числа минимаиъных сечений устройство работаетпод действиеи импульсов, наступающих от блока управления 3.Первый импульс от генератора тактовых импульсов 19 возбуждает первый выход блока управления. Сигналс этого выхода сбрасывает в нультриггеры 9 -9 р и считывает информаЯцию из регистра 10. В то же время сигнал, поступая на вход коммутатора4, возбуждает его первый и второйвыходы. Сигналы с выходов коммутатораИпоступают на блоки формирования топологии 5, б и шифратор 8.Шифратор 8 при наличии сигнала налюбых двух входах возбуждает первый выход, на любых трех - второй на М-вых входах - потенциал на Й-вом выходе.Если номера возбужденных выходов коммутатора соответствуют вершинам, непосредственно связанным между собой, то через блок 6 будет возбуждено число входов шифратора 7 на один меньше, чем возбуждено выходов коммутатор 4. 1 Пифратор 7, если возбужден адин его вход, формирует сигнал на выходе 1, если два входа - на выходе 2.если возбуждены все Мвхода - сигнал на й -2-м выходеТаким образом, если первая и вторая вершины графа связаны между собой, будут возбуждены одноименные выходы шидраторов 7 и 8. Тогда сигнал поступит на элемент И 15 и далее на элемент ИЛИ 14.С элемента ИЛИ 14 сигнал будет подан на вход блока управления 3 и запишет единицу в нулевой разряд регистра 10Если на входе блока управления есть сигнал, последующие Я -1 импульсов будут поданы на второй выход, следующие 9 импульсов - на третий выход и после прохождения К -1 и М имнульсов будет снова возбужден выход 1 блока управления, иначе (если нет сигнала на входе 2) второй импульс опять возбудит первый выход н заставит перейти коммутатор 4 в следующее положение.Импульсы с выхода 2 блока управления И, поступающие на вход распределителя 1, возбуждают поочередно 1, 2, 3 И-вый выходы.Так как возбуждены выходы 1 и 2 коммутатора 4, то при подаче сигнала на второй выход распределителя сигнал снимается с тех элементов И первой строки, цепи срабатывания которых подготовлены при задании структуры графа, аналогично будет при подаче сигнала на второй выход , распределителя 1, С элементов И строкблока формирования топологии 5 через элементы ИЛИ 13 сигналы поступят на единичные входы соответствующих триггеров и переведут их в единичное состояние. Если подготовлены цепи срабатывания однодоменных элементов И двух строк блока формирования топологии 5, соответствующий триггер перейдетсначала в единичное состояние, а затем вернется в нулевое,Следующие М импульсов поступаютна выход 3 блока управления и далеена вход "0" распределителя 2. Распределитель 2 при поступлении наего вход импульсов опрашивает тригчгеры 91-9 уи при наличии единичногосостояния триггера Аормирует импульссдвига в параллельный регистр 10.Таким образом, сколько триггеровбудет находиться в единичном состоянии, до такого разряда будет сдвинута ( влево ) единица в параллельномрегистре 10.Последующий импульс поступит опятьна первый выход блока управленияи с него - на вход "Сб" триггеров91-9,щ, вход "Сч" регистра 10, входкоммутатора 4, который, перейдя впоследующее положение подаст сигналы на выходыи 3.С поступлением третьего импульсана вход коммутатора 4 возбуждаютсявыходы 1 и 4, далее 1 и 5, 1 и 6,1 и Й, затем 2 и 3, 2 и 42и Я, 3 и 4 Ии И, в дальнейшем 1,2 и 3; 1,2 и 4; и т.д.до 1,2,3 М - 1.После обработки цикла с возбужденными 1,2,3 Ивыходамикоммутатора 4, коммутатор приметисходное состояние, и устройствозакончит подсчет минимальных сеченийграфа.Показания счетчиков 111 -11равны числу минимальных сечений, размерность сечения совпадает с номеромсчетчика.Устройство позволяет упростить процесс выделения минимальных сечений графа при исследовании надежности систем.Формула изобретения1. Устройство для определения минимальных сечений .графа, содержащее группу счетчиков, первый распределитель и коммутатор, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет учета числа минимальных сечений каждой размерности, в него дополнительно введены первый и второй блоки формирования топологии графа, второй распределитель, два шифратора, элемент ИЛИ, группа элементов И,группа триггеров, две группы элементов ИЛИ, регистры сдвига и блок управления, причем 1 -тый (1 =1,2, Я)выход первого распределителя соединен с 1 -тым входом первой группыпервого блока Аормирования топологииграфа, 1 -тый вход второй группы которого подключен к 1-тому выходу коммутатора и к 1 -тому входу первого10 шифратора ( 1 =1,2,.,М -1), К - тыйвыход которого соединен с первым входом К-того элемента И группы, второйвход которого подключен к К -тому вы-,ходу второго шифратора (К=1,2, , й)15 1 -тый вход которого соединен с выходом 1-того элемента ИЛИ первой группы, выход -того элемента И группыподключен к 1-тому входу элементаИЛИ, выход которого соединен с входомблока управления и первым выходом регистра сдвига, первый вход которогоподключен к первому выходу блокауправления и входу коммутатора, 1 -тыйвыход которого соединен с 1 -тымвходом первой группы второго блокаАормирователя топологии графа ( 1=1,2 И -1), К -тый вход второйгруппы которого подключен к К +1-мувыходу коммутатора К =1,2 М - 2),вход которого соединен с первыми входами триггеров группы, выход 1 -тоготриггера подключен к-тому входугруппы второго распределителя=1,2 Щ выход которого соединенсо вторым входом регистра сдвига,35вход И-ного счетчика группы соединен с И +1-м выходом регистра сдвига (у 1 =1, )111-Н +1, 1 -тый выход 1 -той группы первого блока формирования топологии граАа подключен40к 1-тому входу 1 -того элемента ИЛИвторой группы, выход которого соедиВнен со вторым входом )-того триггера группы (1 =1;2 Й)12 .М) вход йервого распре 45делителя подключен ко вгорому выходублока управления, третий выход которого соединен со входом второго распределителя, Щ-ный выход К-тойгруппы второго блока формирования то-пологии граАа подключен к 7 И-ному входу К -того элемента ИЛИ первой группы (1=1,2 Я, И=1,2 М -1 - К),Ъ2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок управления содержит генератор тактовых импульсов, два триггера, четыре элемента888 15 9И, счетчик и дешифратор, причем выход генератора тактовых импульсовсоединен с первыми входами элементов И, выходы первого, второго итретьего элементов И являются соответственно первым, вторым и третьимвыходами блока, выход четвертогоэлемента И подключен к первому входусчетчика, выходы которого соединены с соответствующими входами де Ошифратора, первый выход которогоподключен к первому входу первоготриггера и второму входу счетчика,третий вход которого соединен свыходом первого элемента И, второйвход которого подключен к вторымвходам второго и четвертого элементов И и выходу второго У 9 иггера,первый вход которого является входом блока, второй вход второго триг- , рогера соединен со вторым входомтретьего элемента И, вторым выходомдешифратора и вторым входом первоготриггера, выход которого соединенс третьими входами второго и третьего элементов И.3. Устройство по п. 1, о т л и -ч а ю щ е е с я тем, что первыйблок формирования топологии графа содержит Ягруппу элементов И, при 34 10чем первые входы элементов И -той(=1,2 Мгруппы объединеныи являются 1 -тым входом первой группы блока, вторые входы элементов И1 -той группы объединены и являются-тым входом второй группы блока,выход-того элемента И 1-той 1==1,2 М) группы является 1-тымвыходом-той группы блока.4, Устройство по п. 1, о т л и -ч а ю щ е е с я тем, что второй блокформирования топологии графа содержитД -2 группы элементов И, причем первые входы всех элементов И 1 -той(,1=1,2 М) группы объединеныи являются 1 -тым входом первой груп-пы блока, вторые входы-тых элементов И всех групп объединены и яв-ляются-тым входом второй группыблока, выход 1 -того элемента ИВ-той группы являетсй-тым выходом 1 =1,2 Й -1- 6 ) 5 -той группы блока.Источники информации,принятые во внимание при экспертиз1. Авторское свидетельство СССРВ 468244, кл, С Об Г 15/36, 1971,2. Авторское свидетельство СССРпо заявке У 2414862/18-24,кл. 6 06 Г 15/36, 1976 (прототип)./5 к илиал ППП "Патент", г. Ужгород, ул. Проектная Составитель Л.ТереРедактор В,федотов Текред Т.Маточка Заказ 10726/14 Тираж 748 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, Ра