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

Изобретение относится к вычислительной технике и может быть использовано для решения на графах задач йсследования сетевых структур.Цель изобретения - сокращение ап 5 паратурных затрат.На Фиг.1 представлена функциональная схема предлагаемого устройства; на Фиг.2 - граф, на примере которого рассматривается работа устройства; йа Фиг.3 - матрица длин кратчайших Путей.Устройство содержит (фиг.1) генератор 1 импульсов, распределитель 2 импульсов, элемент И 3, группу элементов 4 задержки, элемент ИЛИ 5, триггер 6, счетчик 7, группу регистров 8, матрицу 9 счетчиков 10, наборное поле 11, состоящее из горизонтальных 12 и вертикальных 13 шин и элементов 14 связи.Устройство работает следующим образом.В исходном статическом состоянии 25 обнуляются распределитель 2, триггер 6, регистры 8, счетчики 10 (которые выполняются таким образом, что их переполнение происходит при прохождении иимпульсов), В счетчик 7 заносится число, дополняющее число идо его полной емкости. Если между д-й и 3-й (. с 3) вершинами графа есть дуга, то между шиной 12, и шиой 13 устанавливается элемент 14;35 в проводящем направлении. Устройство определяет длины кратчайших путей от -й, начиная с -1 и кончая -ивершинами, до всех последующих вершин, при этом длины путей из первой во вторую вершину и из (и"1)-й в и-ю вершину не находятся, поскольку априори,известно, что длина каждого из этих путей равна единице (длины путей находятся в виде числа дуг пуф 5 тей).После подачи пускового сигнала генератор 1 начинает выдачу импульсов, первый из которых поступает на счетные входы счетчиков 7 и 10, а через открытый элемент И 3 - на вход 50 распределителя 2, который выдает единичный потенциал по первому выходу на вход записи регистра 8 и на вертикальную шину 13, наборного поля 11 и с нее на вход элемента 4 задержки, 55 через элемент ИЛИ 5 - на единичный вход триггера 6, который перебрасывается в состояние "1" и нулевым потенциалом со своего инверсного выхода закрывает элемент И 3 для прохождения следующих импульсов генератора 1. При прохождении заднего фронта первого импульса в счетчик 7 и во все счетчики 10 записывается единица.Импульс, появляющийся на выходе элемента 4 задержки, проходит на горизонтальную шину 12и через элементы 14 14, попадает на вертикальные шины 13 , 13 . С выхода шины 13 он проходит на вход элемента 4 задержки, а с выхода шины 13 - на вход элемента 4 задержки и на информацирнный вход третьего разряда регистра 8 в котором записывается единица, Вследствие этого нулевой потенциал с инверсного выхода указанного разряда, поступив на управляющий вход счетчика 10 запрещает ему дальнейший счет импульсов. Содержимое (1) этого счетчика указывает длину кратчайшего пути из первой в третью вершину графа-примера. Отметим, что нумерацию разрядов регистров 8 удобно .производить соответственно номерам вертикальных шин 13. Задним фронтом второго импульса генератора 1 в счетчик 7 и во все счетчики 10, кроме 10 записывается еще одна единица, так что их содержимое равно двум. Импульс, появляющийся на выходе элемента 4 задержки и элемента 4 задержки, проходит через горизонтальные шины 12 , 12, элементы 14, 14 , 14на вертикальные шины 13 13 и с них - на входы элементов 4, 4 задержки (на фиг.1 элемент соответствует элементу 4 ., ) и на информационные входы третьего и четвертого разрядов регистра 8 после чего и в четвертом его разряде записывается единица, а нулевой потенциал с инверс" ного выхода четвертого разряда, пос-, тупив на управляющий вход счетчика 104 запрещает ему дальнейший счет импульсов. Содержимое (2) счетчика 10, указывает длину кратчайшего пути из первой в четвертую вершину графа. Задним фронтом третьего импульса генератора 1 в счетчики 7 и 10 (кроме 10 10, ) записывается еще одна единица и их содержимое равно трем. Импульс, проявляющийся на выходе элемента 4 задержки, проходит через горизонтальную шину 12 (фиг.1, 12 , ) и элемент 14 (фиг,1, 14и) на вертикальную шину 13(фиг1, 13) и с нее - на информационный вход пятого разряда 8 записывая в нем единицу и обуславливаявыдачу ноля на управляющий вход счетчика 10,(фиг.1-10,), запрещая емудальнейший счет импульсов. Содержимое (3) счетчика 10 , указывает длину кратчайшего пути из первой в пятую вершину графа. После прохожде" 10ния импульсов генератора 1 все счетчики 10, кроме 10, 10 м, переполняются, а потому задним фронтом четвертого импульса генератора 1 счетчики 10, кРоме 103 10 10, сбра 15сываются в "9", а счетчик 7 переполняется. Сигнал переполнения с еговыхода поступает на нулевой входтриггера 6 и перебрасывает его в нулевое состояние, поэтому единичнымпотенциалом с инверсного выхода триггера 6 вновь открывается элемент И 3для прохождения пятого импульса генера.тора 1. Этим завершается первыйцикл работы устройства по нахождению 25длин кратчайших путей из первой втретью, четвертую, пятую вершины.Затем начинается второй цикл по нахождению длин кратчайших путей извторой в третью, четвертую и пятуювершины. Пятый импульс генераторапроходит через элемент И 3 на входраспределителя 2, который снимаетединичный потенциал с первого выходаи выдает его по второму выходу навход записи регистра 8, на верти"кальную шину 13 и вход элемента 4задержки и через элемент ИЛИ 5 наединичный вход триггера 6, которыйперебрасывается в единичное состояние и вновь закрывает элемент И 3для прохождения следующих импульсовгенератора 1. Далее устройство работает аналогично первому циклу и после прохождения пятого-восьмого импульсов генератора 1 в счетчики 10210 4 и 10 записываются числа 1, 1,2, указывающие длины кратчайших путейиз второй вершины в третью, четвертую и пятую вершины,Девятый импульс генератора 1 вновь 50проходит через элемент И 3 на входраспределителя 2, который снимаетединичный потенциал со второго выхода и выдает его на третий выход. Далее устройство работает аналогично 55по нахождению длин кратчайших путейиз третьей в четвертую и пятую вершины графа, После прохождения девято 394го и десятого импульсов генератора 1 в счетчики 10, 10 в (фиг,110.1,-г и 10 , ) оказываются записаннымиь;л-гчисла 1 и 2, указывающие длины кратчайших путей, а нулевой потенциал с инверсного выхода и-го разряда регистра 8 (фиг.1,8 г) поступает также на вход останова генератора 1 и прекращает работу устройства.Формула изобретения устройство для исследования пара-метров сетевых графов, содержащее элемент И, счетчик, группу регистров, матрицу счетчиков, группу элементов задержки, наборное поле, первая и вторая группы входов которого соединены в соответствии с топологией исследуемого графа, генератор импульсов, выход которого соединен с первым входом элемента И, о т л и ч а ю - щ е е с я тем, что, с целью сокращения аппаратурных затрат, оно содержит распределитель импульсов, элемент ИЛ, триггер, инверсный выход которого соединен с вторым входом элемента И, вход установки в "0" триггера соединен с выходом переполнения счетчика, вход установки в "1" триггера соединен с выходом элемента ИЛИ, входы которого соединены с соответствующими выходами распределителя импульсов, вход которого соединен с выходом элемента И, а выходы соединены с входами записи соответствующих регистров группы, входами соответствующих элементов задержки группы и соответствукицими входами первой группы наборного поля, которые соединены в соответствии с топологией исследуемого графа с информационными входами регистров группы, каждый из инверсных информационных выходов К-го регистра группы (где К=1М, а М- размерность матрицы) соединен с входом разрешения соответствующего счетчика К-го столбца счетчика матрицы, инверсный информационный выход стар-з шего разряда М-го регистра группы соединен с входом останова генератора импульсов, вход запуска которого является входом запуска устройства, счетные входы счетчиков матрицы объединены и соединены с выходом генератора импульсов, выход каждого из элементов задержки группы соединен с соответствующим входом второй группы наборного поля.1418739 ФАЗ 4 Ьг 2 Гречухин стави йи А.Кравчук Корректор И Редактор Г.Волков ираж 70 каз 4155/47 риятие, г, Ужгород, ул, Проектная, 4 но-полиграфическо роиэвод НИИПИ Государственного ко по делаи изобретений и 35, Москна, И, Раушска