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

(19) (11) 504 С 06 Р ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИОпсдн.86. Бюл, В 25Львов и В.Н. Денисов33(088.8)ское свидетельство СССРкл, С 06 Р 15/20, 1981.ое свидетельство СССРкл. С 06 Р 15/20, 1983. независимых мя вершинамиатричной моов код максииггеИЛИ,ющи тов актовых имтройствомальный путтельно вве(54) УСТРОЙСТВМИНИМАЛЬНЫХ ПУТ счетчик,дифференцяти, кото(57) Изобретен лительной техн пользовано для елй н систем, описыв изобретения яв функциональных помины, 3(21) 3820 (22) 05. 1 (46) 07.0 (72) В.Л. (53) 681. (56) Авто 9 888134,Авторс В 942030,ИЕ ИЗО МУ СВИДЕТЕЛЬСТВ ДЛЯ ОПРБДЕЛЕНИЯ ЕЙ В ГРАФАХе относится к вычиске и может быть исоценки надежности емых графами. Целью яется расширение возможностей устройства за счет нахождения путей в графе между дву Устройство состоит из м дели графа, групп элеме И, НЕ, блока вычисления мального числа регулир ров и триггеров, элеме НЕ и И-НЕ, генератора пульсов дешифратора. У позволяет находить мин в графе. В него дополн дены группа элементов И, дешифратор, элемент ИЛИ, рующая цепочка и блок пам рые обеспечивают последов нахождение минимальных пу фе и их хранение в блоке щего устройства. 2 з.п. ф1 12 чИзобретение относится к вычислительной технике и может быть исполь. зовано для количественной оценки надежности систем, описываемых графами.Целью изобретения является расширение функциональных возможностейВ устройства за счет нахождения независимых путей в графе между двумя вершинами.На фиг. 1 представлена функциональная схема устройства на фиг. 2- функциональная схема формирователя дуги, на Фиг. 3 - функциональная схема блока памяти.Устройство для определения минимальных путей в графах содержит матричную модель графа 1, Формирователи дуг 2 н -2, первую группу элементов ИЛИ 3,-3, вторую группу элементов ИЛИ 4-А, группу триггеров 5,-5, группу элементов НЕ б,-б, первую группу элементов И 7, -7, регистрирующие счетчики 8-8, вторую группу элементов И 9, -9, блок 10 вычисления кода максимального числа, третью группу элементов И 11 -11, группу регистрирующих триггеров 12,-12, блок 13 памяти, дифференцирующую цепочку 14, элемент И-НЕ 15, генератор 16 тактовых импульсов, эле - мент И 17, элемент,ИЛИ 18, элемент НЕ 19, первый счетчик 20, элемент И 21, первый дешифратор 22, второй счетчик 23, второй дешифратор 24, четвертую группу элементов И 25,-25 д, вход 26 запуска устройства.Формирователь дуги содержит первый триггер 27, первый элемент И 28, второй триггер 29, второй элемент И 30, дифференцирующую цепочку 31.Блок памяти содержит группу элементов И 32- 32, группу триггеров 33, - 33, группу элементов ИЛИ34, - ЗА, группу элементов НЕ 35- 35Устройство работает следующим образом.Первоначально в модель 1 заносится информация с топологии графа. При этом триггеры 27 соответствующих формирователей дуг 2 ц (1,3=.1,п).,где п число вершин в моделируемойграфе, устанавливаются в единичноесостояние, если есть информационнаясвязь из -й вершины в )-ю вершину.Соответствующий формирователь 2 определяется пересечением строки с номером 1-я вершина) и столбца с номером 1 (х-я вершина). 2982 2В нулевое состояние устанавливаются все триггеры 29 формирователейдуг 2 11а также все триггеры 32блока запоминающего устройства, первый счетчик 20 находится в сброшенном состоянии. В единичное состояние устанавливаются триггер 51,соответствующий конечной вершинеграфа и.триггер 12 , соответствующий начальной вершине графа.Устройство работает по циклам.В каждом цикле находится одинминимальный путь в графе, Пусковойсигнал с входа 26 запуска через эле" 1 мент ИЛИ 18 сбрасывает счетчики 8и 23, устанавливает в нулевое состоя.ние триггеры 5, кроме триггера 5,триггеры 12, кроме триггера 121,и поступает,на элемент И 17. Импульсы с генератора 16 тактовых импульсов через элемент И 17 поступают навходы элементов Ипервой группы,Импульсы будут проходить через теэлементы И 7, на вторых входах которых есть высокий потенциал. Первоначально все триггеры 5, кроме триггера 5, находятся в нулевом состоя.нии и нулевые потенциалы с их выходов через элементы НЕ б группы переходят в высокие потенциалы и подаются на вторые входы всех элементовИ 7, кроме элемента И 7. Счетные импульсы через элементы И 7, кромеэлемента И 7, поступают на регистрирующие счетчики 8 группы. Одновременнс высокий потенциал с выходатриггера 5 группы, находящегося вединичном состоянии, поступает наодноименный вход элемента И-НЕ и переводит триггеры 27 формирователейдуг одноименной строки в нулевое.состояние. Переброс триггеров 27 внулевое состояние вызывает появлениеимпульса через дифференцирующую цепочку 3 1 на входах триггеров 29, в 45результате чего они запоминаютпредыдущее состояние триггеров 27одноименного формирователя 2 дуги,а также появление импульса черезэлемент ИЛИ 4 второй группы на вхо О де триггера 5 очередного столбца,Этот импульс переводит триггер 5в единичное состояние, вследствиечего высокий потенциал с выходатриггера 5 преобразуется элементом -" НЕ в нулевой потенциал на входе элемента И 7. Появление запрещающегопотенциала на входе элемента И 7прекращает прохождение счетных им 3 1242 пульсов на регистрирующий счетчик 8 очередного столбца, При этом форми. руется запрещение поступления счетных.импульсов на входы регистрирующих счетчиков 8, из соответствующих вершин которых исходят дуги, приводящие в сформированную ранее вершину.Поступление счетных импульсов на регистрирующие счетчики продолжается до тех пор, пока все триггеры 5 группы не будут переведены в единичное состояние. Это свидетельствует о том, что все узлы исследуемого графа сформированы. Наличие высоких15 потенциалов на выходах триггеров 5 через элементы И-НЕ 15 прекращает подачу импульсов с выхода генератора 16 тактовых импульсов через элемент И 17 на входы элементов И 7 группы.20 Количество импульсов, поступивших на регистрирующие счетчики 8, соответствует кодам минимальных величин путей графа (по числу дуг, составляющих путь) из данной (в том числе .и начальной) вершины моделируемого25 графа. Низкий потенциал с выхода элемента И-НЕ 15 через элемент НЕ 19 обеспечивает подачу счетных импульсов с выхода генератора 16 через элемент И 21 на вход счетчика 23, с выхода которого информация поступает на вход дешифратора 24. На выходе дешиф ратора 24 поочередно возбуждаются .З 5 все шины, начиная с первой и кончая п-й, При возбуждении первой выходной шины на выходе дешифратора 24 высокий потенциал поступает на вход элемента И 11 в результате чего . 4 О высокий потенциал поступит на вторые входы элементов И 30 первого столбца. матричной модели графа. Высокий потенциал появится только на тех выходах элементов И 30 формирователей 45 2 дуг, соответствующие триггеры 29 которых находятся в единичном состоя. нии, поэтому только в этих строках на элементах ИЛИ 3 группы будут высокие потенциалы, которые поступят на вторые входы соответствующих элементов И 9 группы, в результате чего на входы блока 10 поступают коды с соответствующих регистрирующих счетчиков 8, Блок 10 обеспечивает выбор из поступивших на его входы кодов максимального числа и переброс соответствующего триггера (или триг 982геров если таких несколько) 12 в единичное состояние.Далее к содержанию счетчика 23 добавляется очередной импульс, на выходе дешифратора 24 возбуждается очередная шина и процесс идентификации вершин, образующих минимальный путь, продолжается до тех пор, пока триггер 12, соответствующий последней вершине графа, не будет переведен в единичное состояние. При переходе триггера 12в единичное состояние на выходе дифференцирующей цепочки 14 появится импульс, который поступит на вход счетчика 20, информация с выхода счетчика 20 поступит в дешифратор 22, в результате чего на его первом выходе появится высокий потенциал, который подается на вторые входы элементов И 32 первой строки блока 12. На первые входы элементов И 32 одноименного столбца подаются потенциалы с выходов соответствующих регистрирующих триггеров 8. Высокий потенциал появится на выходах только тех элементов ф И 32 первой строки блока 12, на первые входы которых подан высокий потенциал с выходов соответствующих регистрирующих триггеров 8, идентифицирующих вершины минимального пути в графе. Под действием высоких потенциалов с выходов элементов И 32 первой строки блока 13 триггеры 33 будут переведены в единичное состояние. Таким образом, триггеры 33 первой строки блока 13 памяти запомнят вершины первого минимального пути.Одновременно импульс с выхода диф. ференцирующей цепочки 14 поступит на вход элемента ИЛИ 18 и произведет новый запуск устройства. При этом пусковой импульс с выхода элемента ИЛИ 18 поступит также на вторые входы элементов И 25 четвертой группы. Импульс пройдет только через те элементы И 25 четвертой группы, на первые входы которых подан низкий потенциал с выходов триггеров 33 блока 13 через элементы ИЛИ 34 и эле. менты НЕ 35. Импульсы с выходов элементов И 25 четвертой группы поступают на вторые входы элементов И 28 и триггеров 29 формирователей дуг 2 одноименной строки матричной модели графа 1. Импульс на входе элемента И 28 обеспечивает переключение триггера 27 в единичное состояние, если в единичном состоянии на-, 1242982ходится триггер 29, а импульс. навходе триггера 29 обеспечивает егоперекпючение в нулевое состояние.Таким образом, в модель 1 будетзанесена информация о топологиипервоначального графа, в которомисключены дуги, исходящие из вершин,составляющих минимальные пути, определенные в предыдущих циклах работыустройства и под действием пусковогоимпульса с выхода элемента ИЛИ 18начнется новый цикл. В каждом циклезапись минимального пути осуществляется в новую строку триггеров 33блока 13 запоминающего устройства,тка как в каждом цикле высокий потенциал с выхода дешифратора 22 будет подаваться на входы элементовИ 32 очередной строки блока 13.Работа устройства продолжаетсядо тех пор, пока в модели 1 не появится информация о топологии несвязанного графа, при этом все независимые пути между парой вершин будутзаписаны в блоке 13 запоминающегоустройства,Формула и з о б р е т е н и я1. Устройство для опрепеления минимальных путей в графах, содержащее матричную модель графа, формирователи дуг по числу строк и столбцов матричной модели графа, первую группу элементов ИЛИ по числу строк матричной модели графа, вторую группу элементов ИЛИ по числу столбцов матричной модели графа, группу триггеров по числу столбцов матричной модели графа, группу элементов НЕ по числу столбцов матричной модели графа, первую вторую и третью группы элементов И по числу столбцов матричной модели графа, группу регистрируюших счетчиков по числу столбцов матричной модели графа, группу регистрирующих триггеров по числу столбцов матричной модели графа, элемент И-НЕ, первый и второй элементы И, элемент НЕ, первый счетчик, первый дешифратор, блок выбора кода максимального числа и генератор гактовых импульсов, причем первый информационный выход каждого ,-го формирователя дуги каждой 1-й строкиматричной модели 11.,1=1,2 п)подключен к 1-му входу х - го элемента ИЛИ первой группы, выход которого соединен с первым входом одноименного элемента И второй группы, к второму входу каждого элемента И второйгруппы подключен выход регистрирующего счетчика группы одноименногостолбца, второй информационный выход каждого ,1-го формирователя .дуги подключен к -му входу 3-гоэлемента ИЛИ второй группы, выходкоторого соединен с входом установкив "1" одноименного триггера группы,выход каждого 3-го триггера группыпоцключен к входу одноименного элемента НЕ группы, к первым входамформирователей дуг одноименной строки и к 1-му входу элемента И-НЕ,выход каждого элемента НЕ группыпоцключен к первому входу одноименного элемента И первой группы, выход каждого элемента И первой группы подключен к счетному входу одноименного регистрирующего счетчикагруппы, выходы элементов И второйгруппы подключены соответственнок входам блока выбора кода максимального числа, каждый выход группыинформационных выходов которого подключен к входу установки в "1" со- ЗОответствующего регистрирующего триггера группы, выход каждого регистрирующего триггера соединен с первымвходом одноименного элемента Итретьей группы, выход каждого элемента И третьей группы подключенк вторым информационным входам формирователей дуг одноименного столбцаматричной модели графа, выход генератора тактовых импульсов подключенк первым входам первого и второго 4 Оэлементов И, выход первого элементаИ соединен с вторыми входами элементов И первой группы, выход элементаИ-НЕ подключен к второму входу первого элемента И, к входу элемента 45НЕ, выход которого соединен с вторым входом второго элемента И, выход которого подключен к счетномувхоцу первого счетчика, выход которого соединен с входом первого дешифратора выходы первого дешифратора соединены соответственно с вторыми входами элементов И третьейгруппы о т л и ч а ю щ е е с ятем, что, с целью расширения функциональных возможностей путем нахождения независимых путей в графемежду двумя вершинами, в него введены элемент ИЛИ, второй счетчик, 1242982второй дешифратор, блок памяти, дифференцирующая цепочка и четвертая группа элементов И по числу строк матричной модели графа, причем первый вход элемента ИЛИ является входом запуска устройства, а второй вход элемента ИЛИ соединен с выходом дифференцирующей цепочки, входкоторой соединен с выходом п-го регистрирующего триггера группы, выход элемента ИЛИ соединен с первыми входами элементов И четвертой группы, с третьим информационным входом формирователя дуги и-й строки первого столбца матричной модели графа, с третьим входом первого элемента И, с входом обнуления первого счетчика, с входами обнуления триггеров группы и с входами обнуления регистрирующих счетчиков группы, счетный вход второго счетчика подключен к выходу дифференцирующей цепочки, а его выход соединен с входом второго дешифратора, выходы которого соответственно соединены с первой группой информационных входов блока памяти, каждый вход второй группы информа" ционных входов которого соединен с выходом соответствующего регистрирую. .щего триггера группы, каждый выход группы выходов блока памяти подключен к второму входу одноиМенного эле,мента И четвертой группы, выход каж" дого элемента И четвертой группы соединен с третьими входами формирователей дуг одноименной строки матричной модели графа, кроме формирователя дуги п-й строки первого столбца . матричной модели графа.2. Устройство по и. 1, о т л ич а ю щ е е с я тем, что формирователь дуги матричной модели графа содержит первый и второй триггеры, первый и второй элементы И, дифферен. цирующую цепочку, причем вход установки в "О" первого триггера соединен с первым информационным входом формирователя дуги, а выход первоготриггера подключен к входу дифференцирующей цепочки, выход которойсоединен с входом установки в "1"второго триггера и является первым.информационным выходом формирователядуги, выход второго триггера соединен с первыми входами первого и второго элементов"И, выход первого элемента И подключен к входу установкив "1" первого триггера, второй входвторого элемента И является вторыминформационным входом формирователядуги, а выход второго элемента Иявляется вторым информационным выходом формирователя дуги, второйвход первого элемента И и вход установки в "О" второго триггера являются третьим информационным входомформирователя дуги.3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок памяти содержит ячейки памяти по числустрок и столбцов матричной моделиграфа, группу элементов ИЛИ по числу столбцов матричной модели графа,группу элементов НЕ по числу столбцов матричной модели графа, каждаяячейка памяти содержит элемент И 0и триггер, вход которого соединенс выходом элемента И, причем выходтриггера -й ячейки памяти 1-гостолбца подключен к 1-му входу 1-гоэлемента ИЛИ группы, выход каждогоэлемента ИЛИ группы подключен к входу одноименного элемента НЕ группы,выход каждого элемента НЕ группыявляется соответствующим выходомгруппы выходов блока памяти, первыевходы элементов И ячеек памяти каждого д-го столбца объединены и являются первой группой информационныхвходов блока памяти, вторые входыэлементов И ячеек памяти каждой1-й строки объединены и являютсявторой группой информационных входовблока памяти.1242982 Составитель Т.СапуноваТехред М.Ходанич Корректор Г. Решетник ктор В.Ивано аз 3707/4 ственно-полиграфическое предприятие, г. Ужгород, ул. Проектная рои Тираж 671 ИИПИ Государстве по делам изобрет 3035, Москва, ЖПодписноеого комитета СССРий и открытийРаушская наб., д