Модель ветви графа

 

Союз Советских

Социалистических

Республик (11 583439 (61) Дополнительное к авт. свид-ву А 470811 (51) М. Кл.

8 06 F 15/20 (22) Заявлено 30,01.76 (21 2321184/

/18-24 с присоединением заявки №Гаоударственив|й комитет

Совета Министров СССР ио делам изобретений и откро1тнй (23) Приоритет (43) Опубликовано 05. 12,77. Бюллетень №4 (4о) Дата опубликования описания 20.12. 17 (53) УД!(681.Ý25 (088,8) В, В, Васильев, A. Г. Додонов, О, Н. Голованова, E. А, Ралдугин и Я. Я, Фенюк (72) Авторы изобретения

Институт алектродинамики AH Украинской ССР (71) Заявитель (54) МОДЕЛ Ь ВЕТВИ ГРАФА

Изобретение относится к области вычислительной техники, в частности, к алектронным моделирующим устройствам, По авт. св. No 470811 известна модель ветви графа, которая содержит алементы И, задатчики начального и конечного адресов, формирователь временного интервала и триггеры.

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

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

BoGBonser получить необходимые статистические данные для исследования широкого круга практически важных задач.(на пример задач организационного управления, системы массового обслуживания), Другим примером графов с изменяющейся топологией могут служить модели различных задач теории графов-задачи о коммивояжере, о наро сочетаниях и т.п., при решении которых тре буется организовать перечисление путей, независимых по ветвям и по узлам. Известная модель ветви не позволяет учесть дополнительные условия, налагаемые.s процессе ое щения на струКтуру. модели графа, Белью изобретения является расширение класса задач, т,е, обеспечение дополнительной возможности моделирования графов с различными структурными ограничениями.

583439 чик 2 начального адреса, задатчик 3 конеч-, ного адреса, сдвиговый регистр С, триггеры 5,6,элементы И 7-12 и инвертор 13, Работу модели ветви рассмотрим, начи: ная с момента, когда сформироВан 1-й узел с вероятностным выходом. допустим, из 1--го узла выходят четыре ветви с вероятностями реализации,Р

0, 2 ° P> 0,1, Р4 О,S, емкость Реги10 щука Ю 10, и реализуется алнгернатив-, ный выбор одной из исходящих ветвей. Один из возможных способов занесенйя информаааа о вероятностях в разряды сдвиговых регистров приведен в табл.

Ф

Пример заполнения регистров Таблица

1 1

1 1 1 1

Поставленная цель достигается тем, что в предложенное устройство введены сдвйго" вый регистр, инвертор и шестой элемент И, Дход 6двигового регистра соединен с дополнительным входом модели ветвФ графа, . а ere выход через инвертор подключен к первому входу шестого элемента И, второй вход которого соединен с выходом второго элемента И, а выход - с дополнительным единичным входом первого триггера, На чертеже приведена функциональная схема предложенного устройства, Модель ветви графа одержит формирователь 1 временного интервала, задатОбязательный выбор одной из ветвей по б кончании формирования Ф -го узла обеспе-. яивается тем, что после каждого импульса сдвига на выходе хотя бы одного из четы« рех регистров появляется единичный сигнал, Альтернативный выбор одной из ветвей обу словлен тем, что этот единичный сигнал появляется на выходе только одного регист., ра. Поскольку число сдвиговых импульсов случайно, то появление в данный момент единичного сигнале на выходе регистра -Й ветви является случайным событием. Допустим, в момент окончания формирования

i-го узла единичный сигнал присутствует на выходе регистра второй модели ветви,. изображенной на чертеже, В момент оконча иия формирования i -го узла на выходах всех четырех задатчиков начального адреса присутствуют единичные сигналы, первые триггеры упомянутых моделей ветвей находятся в нулевом состоянии, поэтому на вы ходах элементов И 8 всех четырех моделей ветвей присутствует единичный сигнал, который является сигналом об окончании фор» мирования i -го узла. Нулевые сигналы с выходов регистров первой, третьей и четвертой моделей вета и через инверторы раз, решают прохождение этого сигнала ad выходы элементов И 12 и на первые триггеры, которые устанавливаются в единичное состоя«. ние, Нулевые выходы этих триггеров через элементы И 7 и 11 запрещают фиксацию момент в окончания соответствующих ветвей.

Таким обРазом, эти ветви исключаютсЯ as процесса моделирования Единичный выходной сигнал регистра второй модели ветви с помощью инвертора 13 запрещает прохождение единичного сигнала с выхода элемента И 8 на вход элемента И 12, следовательно, триггер 5 этой модели. ветви остается в нулевом состоянии.

В остальном устройство работает так же, как описано в основном изобретении.

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

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

583439

Сосгавитель В, Тарасов

Редактор Л. Утехина ТехредА. Богдан Корректор М. немчик

Заказ 4895/54 Тираж 818 Подписное

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

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

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

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

Модель ветви графа по авт. свид.

l4 470811, о т л и ч а ю ш а я с я тем, что, с целью расширения класса решаемых задач путем моделирования графов с различными структурными ограничениями, в нее дополнительно введены сдвпговый регистр, инвертор и шестой элемент И; причем вход сдвигового регистра соединен с дополнительным входом модели ветви графа, а его выход через инвертор подключен к первому! входу шестого элемента И, второй вход которого соединен с выходом второго элемента И, а выход-с дополнительным единичным входом первого триггера.