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

О П И С А Н И Е ( ввз 4 эвИЗОБРЕТЕН Ия Союз СоветскихСоциалистическихРеспублик 61) Дополнитель 22) Заявлено ЭО 70811 кавт, с 1.7 Э 21184//18-24 М. Кл.806 Р 15 исоединением заявкиГесударственивй нцмнт Соеета Министров ССС по делам изобретенийи открытий) Дата опубликования описания 20,1 Е. 1 В, В, Васильев, А, Г. Додонов, О, Н. Голованова, Е. А, Ралдугин и Я. Я, Фенюк 72) Авторы изобретен ктродинамики АН Украинской С ститу Заявитель Ь ВЕТВИ ГРАФА(54 М вей, верш напр личается от стоанной олиной вет Изобретение относится к области вычислительной техники, в частности, к алектронным моделирующим устройствам,По авт. св. Ме 470811 известна модельветви графа, которая содержит алементы И,задатчики начального и конечного адресов,формирователь временного интервала и триггеры.Недостатком такой модели является непригодность ее для моделирования ориентированных графов, в которых вводятся дополнительные ограничения на реализацию вечисходяших из некоторых (или всех)ин графа (структурные ограничения),имер с 1 охастических и альтернативныхграфов, Стохастический граф характеризуется случайной длиной ветвей и вероятностной топологией (т.е, условия начала техили иных ветвей задаются с некоторой вероятностью), Последнее означает, что некоторые вершины графа имеют вероятностные выходы.Алнтернативный граф отхастического детермиииров Фвей и альтернативным характером реализации выходяших ветвей (т.е, реализацияодной ветви, выходящей из вершины, запрешает реализацию остальных ветвей, выходяших из той же вершины). МоделированиеСтохастических и альтернативных графовпозволяет получить необходимые статистические данные для исследования широкого круга практически важных задач (например задач организационного управления,системы массового обслуживания), Другимпримером графов с изменяющейся топологиеймогут служить модели различных задач теории графов-задачи о коммивояжере, о наросочетаниях и т.ппри решении которых требуется организовать перечисление путей, независимых по ветвям и по узлам. Известнаямодель ветви не позволяет учесть дополнительные условия, налагаемые,в процессе дешения на струКтуру. модели графа,Белью изобретения является расширениекласса задач, т,е, обеспечение дополнительной возможности моделирования графов сразличными структурными ограничениями.Поставленная цель достигается тем, чтов предложенное устройство введены сдвйго"вый регистр, инвертор и шестой элемент И,Дход 6 двигового регистра соединен с дополнительным входом модели ветвй графа,а его выход через инвертор подключен кпервому входу шестого элемента И, второйвход которого соединен с выходом второгоэлемента И, а выход - с дополнительнымединичным входом первого триггера,На чертеже приведена функциональнаясхема предложенного устройства,Модель ветви графа .одержит формирователь 1 временного интервала, задат 683439чик 2 начального адреса, задатчик 3 конеч-,ного адреса, сдвиговый регистр 4, триггеры Б,б,элементы И 7-12 и инвертор 13,Работу модели ветви рассмотрим, начи 5 ная с момента, когда сформирован 1-йузел с вероягностным выходом. йопустим,из-го узла выходят четыре ветви свероятностями реализации,Р =, гО,2, Рз 0,1 Р 4 0,8, емкость реги 0 ФФра Ю " 10, и реализуется алцгернитивный выбор одной из исходящих ветвей. Одиниз возможных способов занесенйя информации о вероятностях в разряды сдвиговыхрегистров приведен в табл.ФПример заполнения регистров Таблица,кончаяяиваетссдвига же,Обязательный выбор одной из ветвей по решаюг прохождение этого сигнала н 6 выхоии формирования-го узла обеспе-.ф ды элементов И 12 и на первые триггеры,я тем, что после каждого импульса которые устанавливаются в единичное состояна выходе хотя бы одного из четыние, Нулевые выходы этих триггеров через рех регистров появляется единичный сигнал, элементы И 7 и 11 запрещают фиксацию моАлыгернативный выбор одной из ветвей обу мент в окончания соответствующих ветвей. словлен тем, что этот единичный сигнал ф Таким образом, эти ветви исключаются из появляегся на выходе только одного регист процесса моделирования Единичный выходной ра. Поскольку число сдвиговых импульсовсигнал регистра второй модели ветви с по- случайно, то появление в данный момент мощью инвертора 13 запрещает прохождение единичного сигнала на выходе регистра-й единичного сигнала с выхода элемента И 8 ветви является случайным событием, До на вход элемента И 12, следовательно, тригпустим, в момент окончания формирования гер 5 этой модели. ветви остается в нуле-го узла единичный сигнал присутствует вом состояниина выходе регистра второй модели ветви,. В остальном устройство работает так изображенной на чертеже. В момент оконча как описано в основном изобретении. иия формирования-го узла на выходах 0 В результате многократного моделировавсех четырех эадатчиков начального адреса ния можно получит статистические оценки присутствуют единичные сигналы, первые исследуемых графов. Для реализации обычтриггеры упомянутых моделей ветвей нахо- ных детерминированных графов все регистры дятся в нулевом состоянии, поэтому на вы. заполняются единицами. ходах элементов И 8 всех четырех моделей 55 Для реализации запрещения какой нибо ветвей присутствует единичный сигнал, ко ветви (узла) .регистр ветви (регистры всеХ торый является сигналом об окончании фор выходящих ветвей) заполняются нулями, мирования 1-го узла. Нулевые сигналы с Применение изобретения позволяет мовыходов регистров первой, третьей и чет- делировать графы с раз ичными структурвертой моделей ветаЯ через инверторы раэ ными ограничениями, в частности стохасти60Заказ 4895/54 Тираж 818 Подписное БНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб д. 4/5Филиал ППП "Патент, г. Ужгород, ул. Проектная, 4 ческие,. алиернативные графы, графы с обходом отдельных запрещенных узлов и ветвей, Изобретение позволяет также решатьзадачи теории графов, связанных с перечислением путей задача коммивояжера, задачио паросочетаниях и др),.Чформула изобретении1 ОМодель ветви графа по авт. свид.Мю 470811, о т л и ч а ю ш а я с я тем,что, с целью расширения класса решаемыхзадач путем моделирования графов с различными структурными ограничениями, в неедополнительно введены сдвпговый регистр,инвертор и шестой элемент И; причем входсдвигового регистра соединен с дополнительным входом модели ветви графа, а его выход через инвертор подключен к первомувходу шестого элемента И, второй вход ко"торого соединен с выходом второго элемента И, а выход-с дополнительным единичнымвходом первого триггера.