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

 

Изобретение относится к области вычислительной техники и может быть использовано при решении на графах задач определения наиболее длинных кратчайших путей, центров и радиусов сетевых структур. Целью изобретения является расширение функциональных возможностей устройства за счет определения одного или нескольких узлов, кратчайшие пути до которых из любого узла графа имеют наибольшие значения . Поставленная цель достигается тем, что в устройство для моделирования графов, содержащее модели ветвей 7 и модели узлов 1, соединенные согласно топологии исследуемого графа , каждая модель ветви состоит из элемента задержки 8, формирователя импульсов 9, разделительного диода 10 и полюсов 11 и 12, введены генератор импульсов 14, первый элемент ИЛИ 15, элемент задержки 16, первьй счетчик 17, группа элементов И 18, второй элемент ИЛИ 19, триггер 20, второй счетчик 21, каждая модель узла содержит ключ 2, триггер 3 и полюса 4, 5, 6. Устройство позi (Л

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

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

РЕСПУБЛИК (19) (!1) А1 (51) 4 G 06 F 15/20

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

И A BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3894273/24-24 (22) 06.05.85 (46) 30.12.86. Бюл. й- 48. (72) В.А. Шингиреев и С.К. Михайловский (53) 681.333 (088.8) (56) Авторское свидетельство СССР

9 406198, кл. G 06 F 15/20, 1971.

Авторское свидетельство СССР Ф 223468, кл. G G 7/122, 1967.. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано при решении на графах задач определения наиболее длинных кратчайших путей, центров и радиусов сетевых структур. Целью изобретения является расширение функциональных возможностей устройства за счет определения одного или нескольких узлов, кратчайшие пути до которых из любого узла графа имеют наибольшие значения. Поставленная цель достигается тем, что в устройство для моделирования графов, содержащее модели ветвей 7 и модели узлов 1, соединенные согласно топологии исследуемого графа, каждая модель ветви состоит иэ элемента задержки 8, формирователя импульсов 9, разделительного диода

10 и полюсов 11 и 12, введены генератор импульсов 14, первый элемент

ИЛИ 15, элемент задержки 16, первый счетчик 17, группа элементов

И 18, второй элемент ИЛИ 19, триггер 20, второй счетчик 21 каждая модель узла содержит ключ 2, триггер

3 и полюса 4, 5, 6. Устройство поз1280382 воляет определять узлы, кратчайшие пути до которых иэ любого назначенного узла имеют максимальную величину, при этом определяется и вес этого наибольшего кратчайшего пути. Решение данной задачи необходимо, например, при оценке времени доставки!

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

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

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

Устройство содержит модели узлов

l, каждая из которых состоит из ключа 2, BS-триггера 3 и полюсов

4-6, модели 7 ветвей, каждая из которых состоит из элемента 8 задержки, формирователя 9 импульсов, разде.лительного диода 10 и полюсов 11 и

12, переключатель 13, генератор 14 импульсов, первый элемент ИЛИ 15, элемент 16 задержки, первый счетчик

17, группу элементов И 18, второй элемент ИЛИ 19, триггер 20 и второй счетчик 21.

Первоначально модели узлов и ветвей соединяют согласно топологии графа, триггеры 3 и счетчик 17 устанавливают н нулевое положение (цепи установки на чертеже .не показаны), при этом все ключи 2 открыты единичными потенциалами с инверсных выходов триггеров 3. Переключатель 13 устанавливают в положение, соответствующее узлу графа, из которого должны определяться наиболее длинные кратчайшие пути. В элементах 8 устанавливаются величины задержек, пропорциональные весу ветвей графа.

Устройство работает в два этапа следующим образом. сообщении из пунктов управления до наиболее удаленных исполнительных пунктов, а также при нахождении центров и радиусов сетевых структур с целью выбора оптимальных мест размещения ремонтно-восстановительных и аварийных бригад и служб. 1 ил.

При поступлении сигнала на пусковой вход генератор 14 выдает импульсы, первый из которых через переключатель 13 поступает на второй S-вход

5 триггера 3 модели 1 .начального узла графа. Триггер 3 переходит в единичное состояние, вследствие чего нулевой потенциал с его инверсного выхода закрывает ключ 2, а импульс с прямого выхода триггера 3 поступает на входы элементов 8 всех моделей ветвсй 7, исходящих из начального узла графа. Последующие импульсы генератора 14 на состояние триггера 3 влияния не оказывают, а работа блоков 18-21 на первом этапе значения не имеет.

Импульс, поступивший на вход элемента 8 модели 7, задерживается элементом 8 на время, пропорциональное весу ветви, и далее через формирователь 9 и разделительный диод 10 поступает на вход ключа 2 модели уз2 .ла. Пройдя через ключ 2 на первый . $-вход .триггера 3, он перебрасывает триггер 3 в единичное состояние, вследствие чего нулевой сигнал с инверсного выхода закрывает ключ 2 для прохождения всех других импульсов с выходов 12 моделей ветвей, входящих в данный узел. Импульс с прямого выхода триггера 3 поступает на входы !1 моделей ветвей, исходящих

35 из данного узла, и,т.д.

Кроме того, импульс с выхода триггера 3 каждой модели 1 поступает, во-первых, на первый вход соответствуют!его элемента И 18 (работа

4 этих элементов на первом этапе не имеет значения), во -в-орых, на соответствующий вход элемента ИЛИ 15.

С выхода этого элемента импульс про1280382 4

50

15 ходит через элемент задержки 1Ь на счетный вход счетчика 17, который увеличивает свои показания на l . По истечении времени, не пре зышающего величины N.V .(где И вЂ” число вершин графа; V — максимальыый вес ветви графа), в счетчике 17 .фиксируется число импульсов М: N, причем М = N, если никакая пара триг— геров 3 не перебросилась;в единичное состояние практически одновременно, т.е. на интервале времени, меньшем разрешающей способности счетчика 17, и М (N —, в противном случае.

Через время, не меньшее величины

N V íà вход останова ген.ератора 14 подают сигнал останова, у стройство приводят в исходное состояние, а именно обнуляют триггеры 3 и 20 и счетчик 21. В счетчик же 17 заносят количество импульсов, дополняющее до его полной емкости 1 -1 (где показания счетчика 17 после первого этапа работы устройства).

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

При подаче сигнала на пусковой вход генератор 14 вновь выдает импульсы на выход и блоки I 13 работают аналогично. При этом импульсы, поступающие с прямых выходов триггеров 3 на первые входы соответствующих элементов И 18 на их выходы не проходят, поскольку элементы И 18 закрыты нулевым потенциалом с выхода счетчика 17. И лишь после отсчета счетчиком 17 (M-1) импульсов потенциал переполнения с выхода счетчика 17 открывает элементы И 18, вследствие чего только импульс с выхода триггера 3, перебросившегося в единичное состояние, последним проходит через соответствующий элемент И 18, во-первых, на соответствующий выход устройства, идентифи- . цируя номер искомого J-го (jeN) узла графа, кратчайший путь до которого из начального узла имеет наибольшее значение. Во-вторых, этот импульс с выхода элемента И 18 проходит через элемент ИЛИ 19 на вход триггера 20 и перебрасывает его в единичное состояние, что обусловливает снятие с управляющего входа .. счетчика 21 разрешения на дальнейший отсчет импульсов. Счетчик 21, ведущий счет импульсов, поступающих на

1 его счетщый вход с выхода генерато20

55 ра 14, благодаря наличию сигнала раз решения с инверсного выхода триггера

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

И, элемент задержки, триггер, генератор импульсов, переключатель, каждая модель узла содержит ключ и

RS-триггер, управляющий вход ключа подключен к инверсному выходу триггера, прямой выход которого является выходом модели узла, информационный вход ключа является информационным входом модели узла, выход ключа подключен к первому Б-входу RSтриггера, второй S — вход RS †триггера каждой i-й модели узла (где

=1,й) подключен к одноименному неподвижному контакту переключателя, подвижный контакт которого подключен к выходу генератора импульсов, вход запуска и вход останова которого являются соответственно входом запуска и входом останова устройства, прямой выход RS-триггера каждой

1.-й модели узла подключен к первому входу i-го элемента И группы и к i-му входу первого элемента ИЛИ, выход которого через элемент задержки подключен к счетному входу первого счетчика, выход которого подключен ко вторым входам элементов И группы, выход

1280382

Составитель Т. Сапунова

Техред Л.Олейник

Редактор Л. Пчелинская

Корректор М. Пожо

Заказ 7051/42

Тираж 671

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

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

Подписное

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

5 рого подключ! як выходу генератора имI пульсов °