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

СОЮЗ СОВЕТСКИХСОЦИАЛ СТИЧЕСНИРЕСПУБЛ 1 Н 19) (1 И/2 1)4 СО ГОСУДАРСТВЕННЫЙПО ИЗОБРЕТЕНИЯМ ИПРИ ГКНТ СССР ИТЕТРЫТИЯМ 1 к,пл.;11,1 ОПИСАН ЕЛЬСТ ост А.Ч ЯК ство СССР20, 1978 о С 20,984. 54) УСРАФОВ57) Из бретен й техн е отнке иоценк ится к вычис -жет быть иснадежности тельн пользован А ВТОРСНОМУ СОИ(71) Институт проблем ндолговечности машин АН(56) Авторское свидетелУ 843738, кл. С 06 Р 15Авторское сюидетельсВ 174937, кл. С 06 Р 1 ОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ БРЕТЕНИЯ сложных систем на этапе проектирова-ния за счет определения топологической надежности графа систем). Цельизобретения - расширение функциональных возможностей за счет определенияпоказателей топологической надежности графа системы, В устройство, содержащее матрицу элементов И 4, наборное поле 9, дешифратор 3 и счет-.чик 2, дополнительно введены блокуправления, группа элементов ИЛИ 5,блок 6 памяти параметров достижимости, группа блоков 7 памяти показателей топологической надежности, группа блоков 8 определения минимума,блок 1 О перебора подмножеств, блок11 подсчета количества разорванныхСчетчик 2 предназначен для подсчета количества тактовых импульсов, формируемых блоком управления, и формирования в соответствии с количеством подсчитанных импульсов двоичного кода номера строки, соответствующей вершине, от которой определяется достижимость ко всем остальным вершинам.Дешифратор 3 предназначен для преобр аз ования двоично го кода номер а строки в унитарный код номера стро 50 Изобретение относится к вычисли-тельной технике и может быть использовано для оценки надежности сложных систем на этапе проектированияза счет определения топологическойнадежности графа систею.Цель изобретения - расширениефункциональных возможностей устройства за счет определения показателей 1 Отопологической надежности (ПТН) графа систем.Основным параметром ПТН дпя любойпары вершин графа является наименьшее число дуг графа, разрыв которыхприводит к разрыву всех ориентированных маршрутов из первой вершины парыво вторую.На фиг, 1 приведена функциональная схема устройства; на фиг, 2 - 20функциональная схема блока управления; на фиг. 3 - функциональная схема блока памяти ПТН; на фиг, 4 - функциональная схема блока перебора подмножеств; на фиг, 5 - функциональнаясхема блока подсчета количества разорванных дуг.Устройство состоит из блока 1 управления, счетчика 2, дешифратора3, матрицы Р Р элементов И 4, 30группы элементов ИЛИ 5,блока 6 памяти параметров достижимо сти, группыблоков 7 памяти ПТН, блоков 8 определения минимума, наборного поля 9,1 лока 10 перебора подмножеств, блока11 подсчета количества разорванныхдугБлок 1 управления предназначендпя задания алгоритма работы устройства. Он формирует импульсы тактовой 40частоты, поступающие на счетчик, импульсы частоты циклов, поступающиена блок пере бор а по дмноже ст в, и уйравляет занесением единицв блокипамяти ПТН перед началом определения 45этих параметров. ки, единичный разряд которого соответствует номеру опрашиваемой строки.Элементы И 4 предназначены для моделирования дуг графа. Единичный уровень сигнала на втором входе элемента И 4 определяет наличие дуги из вершины, соответствующей номеру строки, в вершину, соответствующую Номеру столбца матрипы. Единичные уровни на третьих входах появляются при опросе элементов, принадлежащих соответствующим строкам в процессе определения параметров достижимости вершин а нулевые уровни на первых . входах этих элементов соответствуют разрываемлм дугам при определении ПТН.Элементы ИЛИ 5 предназначены для объединения выходов трехвходовых элементов И по столбцам и, таким образом, обеспечивают возможность. моде лирования достижимости по всем возможным задействованным маршрутам графа.Блок 6 памяти параметров достижимости предназначен для хранения кодов, соответствующих параметрам достижимости между вершинами.Блоки 7 памяти ПТН предназначены для хранения двоичных кодов, соответствующих максимальному количеству дуг, которые необходимо разорвать, чтобы потерялась достижимость вершины М из вершины К, При этом по адресу К блока 7 М памяти ПТН хранится двоичный код соответствующий минимальномуФколичеству дуг, которые должны быть разорваны для того, чтобы была потеряна достижимость вершины Миз вершины К.Блоки 8 определения минимума предназначены дпя сравнения двоичных кодов, хранящихся в блоках памяти ПТН и соответствующих текущим значениям ПТН для каждой пары вершин, с двоичными кодами, соответ ст вующими количеству разорванных дуг. При этом, если количество разрываемых дуг, приводящее к потере достижимости из вершины К в вершину М, меньше текущего значения ПТН, то это текущее значение ПТН заменяется числом, соответствующим меньшему количеству дуг, разрыв которых приводит к потере достижимости из вершины К в вершину М,Наборное поле 9 предназначено дпя формирования топологии графа, С помощью наборного поля 9 на вторых входах .элементов И 4 задаются единичные или нулевые уровни в соответствии с14729 наличием или отсутствием дуг междувершинами графа,Блок 1 О перебора подмножествпредставляет собой специальный снет 5чик и предназначен для перебора всехвозможных сочетаний разрываемых дугпри определении ПТН, Разрядность этого счетчика определяется количествомдуг в исследуемом графе и задаетсяавтоматически с наборного поля приформировании топологии графа, приэтом количество нулей в его разрядахсоответствует количеству разрываемыхдуг при определении ПТН. 15Блок 1 подсчет а кол иче ств а р аз орванных дуг предназначены для подсчета количества нулей в блоке 1 О перебора подмножеств и представлениячисла, со ответ ст вующе го этому количеству, в двоичном коде.При описании принципа работы устройства вводятся следующие понятия,Такт - элементарная операция, врезультате выполнения которой получаются параметры достижимости из одной вершины графа во все остальные.Подготовительный цикл - последовательность операций, в результате выполнения которых в блоке памяти пара- З 0метров достижимости формируются коды,соответствующие исходным достижимостям между всеми вершинами графа приисходной топологии (без разрыва дуг).Подготовительный цикл состоит из З 5Р тактов, где Р - количество вершинв исследуемом графе.Рабочий цикл - последовательностьопераций, в результате выполнения которых в блоке памяти параметров достижимости формируются коды, соот -ветствующие текущим достижимостям,а в блоках памяти ПТН формируютсякоды, соответствующие текущим ПТН,Принцип работы устройства заключается в последовательной модификациитекущих ПТН (каждый этап модификациисостоит из одного подготовительногоцикла и одного рабочего цикла) наоснове информации об изменении достижимости между вершинами и о количестве дуг, разрываемых на данном этапе модификации, при исчерпывающемпереборе подмножеств.Перед началом работы устройствана наборном поле 9 набирается топология исследуемого графа: если междувершиной К и вершиной М имеется дуга,то на второй вход соответствующего 15элемента И 4 подается единичный сигнал.Работа устройства начинается послеподачи команды "Пуск" на первый входблока 1 управления и формированиязапускающего импульса, по которомучерез блок управления устанавливаетсяисходное состояние счетчика 2 и наего первый вход начинают поступатьтактовые импульсы, После поступленияиз блока 1 управления на счетчик 2первого импульса счетчик 2 устанавливается в первое состояние, которое дешифрируется дешифратором 3, При этомна первый элемент ИЛИ 5 подается единичный сигнал, который проходит наего выход и подается на третьи входыэлементов И 4, образующих первую строку матрицы. На первые входы элементовИ 4 этой строки подается единичныйсигнал от блока 10 перебора подмножеств, а на вторые входы этих элеметов поступают единичные или нулевыесигналы от наборного поля 9 в соответствии с топологией графа. На техвыходах элементов И 4 первой строки,которые задействованы в структуреграфа, формируются единичные сигналы,С выходов элементов И 4 первой строки, на которых сформированы единичные сигналы, последние. поступают насоответствующие входы соответствующих элементов ИЛИ 5. С выходов указанных элементов 5 ИЛИ сигналы поступаютна третьи входы элементов И 4 соответствующих строк и проходят на выходызадействованных в структуре графаэлементов И 4, В результате на выходах тех элементов ИЛИ 5, индексы которых соответствуют вершинам, имеющимдостижимость из первой вершины, формируются единичные сигналы, которыезаписываются по первому адресу блока6 памяти параметров достижимости.Адрес в этом блоке выбирается попервому входу, куда поступает сигнал от счетчика 2, Таким образом,после окончания первого такта по первому адресу блока 6 памяти параметров достижимости записываются единицы в те разряды, номера которых соответствуют вершинам, имеющим достижимость из первой вершины,После перехода счетчика 2 во второе состояние такая же процедуравыполняется по отношению к второйстроке, После окончания Р-го тактапервый подготовительный цикл завер 14 2915шается, в результате чего в блоке 6 памяти параметров достижимости по всем адресам записана информация о достижимости всех вершин из каждой вершины, при этом номер адреса в блоке 6 памяти параметров достижимости определяет вершину, из которой определяется достижимость, а номер разряда в этом адресе - номер вершины, 10 в которую определяется достижимость из этой вершины.На первом подготовительном цикле, как и на всех последующих, от блока 10 перебора подмножеств на первые 15 входы элемеитов И 4 поступают единичные сигналы, поэтому на всех подготовительных циклах достижимость определяется для исходного графа, те, при всех неразорванных дугах. Кроме 20 того,на первом подготовительномцикле .по команде из блока 1 управления по всем адресам всех блоков 7 памяти ПТН записываются "1", которые являются исходными фиктивными ПТН. 25На первом рабочем цикле на блок 10 перебора подмножеств от блока 1 управления подается импульс и на его выходе формируется двоичный код, нулевые разряды которого соответствуют 30 разрывам определенных дуг, при этом на первых входах соответствующихэлементов И 4 - 0, Дпя графа с разорванными дугами анапогично описанному определяется совокупность параметров достижимости. При этомна К-м такте каждого рабочего цикла информация в разрядах адреса К блока 6 памяти параметров достижимости может меняться, т. е. в определенных разря дах может происходить замена записанных туда "1" на "0". Разряд М адреса К блока 6 памяти параметров достижимости соединен с пятым входом соответствующего блока 7 памяти ПТН, Ког да в разряде М адреса К блока 6 памяти параметров достижимости происходит замена "1" на "0", то при напичии разрешающего сигнала на четвер-, том входе соответствующего блока 7 б 0 памяти ПТН производится перезапись содержимого блрка 11 подсчета количества разорванных дуг по адресу Кэтого блока 7 памяти ПТН. Разрешающий сигнал на четвертый вход блока 7 памяти ПТН подаетсятогда, когда число в блоке 11 подсчета количества разорванных дуг меньше числа, записанного в блоке 7 памяти ПТН. Таким образом, на каждом тактекаждого рабочего цикла по соответствующим адресам блоков 7 памяти ПТНпроисходит запись содержимого блока11 количества разорванных дуг. В результате происходит последовательнаямодификация ПТН в процессе перебораразличных комбинаций разорванных дуг.Блок 1 управления (фиг. 2) состоит из з адающего генератор а 1. 1,формирователя 1.2, триггера 1. 3,счетчика 1,4 циклов, триггера 1.5,элемента И 1.6. Генератор 1,1 предназначен для синхронизации работыблока управления и устройства в целом.Формирователь 1,2 представляет собойодновибратор и предназначен дпя установки в исходное состояние счетчика 1.4 циклов, и триггера 1.5. Триггер 1.3 предназначен дпя запуска генератора 1,1 и формирователя 1,2 покоманде "Пуск", подаваемой операторомс пульта упранления, и остановкигенератора после окончания работыустройства, Счетчик 1.4 циклов предназначен дпя подсчета количествациклов по команде с последнего выхода,дешифратора 3 и формирования командна блок 10 перебора подмножеств.Триггер 1,5 предназначен для формированияинтервала заполнения единицами блоков7 памяти ПТН на первом подготовительном цикле. Элемент И 1,6 предназначендпя формирования последовательностиимпульсов записи единиц в блоки 7 па"мяти ПТН на первом подготовительномцикле,Блок упранления работает следующимобразом, После выдачи операторомкоманды "Пуск" на первый вход блокауправления триггер 1,3 по входу Яустанавливается в единичное состояниеи на его выходе Формируется единичный сигнал, который запускает формирователь 1,2 и разрешает работу генератора 1, 1, Дпительность импульса наныходе формирователя 1.2 приблизительно равна длительности импульса генератора, и по нему устанавливаются внулевое состояние счетчик 1.4 циклов и триггер 1,5. Импульсы, Формируемые генератором, через первый выходблока упранления поступают на входсчетчика 2 (см, фиг. 1). После окончания одного цикла (подготовительногоили рабочего) на последнем (и+1)-мвыходе дешифратора 3 формируется сигнал, который по второму входу блокауправления запускает счетчик 1.4 циклов. После каждого нечетного цикла (подготовительного) на первом выходе счетчика 1.4 циклов формируется сигнал, который через выход блока 1 управления поступает на блок 10 подсчета количества подмножеств, В течение первого подготовительного цикла с инверсного выхода триггера 1.5 10 единичный сигнал поступает на второй вход элемента И 1.6, В результате дается разрешение на прохождение по первому входу элемента И 16 на выход блока 1 управления .импульсов, 15 которые поступают на первые входы блоков 7 памяти ПТН и дают разрешение на запись туда единиц на первом подготовительном цикле, После окончания первого подготовительного цикла по 20 команде с первого выхода счетчика 1. 4 циклов триггер 1.5 устанавливается в единичное состояние, при этом на его инверсном выходе устанавливается нулевой сигнал, который эапреща ет прохождение импульсов через элемент И 16, После формирования всех подготовительных циклов на соответствующем выходе счетчика 1,4 циклов формируется сигнал, по которому триг гер 1.3 по входу К устанавливаетсяв нулевое состояние и нулевым сигналом на своем выходе запрещает работу генератора 1;1, На этом работа устройства заканчивается, 35Блоки 7 памяти ПТН отличаются организацией записи. Когда на второй вход блока 7 памяти ПТН (фиг. 3) поступает адресный код, по соответствующему адресу производится выборка 40 информации, которая с задержкой на время выборки формируется на его первых выходах и подается на блок 8 определения минимума, где сравнивается с текущим значением содержимого бло ка 11 подсчета количества разорванных дуг. После задержки на время сравнения на выходе соответствующего блока 8 определения минимума может сформироваться сигнал разрешения эаписи (в зависимости от результата сравнения). Таким образом, сигнал разрешения записи на четвертом входе блока 7 памяти ПТН формируется с некоторой суммарной задержкой по отношению к сигналу адресного кода на первом входе этого же блока. Сигнал разрешения записи на входе блока,6 памяти параметров достижимости формируется после подачи адресного кода на первый вход блока 6 через время, требуемое на то, чтобы на одном или нескольких выходах блока 6 памяти параметров достижимости произошел переход единичного сигнала в нулевой,Блок 10 перебора подмножеств (фиг, 4) представляет собой специальный счетчик, с прямых разрядных выходов которого подаются сигналы блокировки на те элементы И 4 матрицы, на вторые входы которых с наборного поля 9 подаются "0", подтверждая таким образом закрытое состояние этих элементов, а с инверсных разрядных выходов этого счетчика сигналы одаются на первые входы блока 11, ри подаче от наборного поля 9 на входы блока 10 нулей запираются нижние вентили И элементов И/ИЛИ и открываются верхние, При этом сигнал переноса с инверсного выхода триггеа, предшествующего з аблокированнойжней части элемента И/ИЛИ, блокиуется и на счетный вход следующего риггер а по ступает тот же сигнапкоторый поступает на счетный вход предшествующего триггера. Таким образом, те разряды счетчика, на которые от наборного поля 9 поступают "0", оказываются блокированными и в работе счетчика не участвуют. Эти же нулевые блокирующие сигналы, поступащцие от наборного поля 9, подаются на разрешающие входы элеменгов И, которые включены после прямых и инверсных выходов триггеров. Эти элементы И оказываются закрытыми, и на входы элементов И 4 и входы блока 11 подаются нулевые сигналы. Это означает, что соответствующие элементы И 4 и входы блока 11 в работе устройства не участвуют, поскольку они соответствуют йезадействованным в топологии графа дугам, а перебор дуг при моде; лировании их разрыва соответствует тем логическим элементам 4, на первые входы которых с наборного поля 9 поступают "1",Блок 11 подсчета количества разорванных дуг (фиг. 5) состоит иэ формирователя 11,1, представляющего собой одновибратор, счетчиков 11,2 и 11,3, генератора 11.4 и мультиплексора 11,5, На первую группу входов блока 11 подсчета количества разорванных дуг подается код перебора подмножеств от блока 10 перебора подмно 1472915жеств. По сигналу с выхода блока 1 управления на второй вход блока 11 подсчета количества разорванных дуг поступает запускающий сигнал. На каждом подготовительном цикле этот сигнал нулевой, а на каждом рабочем цикле - единичньй. При окончании каждого подготовительного цикла с помощью формирователя 11,1 счетчики 11,2 10 и 11,3 сбрасываются и на генератор 11.4 с выхода переполнения счетчика 11,2 поступает разрешающий сигнал.Генератор 11,4 работает до заполнения счетчика 11.2. С помощью мультиплексора 1.5 на его входе формируются импульсы, количество которых соответствует количеству единиц в коде, поступающем от блока 10 перебора подмножеств. Эти импульсы подсчитываются счетчиком 11.3, и на его выходе формируется двоичный код, соответствующий количеству единиц в коде, поступающем от блока 10 перебора подмножеств, которое соответст 25 вует количеству разорванных дуг.Формула изобретенияУстройство дпя исследования гра фов, содержащее матрицу РФ Р элементов И (Р - количество вершин в исследуемом графе) без диагональных элементов главной диагонали, наборное поле, дешифратор, счетчик, информа ционные выходы которого соединены с информационными входами дешифратора, отличающееся тем, что, с целью расширения функциональных возможностей за счет определения 40 показателей топологической надежности графа систекв, в него введены блок управления, группа элементов ИЛИ, блок памяти параметров достижимости, группа блоков памяти параметров топо логической надежности, группа блоков определения минимума, блок подсчета количества разорванных дуг, блок перебора подмножеств, первый выход блока управления соединен сб счетным 50 входом счетяика, второй выход соедицен с первыми входами блока подсчета количества разорванных дуг и блока перебора подмножеств, третий выход соединен с первыми входами блоков памяти показ ателей тополо гиче ской надежности группы и вторыми входамиблока перебор а подмноже ст в, выходыкоторого соединены с первыми входами соответствующих элементов И матри.цы и вторыми входами блока подсчетаколичества разорванных дуг, а третьивходы блока перебора подмножеств соединены с соответствующими выходаминаборного поля и вторыми входамисоответствующих элементов И матрицы,информационные выходы счетчика соединены с первыми входами блока памяти параметров достижимости и вторыми входами блоков памяти параметровтопологической надежности группы,информационные выходы которых соединены с первыми информационными входами соответствующих блоков определенияминимума группы, вторые информационные входы которых соединены с выходами блока подсчета количества разорванных дуг и третьими входами блоковпамяти показателей, топологической надежности группы, четвертые входы которых соединены с выходами соответствующих блоков определения минимумагруппы, а пятые входы соединены ссоответствующими выходами блока памяти параметров достижимости, вторнвходы которого соединены с выходамисоответствующих элементов ИЛИ группыи третьими входами элементов И соответствующей строки, матрицы, выход(К,М)-го элемента И матрицы (где Ки М - номера строки и столбца матрицы соответственно, которым принадлежит элемент) соединен с (Р)-м входом М-го элемента ИЛИ группы, К-йвыход дешифратора (где К изменяетсяот 1 до Р) соединен с нулевым вхо-.дом К-го элемента ИЛИ группы, (Р+1)-йвыход дешифратора соединен с вторымвходом блока управления, первый входкоторого является входом пуска устройства,67 Заказ 1712/4ВНИИПИ Госуда Подписное тениям и открытия ская наб., д. 4/5 твенного комитета по иэо 113035, Москва, Ж, Р гарина, 1 евно-издательский комбинат "Патент", г. Ужгород,роиз Гбыабл, 1