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

 

Изобретение относится к вычислительной технике и может быть использовано для оценки надежности систем, описываемых графами. Целью изобретения является расширение функциональных возможностей устройства за счет нахождения независимых путей в графе между двумя вершинами.. Устройство состоит из матричной модели графа, групп элементов ИЛИ, И, НЕ, блока вычисления кода, максимального числа регулирующих триггеров и триггеров, элементов И, ИЛИ, НЕ и И-НЕ, генератора тактовых импульсов дешифратора. Устройство позволяет находить минимальный путь в графе. В него дополнительно введены группа элементов И, счетчик, дешифратор, элемент РШИ, дифференцирующая цепочка и блок памяти, которые обеспечивают последовательное нахождение минимальных путей в графе и их хранение в блоке запоминающего устройства. 2 з.п, ф-лы, 3 ил. § Гчр

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

СОЦИАЛИСТИЧЕСНИХ .РЕСПУБЛИН (5д 4 С 06 F 15/20

ВСЕ(()1";3l"" %

13 .;, списочник изоБРКткНия

К A BTOPCHOlVlY СВИДЕТЕЛЬСТВУ,13

ЬМЬАЗЫ * -- 1А

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3820766/24-24 (22) 05. 12.84 (46) 07.07.86. Бюл. ¹ 25 (72) В.Л. Львов и В.Н. Денисов (53) 68 1.333(088.8) (56) Авторское свидетельство СССР № 888134, кл. С 06 F 15/20, 1981.

Авторское свидетельство СССР № 942030, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ОПРБДЕЛЕНИЯ

МИНИМАЛЬНЫХ ПУТЕЙ В ГРАФАХ (57) Изобретение относится к вычислительной технике и может быть использовано для оценки надежности систем, описываемых графами. Целью изобретения является расширение функциональных возможностей устройÄÄSUÄÄ 1242982 Д 1 ства за счет нахождения независимых путей в графе между двумя вершинами..

Устройство состоит из матричной мо.дели графа, групп элементов ИЛИ„

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

1 12ч

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

Целью изобретения является расширение функциональных возможностей

1 устройства за счет нахождения независимых путей в графе между двумя вершинами.

На фиг. 1 представлена функциональная схема устройства на фиг. 2функциональная схема формирователя дуги, на фиг. 3 — функциональная схема блока памяти. Устройство для определения минимальных путей в графах содержит матричную модель графа 1, формирователи дуг 2 н — 2»„, первую группу элементов ИЛИ 3.,-3», вторую группу элементов ИЛИ Ц. -А», группу триггеров 5,-5„, группу элементов HE 6,-6„, первую группу элементов И 7,, -7», ре— гистрирующие счетчики 8„-8», вторую группу элементов И 9, -9„, блок 10 вычисления кода максимального числа, третью группу элементов И 11 -11„, группу регистрирующих триггеров

12,-12», блок 13 памяти, дифференцирующую цепочку 14, элемент И-НЕ 15, генератор 16 тактовых импульсов, эле— мент И 17, элемент .ИЛИ 18, элемент

HE 19, первый счетчик 20, элемент

И 21, первый дешифратор 22, второй счетчик 23, второй дешифратор 24, четвертую группу элементов И 25,-25д, вход 26 запуска устройства.

Формирователь дуги содержит первый триггер 27, первый элемент И 28, второй триггер 29, второй элемент

И 30, дифференцирующую цепочку 31.

Блок памяти содержит группу элементов И 32„- 3?„„, группу триггеров 33„- 33,»„, группу элементов ИЛИ 3ч, — 34», группу элементов HE 35 - 35

Устройство работает следующим образом.

Первоначально в модель 1 заносится информация с топологии графа.

При этом триггеры 27 соответствующих формирователей дуг 2 ij (i,j=-1,п), где п число вершин в моделируемой графе, устанавливаются в единичное состояние, если есть информационная связь из i-й вершины в j-ю вершину.

Соответствующий формирователь 2 определяется пересечением строки с номером j(j-я вершина) и столбца с номером i (i-я вершина).

2982 2

В нулевое состояние устанавливаются все триггеры 29 формирователей дуг 2 1 1 „ а также все триггеры 32 блока запоминающего устройства, пер5 вый счетчик 20 находится в сброшенном состоянии. В единичное состояние устанавливаются триггер 5q, соответствующий конечной вершине графа., и.триггер 12, соответствующий начальной вершине графа.

Устройство работает по циклам.

В каждом цикле находится один минимальный путь в графе. Пусковой сигнал с входа 26 запуска через эле1 мент ИЛИ 18 сбрасывает счетчики 8 и 23, устанавливает в нулевое состояние триггеры 5, кроме триггера 5„, триггеры 12, кроме триггера 121, и поступает,на элемент И 17. Импульсы с генератора 16 тактовых импульсов через элемент И 17 поступают на входы элементов И 7 первой группы.

Импульсы будут проходить через те элементы И 7, на вторых входах которых есть высокий потенциал. ПервоI начально все триггеры 5, кроме триггера 5», находятся в нулевом состоя.нии и нулевые потенциалы с их выходов через элементы HE б группы переходят в высокие потенциалы и подаются на вторые входы всех элементов

И 7, кроме элемента И 7». Счетные импульсы через элементы И 7, кроме элемента И 7>, поступают на регистри. рующие счетчики 8 группы. ОдновреЗ1 меннс высокий потенциал с выхода триггера 5 группы, находящегося в единичном состоянии, поступает на одноименный вход элемента И-НЕ и переводит триггеры 27 формирователей дуг одноименной строки в нулевое. состояние. Переброс триггеров 27 в нулевое состояние вызывает появление импульса через дифференцирующую цепочку 3 на входах триггеров 29, в

45 результате чего они запоминают предыдущее состояние триггеров 27 одноименного формирователя 2 дуги, а также появление импульса через элемент ИЛИ 4 второй группы на вхо5О де триггера 5 очередного столбца.

Этот импульс переводит триггер 5 в единичное состояние, вследствие чего высокий потенциал с выхода триггера 5 преобразуется элементом

-"> HE в нулевой потенциал на входе элемента И 7. Появление запрещающего потенциала на входе элемента И 7 прекращает прохождение счетных им3 1242 пульсов на регистрирующий счетчик 8 очередного столбца. При этом форми„ руется запрещение поступления счетных-импульсов на входы регистрирующих счетчиков 8, из соответствующих вершин которых исходят дуги, приводящие в сформированную ранее вершину.

Поступление счетных импульсов на регистрирующие счетчики продолжается до тех пор, пока все триггеры 5 группы не будут переведены в единичное состояние. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Наличие высоких

15 потенциалов на выходах триггеров 5 через элементы И-НЕ 15 прекращает подачу импульсов с выхода генератора

16 тактовых импульсов через элемент

И 17 на входы элементов И 7 группы.

Количество импульсов, поступивших на регистрирующие счетчики 8, соответствует кодам минимальных величин путей графа {по числу дуг, составляющих путь) из данной (в том числе .и начальной) вершины моделируемого

25 графа.

Низкий потенциал с выхода элемента И-HE 15 через элемент НЕ 19 обеспечивает подачу счетных импульсов с выхода генератора 16 через элемент

И 21 на вход счетчика 23, с выхода которого информация поступает на вход дешифратора 24. На выходе дешиф. ратора 24 поочередно возбуждаются все шины, начиная с первой и кончая и-й. При возбуждении первой выходной шины на выходе дешифратора 24 высокий потенциал поступает на вход элемента И 11 „ в результате чего . 4O высокий потенциал поступит на вторые входы элементов И 30 первого столбцаматричной модели графа. Высокий потенциал появится только на тех выходах элементов И 30 формирователей 45

2 дуг, соответствующие триггеры 29 которых находятся в единичном состоянии, поэтому только в этих строках на элементах ИЛИ 3 группы будут высокие потенциалы, которые поступят на вторые входы соответствующих элементов И 9 группы, в результате чего на входы блока 10 поступают коды с соответствующих регистрирующих счетчиков 8. Блок 10 обеспечивает выбор из поступивших на его входы кодов максимального числа и переброс соответствующего триггера (или триг982 4 геров, если таких несколько) 12 в единичное состояние.

Далее к содержанию счетчика 23 добавляется очередной импульс, на выходе дешифратора 24 возбуждается очередная шина и процесс идентификации вершин, образующих минимальный путь, продолжается до тех пор, пока триггер 12и, соответствующий последней вершине графа, не будет переведен в единичное состояние. При переходе триггера 12 в единичное состояние на выходе дифференцирующей цепочки 14 появится импульс, который поступит на вход счетчика 20, информация с выхода счетчика 20 поступит в дешифратор 22, в результате чего на его первом выходе появится высокий потенциал, который подается на вторые входы элементов И 32 первой строки блока 12. На первые входы элементов И 32 одноименного столбца подаются по-,енциалы с выходов соответствующих регистрирующих триггеров 8. Высокий потенциал появится на выходах только тех элементов

И 32 первой строки блока 12, на первые входы которых подан высокий потенциал с выходов соответствующих регистрирующих триггеров 8, идентифицирующих вершины минимального пути в графе. Под действием высоких потенциалов с выходов элементов И 32 первой .строки блока 13 триггеры 33 будут переведены в единичное состояние. Таким образом, триггеры 33 пер-. вой строки блока 13 памяти запомнят вершины первого минимального пути.

Одновременно импульс с выхода дифференцирующей цепочки 14 поступит на вход элемента ИЛИ 18 и произведет новый запуск устройства. При этом пусковой импульс с выхода элемента

ИЛИ t8 поступит также на вторые входы элементов И 25 четвертой группы. Импульс пройдет только через те элементы И 25 четвертой группы, на первые входы которых подан низкий потенциал с выходов триггеров 33 блока 13 через элементы ИЛИ 34 и элементы НЕ 35. Импульсы с выходов элементов И 25 четвертой группы поступают на вторые входы элементов

И 28 и триггеров 29 формирователей дуг 2 одноименной строки матричной модели графа 1. Импульс на входе элемента И 28 обеспечивает переключение триггера 27 в единичное состояние, если в единичном состоянии на-, 12ч 2982 ходится триггер 29, а импульс. на входе триггера 29 обеспечивает его перекпючение в нулевое состояние.

Таким образом, в модель 1 будет занесена информация о топологии первоначального графа, в котором исключены дуги,.исходящие из вершин, составляющих минимальные пути, определенные в предыдущих циклах работы устройства и под действием пускового импульса с выхода элемента ИЛИ 18 начнется новый цикл. В каждом цикле запись минимального пути осуществляется в новую строку триггеров 33 блока 13 запоминающего устройства, тка как в каждом цикле высокий потенциал с выхода дешифратора 22 будет подаваться на входы элементов

И 32 очередной строки блока 13.

Работа устройства продолжается до тех пор, пока в модели 1 не появится информация о топологии несвязанного графа, при этом все независимые пути между парой вершин будут записаны в блоке 13 запоминающего устройства. формула и з о б р е т е н и я

1. Устройство для опрепеления минимальных путей в графах, содержаmee матричную модель графа, формирователи дуг по числу строк и столбцов матричной модели графа, первую группу элементов ИЛИ по числу строк матричной модели графа, вторую группу элементов ИЛИ по числу столбцов матричной модели графа, группу триггеров по числу столбцов матричной модели графа, группу элементов НЕ по числу столбцов матричной модели графа, первую„ вторую и трет:ью группы элементов И по числу столбцов матричной модели графа, группу регистрируюших счетчиков по числу столбцов матричной модели графа, группу регистрирующих триггеров по числу столбцов матричной модели графа, элемент И-НЕ, первый и второй элементы И, элемент НЕ, первый счет— чик, первый дешифратор, блок выбора кода максимального числа и генератор гактовых импульсов, причем первый информационный выход каждого i,j-го формирователя дуги каждой i-й строки матричной модели(ь.,j= 1,2,..., п) подключен к j-му входу i — го элемента

ИЛИ первой группы, выход которого соединен с первым входом одноименного элемента И второй группы, к вто рому входу каждого элемента И второй группы подключен выход регистрируюS щего счетчика группы одноименного столбца, второй информационный выход каждого i,j-ro формирователя . дуги подключен к -му входу j-го элемента ИЛИ второй группы, выход которого соединен с входом установки в "1" одноименного триггера группы, выход каждого j-го триггера группы поцключен к входу одноименного элемента НЕ группы, к первым входам формирователей дуг одноименной строки и к j ìó входу элемента И-НЕ, выход каждого элемента НЕ группы поцключен к первому входу одноименного элемента И первой группы, выход каждого элемента И первой группы подключен к счетному входу одно— именного регистрирующего счетчика группы, выходы элементов И второй группы подключены соответствеí io к входам блока выбора кода максимального числа, каждый выход группы информационных выходов которого подключен к входу установки в "1" со30 ответствующего регистрирующего триггера группы, выход каждого регистрирующего триггера соединен с первым входом одноименного элемента И третьей группы, выход каждого элемента И третьей группы подключен к вторым информационным входам фор35 мирователей дуг одноименного столбца матричной модели графа, выход генератора тактовых импульсов подключен к первым входам первого и второго

4О элементов И, выход первого элемента

И соединен с вторыми входами элементов И первой группы, выход элемента

И-HE подключен к второму входу первого элемента И, к входу элемента

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

2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что формирователь дуги матричной модели графа содержит первый и второй триггеры, первый и второй элементы И, дифференцирующую цепочку, причем вход установки в "О" первого триггера соединен с первым информационным входом формирователя дуги, а выход первого триггера подключен к входу дифференцирующей цепочки, выход которой соединен с входом установки в "1" второго триггера и является первым. информационным выходом формирователя дуги, выход второго триггера соединен с первыми входами первого и второго элементов"И, выход первого .элемента И подключен к входу установки в "1" первого триггера, второй вход второго элемента И является вторым информационным входом формирователя дуги, а выход второго элемента И является вторым информационным выходом формирователя дуги, второй вход первого элемента И и вход установки в "О" второго триггера явля20 ются третьим информационным входом формирователя дуги.

3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок памяти содержит ячейки памяти по числу строк и столбцов матричной модели графа, группу элементов ИЛИ по числу столбцов матричной модели графа, группу элементов НЕ по числу столбцов матричной модели графа, каждая ячейка памяти содержит элемент И

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

j-й строки объединены и являются второй группой информационных входов блока памяти.

1242932

1242982

Составитель Т.Сапунова

Редактор В.Иванова Техред М.Ходанич Корректор Г. Решетник

Тираж 671 Подписное

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

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

Заказ 3707/49

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4