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

СОЮЗ СОВЕТСКИ НСОЦИАЛИСТИЧЕСКРЕСПУБЛИК 9) 111) 5 1)4 С 06 Р 15 ИИ БРЕТЕНИЯ У ТВО ДЛЯ ИССЛЕДОВАНИЯ ПУюл. Р 40 в и А.Г етен хник относ може ся к вычисли- быть испольенко определения ах без конту етения являе ных возможно определения СССР1978.ССР1978. идетельс т 6 Р 15/20 етельство 6 Р 15/20 пути в елью изоб ункционал а за счет СУДАРСТ 8 ЕННЫЙ КОМИТЕТ ССО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫ ПИСАНИ К АВТОРСКОМУ СВИДЕТЕЛ(54) УСТРО ТЕИ В ГРАФ (57) Изобр тельной те зовано для аксимального ов и петель. ся расширени тей устройст ершин макси1348850 мального пути в графе. В состав устройства для исследования путей в графе входят наддиагональная матрица 1моделей 2 дуг, каждая из которых содержит счетчик 3, элемент НЕ 4 и триггер 5, две группы элементов И б идве группы счетчиков 8 и 9, группарегистров 1 О, группа схем 11 сравнения, группа элементов НЕ 12, элементИ 13, счетчик 14 и генератор 15 импульсов. Перед пуском устройства вматрицу 1 заносят информацию о топологии графа, устанавливая в 0 триггеры 5 и занося в счетчики 3 коды,дополняющие веса дуг до полной емкости счетчиков 3, и обнуляют регистры10 и счетчики 8, 9, 14. На первомэтапе работы определяют наиболееранние времена выполнения вершин графа и запоминают их на регистрах 10. 1 Изобретение относится к вычислительной технике и может быть использо вано при исследовании параметров сетевых графов без контуров и петельЦелью изобретения является расши-рение функциональных возможностей устройства за счет определения вершин максимального пути в графе.На чертеже изображена функциональная схема предлагаемого устройства.В состав устройства входит наддиагональная матрица 1 моделей 2 дуг, каждая из которых содержит счетчик 3, элемент НЕ 4 и триггер 5, две группы элементов И б и 1, две группы счет 15 чиков 8 и 9, группа регистров 10, группа схем 11 сравнения, группа элементов НЕ 12, элемент И 13, счетчик 14 и генератор 15 импульсовУстройство работает следующим образом.Перед пуском устройства в матрицу 1 заносят информацию о топологии граФа, при этом триггеры 5 устанавливаются в "0", а в счетчики 3 заносят коды, дополняющие веса дуг до полной емкости счетчиков 3. Обнуляют регистры 10 и счетчики 8, 9 и 14.После подачи сигнала на вход пуска устройства генератор 15 начинает выра З" батывать импульсы, которые подсчитыПосле этого устройство вновь приводятв исходное состояние, однако регистры10 не обнуляют, а в матрицу 1 заносят информацию о топологии графа,транспортированного относительно неглавной диагонали. После пуска устройства в счетчиках 8 фиксируются наиболее ранние времена выполнения вершин инвертированного графа, которыев прямом графе соответствуют величинам максимальных путей в конечную вершину графа, Лалее величины временвыполнения вершин прямого и инвертированного графов сравнивают на схемах11 сравнения, при этом номер схемы11 сравнения, которая выдала единичный сигнал на свой выход признака равенства,соответствует номеру вершины,через которую проходит максимальныйпуть в графе. 1 ил. 2ваются счетчиками 3 моделей 2 первой строки матрицы 1 и всеми счетчиками 8, Отсчитав число импульсов, равное весу дуги, счетчик 3 переполняется и устанавливает в единичное состояние триггер 5, Когда все триггеры 5 моделей 2 дуг всего столбца матрицы 1 перебрасываются в единичное состояние, на выходе соответствующего элемента И 6 появляется единичный потенциал, поступающий на управляющие входы счетчиков 3 моделей 2 одноименной строки матрицы 1, и те начинают счет импульсов. Кроме того, на выходе соответствующего элемента НЕ 12 появляется нулевой потенциал, и соответствующий счетчик 8 прекращает счет импульсов, Вычислительный процесс продолжается до те пор, пока на всех входах элемента И 13 не установятся единичные потенциалы. В этот момент единичный потенциал с выхода элемента И 13 поступает на вход останова генератора 15 и прекращает работу устройства. Число импульсов, зафиксированное в счетчиках 8, соответствует наиболее ранним временам выполнения вершин.Кроме того, импульс с выхода элемента И 13 поступает на вход счетчика 14, который увеличивает свое содержимое на единицу и выдает единичный потенциал на первый разряд инФормационного выхода. Появление сигнала на импульсных входах признаков записи регистров 10 обусловливает запись на ней содержимого счетчиков 8. Кроме того, единичный потенциал с первого разряда информационного выхода счетчика 14 открывает элементы И 7.При наличии в графе дуги с нулевым весом в соответствующий счетчик 3 заносят число импульсов, равное его емкости, но триггер 5 устанавливается в состояние "0", Тогда первый же импульс сбрасывает счетчик 3 в "0", что обусловливает появление единичного сигнала на выходе элемента НЕ 4 и переход триггера 5 в состояние "1",На втором этапе вновь приводят20 устройство в исходное состояние, но регистры 1 О не обнуляются, а в матрицу 1 заносят информацию о топологии инвертированного графа, т.е. данные матрицы исходного графа, но транспортированные относительно неглавной диагонали.Затем пускают устройство и в счетчиках 8 повторно фиксируются наиболее ранние времена выполнения вершин ин 30 вертированного графа, которые в прямом графе соответствуют величинам максимальных путей из вершин графа в его конечную вершину. Однако в регистры 10 содержимое счетчиков 8 уже не ,записывается, так как единичный потенциал с первого разряда информационного счетчика 14 через импульсные входы признаков записи регистров 10 не проходит, Другая особенность работы устройства на втором этапе состоит в том, что при появлении на выходе элемента И 6 единичного потенциала, обусловливающего запрещение счета импульсов соответствующим счетчиком 8, на выходе одноименного элемен та И 7 появляется единичный потенциал, разрешающий счет импульсов соответствующим счетчиком 9 до останова генератора 15 после того, как на выходе элемента И 13 появится единичный потенциал. В результате по окончании второго этапа работы устройства в счетчиках 9 будут зафиксированы наиболее поздние времена выполнения вершин прямого (исследуемого) графа. 55Появление единичного потенциала на выходе элемента И 13 приводит к увеличению содержимое счетчика 14,который выдает единичный сигнал на второй разряд информационного выхода. При поступлении единичного сигнала на входы опроса схемы 11 сравнения сравнивают числа, коды которых установлены на их входах, и при их равенстве, выдают единичные сигналы на выход признака равенства, Номер схемы 11 сравнения, которая выдала, единичный сигнал, указывает вершину, через которую проходит максимальный критический путь из первой в последнюю вершину исследуемого графа. Вершина принадлежит критическому пути, если наиболее раннее и наиболее поздйее время ее выполнения совпадают.Формула и з о б р е т е н и яУстройство для исследования путейв графе, содержащее наддиагональнуюматрицу из (Р) х (Р) моделей дуг,где Р - количество вершин в графе,две группы элементов И, группу элементов НЕ, две группы счетчиков,группу схем сравнения и генератор импульсов, вход пуска которого являетсявходом пуска устройства, причем каждая модель дуги наддиагональной матрицы содержит триггер и счетчик, выход признака переполнения которогоподключен к первому входу установки11 чв 1 триггера той же модели дугинаддиагональной матрицы, выход триггера М-й модели дуги К-й строки наддиагональной матрицы (М = 2,Р - 1; К = 1, , Р - 1) подключен кК-му входу (М)-го элемента И первойгруппы, выход которого подключен квыходу М-го элемента НЕ группы и первому входу (М) -го элемента И второйгруппы, информационный выход К-госчетчика первой группы (К Ф Р) подключен к первому информационному входу К-й схемы сравнения группы, о тл и ч а ю щ е е с я тем, что, с целью расширения функциональной возможности устройства за счет определениявершин максимального пути в графе,й него введены группа регистров, элемент И и счетчик, а в каждую модельдуги наддиагональной матрицы введенэлемент НЕ, вход которого подключенк выходу признака переполнения счетчика той же модели дуги наддиагональной матрицы, а выход подключен к второму входу установки в "1" триггератой же модели дуги наддиагональнойКорректор В.Бутяга Редактор Е,Копча Заказ 4803/49 Тираж 670 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 матрицы, вход разрешения пуска устройства подключен к входу разрешения счета счетчиков всех моделей дуг первой строки наддиагональной матрицы, выход триггера первой модели дуги5 первой строки наддиагональной матрицы подключен к входу первого элемента НЕ группы, первому входу элемента И и к входам разрешения счета всех счетчиков моделей дуг второй строки наддиагональной матрицы, выход К-го элемента И первой группы (К Ф Р, Р) подключен к входам разрешения счета всех счетчиков моделей дуг (К+2) -й строки наддиагональной матрицы и к (К+1) -му входу элемента И, выход (Р)-го элемента И подключен к (Р) - му входу элемента И, выход которого подключен к счетному входу счетчика и к входу останова генератора импульсов, выход которого подключен к счетным входам счетчиков всех моделей дуг наддиагональной матрицы и к счетным входам всех счетчыков первой ивторой групп, выход К-го элемента НЕгруппы подключен к входу блокировкисчета К-го счетчика второй группы,информационный выход которого подключен к информационному входу К-го регистра группы, первый разряд информационного выхода счетчика подключенк вторым входам всех элементов И второй группы и к входам признака записивсех регистров группы, выход К-го регистра группы подключен к второму информационному входу К-й схемы сравнения группы, выход признака равенства которой является выходом признака принадлежности (К+1)-й вершинымаксимальному пути в графе устройства, второй разряд информационного выхода счетчика подключен к входам всехсхем сравнения группы, выход К-гоэлемента И второй группы (К Ф Р)подключен к входу разрешения счетаК-го счетчика первой группы.