Устройство для моделирования графов Советский патент 1986 года по МПК G06G7/122 

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

1

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

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

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

Устройство содержит модели узлов , каждая из которых состоит из ключа 2, RS-триггера 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 ил.

fO

15

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

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

jj прохождения всех других импульсов с выходов 12 моделей ветвей, входящих в данный узел. Импульс с прямого выхода триггера 3 поступает на входы 11 моделей ветвей, исходящих из данного узла, и .т.д.

0

35

Кроме того, импульс с выхода триггера 3 каждой модели 1 поступает, во-первых, на первый вход соот- ветствую11его элемента И 18 (работа этих элементов на первом этапе не имеет значения), во -в орых, на соответствующий вход элемента ИЛИ 15. С выхода этого элемента импульс про3

ходит через элемент задержки 16 на счетный вход счетчика 17, который увеличивает свои показания на 1. По истечении времени, не превышающего величины N.V, , (где N - число вершин графа; Vfj - максимальный вес ветви графа), в счетчике 17 .фиксируется число импульсов М : N, причем М N, если никакая п.ара триггеров 3 не перебросилась в единично состояние практически одновременно, т.е. на интервале времени, меньшем разрешающей способности счетчика 17 и М N г в противном случае.

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

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

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

ра 14, благодаря наличшо сигнала раз решения с инверсного выхода триггера 20 при снятии разрешения прекращает счет импульсов, фиксируя вес макси- 5 мяльного кратчайшего пути от начального до j-ro узла графа. Если в графе имеется два или более таких равноудаленных ( в пределах разрешающей способности счетчика 17) узлов, О то импульсы поступят на два или более выходов устройства с выходов двух или более элементов И 18.

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

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

ный вход ключа является информационным входом модели узла, выход ключа подключен к первому S-входу RS- триггера, второй S-вход RS-тригге- ра каждой i-й модели узла (где i 1,п) подключен к одноименному неподвижному контакту переключателя, подвижный контакт которого подключен к выходу генератора импульсов, вход запуска и вход останова кото- рого являются соответственно входом запуска и входом останова устройства, прямой выход RS-триггера каждой L-и модели узла подключен к первому входу i-ro элемента И группы и к i-му входу первого элемента ИЛИ, выход которого через элемент задержки подключен к счетному входу первого счетчика, выход которого подключен ко вторым входам элементов И группы, выход

512803826

каждого i-го элемента И группы под- . подключен к входу установки в Г ключей к i-му входу второго элемей- триггера,инверсный выход которого под- та ИЛИ и,является г-тым выходом ключей к входу разрешения счета импуль- группы информационных выходов уст- -ОН второго счетчика,счетный вход кото- ройства, выход второго элемента ИЛИ з рого подключ(гн к выходу генератора импульсов .

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