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

 

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

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

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

ÄÄSUÄÄ 1348850 A 1 (51)4 G 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К ABTOPCKOIVIY СВИДЕТЕЛЬСТВУ (21) 4047345/24-24 (22) 01.04.86 (46) 30.10.87. Бюл. Ф 40 (72) В.М.Балакирев и А.Г.Луценко (53) 681.333(088.8) (56) Авторское свидетельство СССР

Р 444592, кл. С 06 F 15/20, 1978.

Авторское свидетельство СССР

У 798854, кл. G 06 F 15/20, 1978. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ.ПУТЕЙ В ГРАФЕ (57) Изобретение относится к вычислительной технике и может быть использовано для определения максимального пути в графах без контуров и петель.

Целью изобретения является расширение функциональных возможностей устройства за счет определения вершин максиОПИСАНИЕ ИЗОБРЕТЕНИЯ

1348850 мального пути в графе. В состав устройства для исследования путей в графе входят наддиагональная матрица 1 моделей 2 дуг, каждая из которых содержит счетчик 3, элемент HF. 4 и триггер 5, две группы элементов И б и 7, две группы счетчиков 8 и 9, группа регистров 10, группа схем 11 сравнения, группа элементов НЕ 12, элемент

И 13, счетчик 14 и генератор 15 импульсов. Перед пуском устройства в матрицу 1 заносят информацию о топологии графа, устанавливая в 0 триггеры 5 и занося в счетчики 3 коды, дополняющие веса дуг до полной емкости счетчиков 3, и обнуляют регистры

10 и счетчики 8, 9, 14. На первом этапе работы определяют наиболее ранние времена выполнения вершин графа и запоминают их на регистрах 10.

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

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

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

В состав устройства входит наддиагональная матрица 1 моделей 2 дуг, каждая из которых содержит счетчик 3, элемент НЕ 4 и триггер 5, две группы элементов И б и 7, две группы счет15 чиков 8 и 9, группа регистров 10, группа схем 11 сравнения, группа элементов НЕ 12, элемент И 13, счетчик

14 и генератор 15 импульсов..

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

Перед пуско < устройства в матрицу

1 заносят информацию о топологии графа, при этом триггеры 5 устанавливаются в "О", а в счетчики 3 заносят коды, дополняющие веса дуг до полной емкости счетчиков 3. Обнуляют регистры 10 и счетчики 8, 9 и 14.

После подачи сигнала на вход пуска устройства генератор 15 начинает выра- З0 батывать импульсы, которые подсчитыПосле этого устройство вновь приводят в исходное состояние, однако регистры

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, который увеличивает свое со1348850 держимое на единицу и выдает единичный потенциал на первый разряд информационного выхода. Появление сигнала на импульсных входах признаков записи регистров 10 обусловливает запись на ней содержимого счетчиков 8.

Кроме того, единичный потенциал с первого разряда информационного выхода счетчика 14 открывает элементы И 7.

При наличии в графе дуги с нулевым весом в соответствующий счетчик 3 saносят число импульсов, равное его емкости, но триггер 5 устанавливается в состояние "0". Тогда первый же импульс сбрасывает счетчик 3 в "0", что обусловливает появление единичного сигнала на выходе элемента НЕ 4 и переход триггера 5 в состояние "1".

На втором этапе вновь приводят

?О устройство в исходное состояние, но регистры 10 не обнуляются, а в матрицу 1 заносят информацию о топологии инвертированного графа, т.е. данные матрицы исходного графа, но транспортированные относительно неглавной диагонали.

