Модель ветви графа Советский патент 1977 года по МПК G06F15/173 

(54) МОДЕЛЬ ВЕТВИ ГРАФА

Изобретение относится к области вычиспительной техники, в частности, к электронным моделирующим устройствам. ,

По, авт. св. № 470811 известна модель ветви графа, которая содержит элементы И, задатчики начального и конечного адресов, формирователь временного интервала и триггеры.

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

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

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

Поставленная цель достигается тем, что fi предложеяное устройство введены сдвига вый регистр, инвертор и шестой элемент Rf РХОП Сдвигового регистра соединен с дополнительным влодом модели ветви графа, а его выход через инвертор лоцключен к первому входу шестого элемента И, второй вход которого соединен с выходом второго элемента И, а выход - с дополнительным единичным входом первого триггера.

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

Модель ветви графа содержит формирователь 1 временного интервала, задатПример заполнения регистров

1 2 Обязательный выбор одной из ветвей по окончании формирования i -го узла обеспе«ивается тем, что после каждого импульса сдвига на выходе хотя бы одного из четырех регистров появляется единичный сигнал, Алыгернативный выбор одной из ветвей обуч словлен тем, .что этот единичный сигнал появляется ка выходе только одного регист ра. Поскольку число сдвиговых импульсов случайно, то появление в данный момент единичного сигнала на выходе регистра j-и ветви является случайным событием. Допустим, в момент (Жончания формирования I -го узла единичный сигнал присутствует иа выходе регистра второй модели ветви,, изображенной на чертеже. В момент оконча. ВИЯ формирования i -го узла на выходах всех четырех задатчиков начального адреса npacj TCTByioT единичные сигналы, первые триггеры упомянутых моделей ветвей находятся в нулевом состоянии, поэтому на вы- ходах элементов И 8 всех четырех моделей ветвей присутствует единичный сигнал, который является сигналом об окончании фор-« мирования 1-го узла. Нулевые сигналы с Выходов регистров первой, третьей и четвертой моделей ветврй через инверторы раз-.

чик 2 начального адреса, задатчик 3 кокечlaoro адреса, сдвиговый регистр 4, триггеры 6,6, элементы И 7-12 и инвертор 13,

Работу модели аетви рассмотрим i, начиная с момента, когда сформировав 1-й узел с вероятностным выходом. Допустим, к$ 1-го узла выход$п четьгре ветви с вероятностями реализании Pj Oj,, Т в 0,1, , 1 0,5, емкасть реги г а N 1О, и реализуется алья ррсатив-, ашй выбор одной ю исходящих ветАе& Один КЗ возможных способов занесения информаШа о BeposTTHOcTSX в разряды сдвиговых регистров приведен в табл.

Таблица решают прохождение этого сигнала нА вькоды элементов И 12 и на первые триггеры которые устанавливаются в единичное состояние. Нулевые выходы этих триггеров через элементы И 7 и 11 запрещают фиксацию момент /в окончания соответствующих ветвей. Таким образом, эти ветви исключаются на процесса моделирования Единичный выходной сигнал регистра второй модел ветви с прмсшью инвертора 13 запрещает прохождение единичного сигнала с выхода элемента И 8 на вход элемента И 12, следовательно, триггер 5 этой модели ветви остается в нулевом состоянии. В остальном устройство работает так же, как описано в основном изоб|$етеиии. В резул1Угате мисягократного моделирования можно получит статистйческ ие оценки исследуемых графов. Для реализации обычных детерминированных графов все регистры заполняются единицами. Для реализации запрещения какой-либо вет1ви (узла) регшзтр ветви (регистры всех выходящих ветвей) заполняются нулями, Применение изобретения позволяет моделиропать графы с раз ичными структурными ограничениями, в частности стохастические, апагернативные графы, графы с об хоцом отдельных аапрещевйых узлов и вет вей. Изобретение позволяет также решать эапачи теории графов, связанных с перечислением путей (.задача коммивояжера, задачи о паросочетаниях и цр). Формула изобретения Модель ветви графа по авт. сайд, hfe 47О8И, отличающаяся тем. что, с целью расширения класса задач путем моделирования графов с различными структурными ограничениями, в нее дополнительно введены сдвиговый регистр, инвертор и шестой элемент И; причем вход сдвигового регистра соединен с донолнительгным входом модели ветви графа, а его выход через инвертор подключен к первому) входу шестого элемента И, второй вход которого соединен с выходом второго (элемента И, а выход-с дополнительным единичным входом первого триггера.