Устройство для определения минимальных путей в графах Советский патент 1986 года по МПК G06F15/173 

1242982

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

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

На фиг. 1 представлена функциональная схема устройства на фиг. 2- функциональная схема формирователя дуги на фиг. 3 - функциональная схема блока памяти.

Устройство для определения минимальных путей в графах содержит матричную модель графа 1, формирователи дуг 2,,, первую группу элементов ИЛИ 3,,-3(,, вторую группу элементов ИЛИ 4,-4„, группу триггебг п

ров , группу элементов НЕ первую группу элементов И 7,| -7, ре- гистрируюид е счетчики , вторую группу элементов И 9,-9, блок 10 вычисления кода максимального числа, третью группу элементов И 11,-11р, группу регистрирующих триггеров 12j-12f,, блок 13 памяти, дифференцирующую цепочку 14, элемент И-НЕ 15 генератор 16 тактовых импульсов, элемент И 17, элемент ДПИ 18, элемент НЕ 19, первьй счетчик 20, элемент И 21, первый дешифратор 22, второй счетчик 23, второй дешифратор 24, четвертую группу элементов И вход 26 запуска устройства.

Формирователь дуги содержит первый триггер 27, первый элемент И 28 второй триггер 29, второй элемент И 30, дифференцирующую цепочку 31.

Блок памяти содержит группу элементов И 32,|- 32„р,, группу триггеров 33,,- 33,,, группу элементов ТИЛИ 34,- 34, группу элементов НЕ 35,-

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

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

0

5

0

5

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

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

В каждом цикле нах;одится один миним-альный путь в графе. Пусковой сигнал с входа 26 запуска через элемент ИЛИ 18 сбрасывает счетчики 8 и 23, устанавливает в нулевое состояние триггеры 5, кроме триггера 5, триггеры 12, кроме триггера 12, и поступает на элемент И 17. Импульсы с генератора 16 тактовых импульсов через элемент И 17 поступают на входы элементов И 7 первой группы. Импульсы будут проходить через те элементы: И 7, на вторых входах кото- есть высокий потенциал. Первоначально все триггеры 5, кроме триггера 5, находятся в нулевом состоя- .нии и нулевые потенциалы с их выходов через элементы НЕ 6 группы переходят в высокие потенциалы и подаются на вторые входы всех элементов И 7, кроме элемента И,7„. Счетные импульсы через.элементы И 7, кроме элемента И 7,, поступают на регистрирующие счетчики 8 группы. Одновре- менно высокий потенциал с выхода триггера 5 группы, находящегося в единичном состоянии, поступает на одноименный вход элемента И-НЕ и переводит триггеры 27 формирователей дуг одноименной строки в нулевое. состояние. Переброс триггеров 27 в нулевое состояние вызывает появление импульса через дифференцирующую цепочку 31 на входах триггеров 29, в результате чего они запоминают предыдущее состояние триггеров 27 одноименного формирователя 2 дуги, а та1сже появление импульса через элемент ИЛИ 4 второй группы на входе триггера 5 очередного столбца. Этот импульс переводит триггер 5 в единичное состояние, вследствие чего высокий потенциал с выхода триггера 5 преобразуется элементом 55 НЕ в нулевой потенциал на выходе элемента И 7. .Появление запрещающего потенциала на входе элемента И 7 прекращает прохождение счетных им0

40

45

50

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

Поступление счетных импульсов на регистрирующие счетчики продолжается до тех пор, пока все триггеры 5 группы не будут переведены в единичное состояние. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Наличие высоких потенциалов на выходах триггеров 5 через элементы И-НЕ 15 прекращает подачу импульсов с выхода генератора 16 тактовых импульсов через элемент И 17 на входы элементов И 7 группы. Количество импульсов, поступивших на регистрирующие счетчики 8, соответствует кодам минимальных в еличин путей графа (по числу дуг, состав- ляющих путь) из данной (в том числе .и начальной) вершины моделируемого графа.

Низкий потенциал с выхода элемента И-НЕ 15 через элемент НЕ 19 обеспечивает подачу счетных импульсов с выхода генератора 16 через элемент И 21 на вхой счетчика 23, с выхода которого информация поступает на вход дешифратора 24. На выходе дешифратора 24 поочередно возбуждаются все щины, начиная с первой и кончая п-й. При возбуждении первой выходной шины на выходе дешифратора 24 высокий потенциал поступает на вход элемента И llj/, в результате чего высокий потенциал поступит на вторые входы элементов И 30 первого столбца матричной модели графа. Высокий потенциал появится только на тех выходах элементов И 30 формирователей 2 дуг, соответствующие триггеры 29 которых находятся в единичном состоянии, поэтому только в этих строках на элементах ИЛИ 3 группы будут высокие потенциалы, которые поступят на вторые входы соответствующих элементов И 9 группы, в результате чего на входы блока 10 поступают коды с соответствующих регистрирующих счетчиков 8. Блок 10 обеспечивает выбор из поступивших на его входы кодов максимального числа и переброс соответствующего триггера (или триг10

15

20

5

429824

геров, если таких несколько) 12 в

единичное состояние.

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

Одновременно импульс с выхода дифференцирующей цепочки 14 поступит на вход элемента ИЛИ 18 и произведет новый запуск устройства. При этом пусковой импульс с выхода элемента ИЖ 18 поступит также на вторые входы элементов И 25 четвертой груп- пы. Импульс пройдет только через те элементы И 25 четвертой группы, на первые входы которых подан низкий потенциал с выходов триггеров 33 блока 13 через элементы ИЛИ 34 и эле- 0 менты НЕ 35. Импульсы с выходов

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

ходится триггер 29, а импульс, на входе триггера 29 обеспечивает его переключение в нулевое состояние.

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

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

Формула изобретения

1. Устройство для определения минимальных путей в графах, содержащее матричную модель графа, формирователи дуг по числу строк и столбцов матричной модели графа, первую группу элементов ИЛИ по числу строк матричной модели графа, вторую группу элементов ИЛИ по числу столбцов матричной модели графа, группу триг- г еров по числу столбцов матричной модели графа, группу элементов НЕ по числу столбцов матричной модели графа, первую, вторую и третью группы элементов И по числу столбцо матричной модели графа, группу ре- гиcтpиpyюш x счетчиков по числу столбцов матричной модели графа, группу регистрирующих триггеров по числу столбцов матричной модели графа, элемент И-НЕ, первый и второй шементы И, элемент -НЕ, первый счетчик, первый дешифратор, блок выбора кода максимального числа и генерато тактовых импульсов, причем первый информационный выход каждого i,j-ro формирователя дуги каждой i-й строк матричной модели(i,,2,..., п) подлслючен к j-му входу i-ro элемент 11ПИ первой группы, ньпкод которого

5

0

5

0

5

0

5

O

5

соединен с первьм входом одноимен- .ного элемента И второй группы, к вто рому входу каждот о элемента И второй группы подключен выход регистрирующего счетчика группы одноименного столбца, второй информационный выход каждого i,j-ro формирователя . дуги подключен к i-му входу элемента FUIH второй группы, выход которого соединен с входом установки в 1 одноименного триггера группыj выход каждого j-ro триггера группы подключен к входу одноименного элемента НЕ группы, к первым входам формирователей дуг одноименной строки и к j- i-ty входу элемента И-НЕ, выход каждого элемента НЕ группы подключен к первому входу одноименного элемента И первой группы, выход каждого элемента И первой группы подключен к счетному входу одноименного регистрирующего счетчика группы, выходы элементов И второй группы подключены соответственно к входам блока выбора кода максимального числа, каж,с(ый выход группы информационных выходов которого подключен к входу установки в 1 соответствующего регистрирующего триггера группы, выход каждого регистрирующего триггера соединен с первым входом одноименного элемента И третьей группы, выход каждого элемента И третьей группы подключён к вторым информационным входам фор- 1 1ирователей дуг одноименного столбца матричной моделитрафа, выход генератора тактовых импульсов подключен к первьм входам первого и второго элементов И, вькод первого элемента И соединен с вторыми входами элементов И первой группы, выход элемента И-НЕ подключен к второму входу первого элемента И, к входу элемента НЕ, вькод которого соединен с вторым входом второго элемента И, выход которого подключен к счетног-гу входу первого счетчика, выход кото- эого соединен с входом первого дешифратора., выходы первого .дешифратора соединены соответственно с вторы- ivfli входами элементов И третьей :группы,, отличающееся тем, что, с целью расширения функ- циональньпс возможностей путем нахождения независимых путей в графе между двумя вершинами, в него введены элемент ИЛИ, второй счетчик.

второй дешифратор, блок памяти, дифференцирующая цепочка и четвертая группа элементов И по числу строк матричной модели графа, причем пер вый вход элемента ИЛИ является входом запуска устройства, а второй вход элемента ИЛИ соединен с выхо- , дом дифференцирующей цепочки, вход которой соединен с выходом п-го регистрирующего триггера группы, выход элемента ИЛИ соединен с первыми входами элементов И четвертой груп- пы, с третьим информационным входом формирователя дуги п-й строки первого столбца матричной модели графа, с третьим входом первого элемента И, с входом обнуления первого счетчика, с входами обнуления триггеров группы и с входами обнуления регистрирующих счетчиков группы, счетный вход второго счетчика подключен к выходу дифференцирующей цепочки, а его выход соединен с входом второго дешифратора, выходы которого соответственно соединены с первой группой информационных входов блока памяти, каждый вход второй группы ИНФОРМАЦИОННЫХ входов которого соединен с выходом соответствующего регистрирующего триггера группы, каждый выход группы выходов блока памяти подключен к второму входу одноименного элемента И четвертой группы,выход каждого элемента И четвертой группы соединен с третьими входами формирователей дуг одноименной строки матричной модели графа, кроме формирователя дуги п-й строки первого столбца ; матричной модели графа.

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

15

20

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

3. Устройство по п, 1, о т л и- чающееся тем, что блок памяти содержит ячейки памяти по числу

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

5 элемента ИЛИ группы подключен к входу одноименного элемента НЕ группы, вькод каждого элемента НЕ группы является соответствующим выходом группы выходов блока памяти, первые

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

5 j-й строки объединены и являются

второй группой информационных входов блока памяти.

Ш

фив.1

(PU2.2

Редактор В.Иванова

Ф/,.lf

Фиг.З

Составитель Т.Сапунова Техред И.Ходанич Корректор Т. Решетник

Заказ 3707/49

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

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

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