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

(Г

С

чиков 1, где Р - количество вершин 8 графе, матрицу из РхР триггеров 2, йервую группу из Р элемеитов ИЛИ 3, Группу из Р триггеров 4, элемент И 5, группу из Р элементов НЕ 6, вто- J)yro группу из Р элементов ИЛИ 7 и группу из Р счетчиков 8. После пода- Чи импульсов на тактовый вход устройства все счетчики первой строки матрицы начинают счет импульсов (испол епке ветвей, исходящих из первой ершины графа). Переполнение К-го йчетчика первой строки матрицы (К 1,...,Р) устанавливает К-й триггер той же строки матрицы в единичное Состояние (достигнута К-я вершина рафа). Высокий потенциал с выхода iC-ro элемента ИЛИ 3 поступает на вхо- |Ц)1 разрешения счета всех счетчиков i К-й строки матрицы, которые начинают счет тактовых импульсов (исполнение ветвей, исходящих из К-й вершины графа), и т.д. Единичный потенциал с выхода элемента И 5 (достигнуты все вершины графа) поступает на входы признака чтения всех триггеров 2 Р-го столбца матрицы. На синхронизируемом информационном выходе М-го триггера 2 (,,,.,Р), принадлежащего кратчайшему пути в графе, появляется высокий потенциал, который устанавливает в единицу М-й триггер 4, высокий потенциал с выхода которого поступает на входы признака чтения триггеров 4 М-го столбца матрицы. Устройство работает аналогично до тех пор, пока не будут установлены в единицу все триггеры 4, соответствующие кратчайшему пути в графе. 1 ил.

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

1

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

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

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

Устройство содержит матрицу из Рх счетчиков 1, где Р - количество вер- шн в графе, матрицу из РхР тригге- ров 2, первую группу из Р элементов 1ШИ 3, группу из Р триггеров 4, элемент И 5,группу из Р элементов НЕ 6, Вторую группу из Р элементов ИЛИ 7 и группу из Р счетчиков 8.

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

Перед началом работы в счетчики 1 Заносят коды,.дополняющие веса соот- ветствуюших ветвей графа до полной емкости счетчика (в том случае, если йетвь отсутствует, соответствующий ей счетчик обнуляют), все триггеры 2 и 4 -и счетчики 8 обнуляют, на вход

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

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

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

20

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

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

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

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

30

35

45

ментов НЕ, вторая группа из Р элемен тов ИЛИ и группа из Р счетчиков,причем выход признака переполнения К-го счетчика М-й строки матрицы (К 1,..., Р; М,..,,Р) подключен к информационному входу К-го триггера М-й строки матрицы, несинхронизируеМЬЙ информационный выход которого iO

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

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

счетчиков, где Р - количество вершин в графе, матрицу из РхР триггеров, первую группу из Р элементов ИЛИ, группу из Р триггеров и элемент И, отличающееся тем,что, с целью расширения функциональных возможностей устройства за счет определения вершин кратчайшего пути в гра5

0

5

0

0

5

5

ментов НЕ, вторая группа из Р элементов ИЛИ и группа из Р счетчиков,причем выход признака переполнения К-го счетчика М-й строки матрицы (К 1,..., Р; М,..,,Р) подключен к информационному входу К-го триггера М-й строки матрицы, несинхронизируеМЬЙ информационный выход которого iO. ,

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

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