Затем пускают устройство и в счетчиках 8 повторно фиксируются наиболее ранние времена выполнения вершин ин30 вертированного графа, которые в прямом графе соответствуют величинам максимальных путей из вершин графа в его конечную вершину. Однако в регистры 10 содержимое счетчиков 8 уже не ,записывается, так как единичный потенциал с первого разряда информационного счетчика 14 через импульсные входы признаков записи регистров 10 не проходит. Другая особенность работы устройства на втором этапе состоит в том, что при появлении на выходе элемента И 6 единичного потенциала, обусловливающего запрещение счета импульсов соответствующим счетчиком 8, на выходе одноименного элемен- 4 та И 7 появляется единичный потенциал, разрешающий счет импульсов соответствующим счетчиком 9 до останова генератора 15 после того, как на выходе элемента И 13 появится единичный потенциал. В результате по окончании второго этапа работы устройства в счетчиках 9 будут зафиксированы наиболее поздние времена выполнения вершин прямого (исследуемого) графа. 5

Появление единичного потенциала на выходе элемента И 13 приводит к увеличению содержимое счетчика 14, который выдает единичный сигнал на второй разряд информационного выхода.

При поступлении единичного сигнала на входы опроса схемы 11 сравнения сравнивают числа, коды которых установлены на их входах, и при их равенстве, выдают единичные сигналы на выход признака равенства. Номер схемы

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

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

Устройство для исследования путей в графе, содержащее наддиагональную матрицу из (Р-1) х (Р-1) моделей дуг, где P — количество вершин в графе, две группы элементов И, группу элементов НЕ, две группы счетчиков, группу схем сравнения и генератор импульсов, вход пуска которого является входом пуска устройства, причем каждая модель дуги наддиагональной матрицы содержит триггер и счетчик, выход признака переполнения которого подключен к первому входу установки н II в 1 триггера той же модели дуги наддиагональной матрицы, выход триггера M-й модели дуги К-й строки наддиагональной матрицы (М = 2, P — 1; К = 1, ..., P — 1) подключен к

К-му входу (М-1)-го элемента И первой группы, выход которого подключен к выходу М-го элемента НЕ группы и первому входу (M-1) -го элемента И второй группы, информационный выход К-го счетчика первой группы (К Ф Р-1) подключен к первому информационному входу К-й схемы сравнения группы, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональной возможности устройства за счет определения вершин максимального пути в графе, и него введены группа регистров, элемент И и счетчик, а в каждую модель дуги наддиагональной матрицы введен элемент НЕ, вход которога подключен к выходу признака переполнения счетчика той же модели дуги наддиагональной матрицы, а выход подключен к второму входу установки в "1" триггера той же модели дуги наддиагональной

1348850

Составитель А,Мишин

Техред А.Кравчук

Корректор В.Бутяга

Редактор Е,Копча

Заказ 4803/49 Тираж 670 Подписное

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

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

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

5 первой строки наддиагональной матрицы подключен к входу первого элемента HE группы, первому входу элемента И и к входам разрешения счета всех счетчиков моделей дуг второй строки наддиагональной матрицы, выход К-ro элемента И первой группы (К Ф P-2, P-1) подключен к входам разрешения счета всех счетчиков моделей дуг (К+2) -й строки наддиагональной матрицы и к (К+1) -му входу элемента И, выход (P-2)-ro элемента И подключен к (P-1)му входу элемента И, выход которого подключен к счетному входу счетчика и к входу останова генератора импульсов, выход которого подключен к счетным входам счетчиков всех моделей дуг наддиагональной матрицы и к счетным входам всех счетчыков первой и второй групп, выход К-го элемента HF группы подключен к входу блокировки счета К-го счетчика второй группы, информационный выход которого подключен к информационному входу К-горегистра группы, первый разряд информационного выхода счетчика подключен к вторым входам всех элементов И второй группы и к входам признака записи всех регистров группы, выход К-ro регистра группы подключен к второму информационному входу К-й схемы сравнения группы, выход признака равенства которой является выходом признака принадлежности (К+1)-й вершины максимальному пути в графе устройства, второй разряд информационного выхода счетчика подключен к входам всех схем сравнения группы, выход К-ro элемента И второй группы (К Ф Р-1) подключен к входу разрешения счета

К-ro счетчика первой группы.