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

 

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

СООЗ СОВЕТСКИХ

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

РЕСПУБЛИК

А1 (19) (11) (51) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. (21) 4063076/24-24 (22) 28,04.86 (46) 30.05.88. Бюл. N 20 (72) Г,СеКолесник (53) 681.333 (088.8) ° °

° ° гг е °

° °

° °

° е ° ° ° ° ° å ° ° ° ð

° ее ° ° ° ° ° ° ° ее е

° е °

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (56) Авторское свидетельство СССР

У 842842, кл. G 06 0 7/122, 1979.

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

У 525954, кл. G 06 F 15/20, 1974. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПУТЕЙ В ГРАФЕ (57) Изобретение относится к вычислительной технике и может быть использовано для исследования путей в графе. Целью изобретения является расширение функциональных возможностей устройства за счет определения вершин кратчайшего пути в графе. Устройство содержит матрицу из РхР счет-!, 1 3> en чиков 1, где P " количество вершин

Н графе, матрицу из РхР триггеров 2, Первую группу иэ P элементов ИЛИ 3, i,"ðóïïó из P триггеров 4, элемент . И 5, группу из Р элементов HF, 6, вторую группу из P элементов ИЛИ 7 и группу из Р счетчиков 8. После подачи импульсов на тактовый вход устройСтва все счетчики первой строки матрицы начинают счет импульсов (испол"

Мение ветвей, исходящих из первой фершины графа). Переполнение К-ro счетчика первой строки матрицы (К =

Ф 1,...,P) устанавливает К-й триггер

1 той же строки матрицы в единичное состояние (достигнута К-я нершина

1 рафа), Высокий потенциал с выхода

К"го элемента ИЛИ 3 поступает на входы разрешения счета всех счетчиков

К-й строки матрицы, которые начина3 ют счет тактовых импульсов (исполне" ние ветвей, исходящих из К-й нершины графа), и т.д, Единичный потенциал с выхода элемента И 5 (достигнуты все вершины графа) поступает на входы признака чтения всех триггеров

2 P-го столбца матрицы. На синхронизируемом информационном выходе М-ro триггера 2 (M=1 Р), принадлежа" щего кратчайшему пути н графе, появляется высокий потенциал, который устанавливает в единицу" М-й триггер

4, высокий потенциал с выхода которо"

ro поступает на входы признака чтения триггеров 4 M-го столбца матрицы.

Устройство работает аналогично до тех пор, пока не будут установлены в "единицу" все триггеры 4, соответствующие кратчайшему пути н графе.

1 ил.

Изобретение относится к вычислительной технике и может быть испольЗовано для определения вершин и ве"

Личины кратчайшего пути в графе.

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

Кратчайшего пути в графе.

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

Устройство содержит матрицу из РхР счетчиков 1, где P — количество вершин в графе, матрицу из РхР триггеров 2, первую группу из P элементов

ИЛИ 3, группу иэ P триггеров 4, элемент И 5,группу из P элементов НЕ 6, вторую группу из P элементов ИЛИ 7 и группу из P счетчиков 8.

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

Перед началом работы в счетчики 1

Заносят коды, дополняющие веса соответствующих ветвей графа до полной емкости счетчика (н том случае, если ветвь отсутствует, соответствующий ей счетчик обнуляют), все триггеры

2 и 4 и счетчики 8 обнуляют, на вход

25 пуска устройства подают единичный потенциал.

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

Переполнение К-го счетчика первой строки матрицы (К=1,...,Р) устанавливает К-й триггер; .2 той же строки матрицы в единичное состояние (достигнута К"я вершина графа) при условии, что с выхода элемента НЕ б на вход разрешения записи указанного триггера подается единичный потенциал.

После установки -ro триггера любой строки матрицы в "единицу" единичный потенциал с его несинхронизируемого информационного выхода, проходя через элемент НЕ Ь, запрещает установку в единичное состояние любого из оставшихся триггеров 2 К-го столбца матрицы и счет импульсов К-м счетчиком 8 °

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

9753

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

М-й строки матрицы, несинхронизируемый информационный выход которого:"«,, подключен к М-му входу К"ro элемента

2р ИЛИ первой группы, выход которого подключен к входам разрешения счета всех счетчиков (K+I)-й строки матрицы (К Р), к К-му входу элемента И и входу К-го элемента НЕ группы, выход

25 которого подключен к входу разрешения счета -ro счетчика группы и вхо" дам разрешения, записи всех .триггеров

К-го столбца матрицы, синхронизируе -. мый информационный выход К:го триггеЗО ра М-й строки матрицы подключен к

К-му входу М-го элемента ИЛИ второй группы, выход которого подключен к входу установки в М-го триггера группы, выход которого подключен к вхо" дам признака чтения всех триггеров

М-го столбца матрицы (М Р), выход элемента И подключен к входам призна" ка чтения всех триггеров P-го столбца матрицы, вход пуска устройства

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

3 139

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

М-й триггер 4, единичный потенциал с выхода которого поступает на входы признака чтения триггеров 4 М-го столбца матрицы. Устройство аналогично работает до тех пор, пока не

II !! будут установлены в единицу все триггеры 4, соответствующие кратчайшему пути в графе.

В результате работы устройства определяются величина кратчайшего пути из первой вершины в К-ю (количество импульсов, поступивших на такто" вый вход устройства до момента появления единичного потенциала на выходе К-ro элемента ИЛИ 3, что соответствует коду, записанному в К"м счетчике 8) и вершины, принадлежащие кратчайшему пути (состав установленных в единицу триггеров 4).

В качестве триггера 2 может быть использована совокупность D-триггера и элемента И, причем информационный .выход D-триггера является несинхронизируемым информационным выходом триггера 2 и подключен к первому вхо" ду элемента И, второй вход которого является входом признака чтения триггера 2, причем выход элемента И является синхронизируемым информационным выходом триггера 2.

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

Устройство для исследования путей в графе, содержащее матрицу из РхР

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

Редактор А,Лежнина Техред А.Кравчук Корректор Г.Решетник

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

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

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

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