МОДЕЛЬ ДУГИ ТРАНСПОРТНОЙ СЕТИ Советский патент 1973 года по МПК G06F15/56 

1

Изобретение относится к области вычислительной техники.

Известны модели дуги транспортной сети, содержащие триггеры, вентили, схемы «НЕ, диоды, линии задержки, блок управления, схему совпадения, счетчик потока через дугу и датчик случайных временных интервалов.

Цель изобретения - упрощение модели транспортной сети со случайными пропускными способностями дуг.

Это достигается тем, что в нее введен счетчик памяти пропускной способности дуги, вход которого через первый вентиль подключен к блоку управления и к потенциальному выходу датчика случайных временных интервалов. При этом вход и выход модели дуги через второй и соответственно третий вентили и линии задержки соединены с единичным входом входного триггера и соответственно нулевым входом выходного триггера и подключены к входу датчика случайных временных интервалов, импульсный выход которого через четвертый и пятый вентили, подсоединенные вторыми входами к блоку управления, и обратно включенные диоды соединены с входом и соответственно выходом модели дуги. Третьи входы четвертого и пятого вентилей подключены к нулевому выходу выходного триггера и единичному выходу входного триггера, а нулевой выход входного и единичный выход выходного триггера - к вторым и третьи: входам второго и третьего вентилей. Вход модели дуги соединен с входом щестого вентиля, второй и третий входы которого подключены к блоку управления и нулевому выходу выходного триггера. Выход шестого вентиля через обратно включенный диод соединен с выходом модели дуги и через седьмой и восьмой вентили, подключенные Другими входами к шинам управления, - с единичным входом выходного триггера и соответственно вычитающим входом счетчика потока через дугу, нулевой выход которого через схему «НЕ подключен к четвертому

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

обратно включенный диод соединен с входом модели дуги и через десятый и одиннадцатый вентили, подключенные другими входами к блоку управления, - с нулевым входом входного триггера и соответственно суммирующим входом счетчика потока через дугу. Выход схемы совпадения, подсоединенной к счетчику потока через дугу и счетчику иамяти пропускной способности дуги, через схему «НЕ связан с четвертым входом второго

вентиля. Пятые входы второго и третьего вен3тилей, нулевой вход входного и единичный вход выходного триггера и вход датчика случайных временных интервалов подключены к блоку управления. На чертеже приведена схема модели дуги5 транспортной сети. Модель дуги содержит вентили 1-//, схемы «НЕ 12 и 13, триггеры 14 и 15, диоды 16-19, линии 20 и 21 задержки, схему 22 совпадения, счетчики потока через дугу 23Ю и памяти пропускной способности дуги 24, датчик 25 случайных временных интервалов, индикатор 26, блок управления (на чертеже не показан). Модель дуги транспортной сети работает 5 следующим образом. Импульс, возникающий в узле сети, например на входе моделируемой дуги, через вентиль 1, линию 20 задержки устанавливает триггер 14 в единичное состояние, тем самым 0 перекрывая вентили / и 2. Аналогично происходит в том случае, когда дуги кончаются в данной верщине, т. е. импульс через вентиль 2, линию 21 задержки устапавливает триггер 15 в нулевое состояние, тем самым 5 перекрывая вентили 2 и 1. Таким образом, во-первых, фиксируются просмотренные дуги (в том числе и вершины), т. е. блокируются все подходы к ним, а во-вторых, направление просмотра, так как триггер 14 (единичное состояние) соответствует положительному направлению просмотра, триггер 15 - отрицательному. Импульс, возникающий на входе или выходе дуги, поступает на вход датчика 25 слу- 5 чайных временных интервалов, осуществляющего задержку импульса на время, подчиненное заданной функции распределения. Назначение датчика состоит в том, чтобы сделать маловероятным появление кратных путей или40 одновременных просмотров верщин, принадлежащим одним дугам, исключить такую возможность путем повторного поиска путей среди уже выделенных дуг. Для статистического анализа сетей со слу- 5 чайными пропускными способностями необходимо в счетчик 24 памяти пропускной способности дуги записывать новую пропускную способность дуги для каждого щага набора статистики. Это достигается измерением дли-50 тельности потенциала на потенциальном выходе датчика 25 случайных временных интервалов, импульсами стандартной частоты из блока управления через вентиль 11. Задание новых кодов определяется подачей разрещаю-55 щего потенциала по щине 27, запрещающего - по щинам 28 и 29 для блокировки остальных элементов сети и подачей единичного импульса по щине 30. Блокировка прохождения импульса в том60 или ином направлении осуществляется еледующим образом. Нулевое состояние счетчика 23 потока через дугу, через схему 13 является управляющим потенциалом для вентиля 2 и разрещает просмотр в обратном65 4 направлении (присвоение знака «-) в случае f(b)0. Выход схемы 22 совпадения счетчика 24 памяти пропускной способности дуги и счетчика 23 потока через дугу (через схему «НЕ 12) является управляющим входом вентиля / и запрещает просмотр дуг (присвоение знака «+) в случае f (i/) c(L). К схеме 22 совпадения присоединен индикатор 26, фиксирующий все множество дуг, принадлежащих минимальным разрядам сети, Процедура нерераспределения и изменения потока через сеть осуществляется следующим образом. В результате описанных выще действий в сети (если поток еще можно увеличить) выделяется единственная цепь дуг, соединяющих источник со стоком. По щине 29 подается запрещающий потенциал, а по щинам 31, 32 - разрещающий, тем самым давая возможность обратного просмотра дуг, начиная со стока. Импульс, возникающий, например, на выходе дуги, если дуга имеет пометку «+,- а триггер 14 находится в единичном состоянии, проходит через диод 16 на вход сети и через вентиль 9 на вход сложения счетчика 23 потока через дугу. Аналогично при обратном просмотре дуги (триггер 15 в нулевом состоянии) импульс с входа Дуги через вентиль 7 и диод 19 поступает на выход дуги, а через вентиль 10 -на вход вычитания счетчика потока через дугу, Вентили 9 н 10 блокируют входы счетчика потока через дугу при выполнении процедуры выделения единственной цепи дуг, соединяюЩих источник со стоком. Выходы вентилей 8 к 9 через вентили 5 и 5 с управлением цо шине 33 соединены соответственно с нулевым и единичными входами триггеров 14 и 15, т. е. первоначально импульс обратного просмотра фиксирует выделенные дуги (вновь открывает их) для повторного, а если необходимо, многократного поиска единственной Цепи. Исходное состояние устанавливается по щине 34. Предмет изобретения Модель дуги транспортной сети, содержащая триггеры, вентили, схемы «НЕ, диоды, линии задержки, блок управления, схему совпадения, счетчик потока через дугу и датчик случайных временных интервалов, отличающаяся тем, что, с целью упр ощения модели транспортной сети со случайными пропускными способностями дуг, она содержит счетчик памяти пропускной способности дуги, вход которого через первый вентиль подключен к блоку управления и к потенциальному выходу датчика случайных временных интервалов, причем вход и выход модели дуги через второй и соответственно третий вентили и линии задержки соединены с единичным входом входного триггера и соответственно нулевым входом выходного триггера и подключены к входу датчика случайных временных интервалов, импульсный выход которого через четвертый и пятый вентили, подключенные вторыми входами к блоку управления, и обратно включенные диоды соединен с входом и соответственно выходом модели дуги, третьи входы четвертого и пятого вентилей подключены к нулевому выходу выходного триггера и единичному выходу входного триггера, нулевой выход входного и единичный выходного триггера соединены с вторыми и третьими входами второго и третьего вентилей, вход модели дуги соединен с входом шестого вентиля, второй и третий входы которого подключены к блоку управления и нулевому выходу выходного триггера, выход шестого вентиля через обратно включенный диод соединен с выходом модели дуги и через седьмой и восьмой вептили, подключенные другими входами к шипам управления, соединен с единичным входом выходного триггера и соответственно вычитаюш.им входом счетчика потока через

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