Устройство для определения минимальных сечений

СОЮЗ СОВЕТСКИХ ЦИАЛИСТИЧЕСК СПУБЛИН 2(19 1 4 С 06 1 15/2 5 САНИЕ ИЗОБРЕТ ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССС ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ ВТОРСИОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССР В 888134, кл. С 06 Р 15/20, 1980.Авторское свидетельство СССР У 635490, кл. С 06 Г 15/20, 1976 . (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИМАЛЬНЫХ СЕЧЕНИЙ(57) Изобретение относится к вычислительной технике, в особенности к решению на графах задач оценки пропускной способности сетей связи, а также надежности систем связи и вычислительных структур. Цель изобретения состоит в расширении функци-. ональных возможностей путем нахождения двух и более минимальных сечений. Для достижения цели схема устройства для определения минимальных сечений, кроме блока перебора сочетаний, первой группы триггеров, первой и второй групп ключей, счетчика и сумматора с соответствующимисвязями содержит вторую группу. триггеров, третью группу ключей, наборное поле, группу блоков памяти, первый и второй ключи, блок памяти,элемент ИЛИ, формирователь импульсов, блок сравнения и два регистра,все блоки соединены между собой всоответствии с решаемой задачей. Работает устройство таким образом,что после перебора всех сочетанийединичное состояние тех или иныхтриггеров второй группы идентифицирует ребра первого минимального сечения, обнаруженного в ходе работы,в блоке памяти записываются номерасочетаний, образующих сечения такого же минимального веса (если таковые в графе есть). Вес минимальногосечения записывается во втором регистре. В последующем перевод в единичное состояние соответствующихтриггеров второй группы идентифицирует второе (и последующие) минимальное сечение. 1 ил, 1249527 2Изобретение относится к вычислительной технике, в особенности к решению на графах задач оценки пропускной способности сетей связи, а также надежности систем связи и вычислительных структур.Цель изобретения - расширение Функциональных возможностей путем нахождения двух и более минимальных сечений.На чертеже схематически изображено предлагаемое устройство.Оно содержит,блок 1 перебора сочетаний, первую группу триггеров 2, вторую группу триггеров 3, третью группу ключей 4, первую группу ключей 5, вторую группу ключей 6, группу блоков 7 памяти, наборное поле 8, первый ключ 9, замыкающий контакт 10, счетчик 11 второй ключ 12, блок 13 памяти, блок 14 сравнения, второй регистр 15, первый регистр 16, сумматор 17, элемент ИЛИ 18 и формирователь 19 импульсов.Устройство работает следующим образом.Первоначально устанавливают исходное нулевое состояние триггеров 2 и 3, в блоки 7 записывают веса К ребер графа, блоки 11, 13, 16, 17 обнуляют, во второй регистр 15 записывают единицы во все разряды. В исходном состоянии ключи 5 и 9 открыты, остальные ключи закрыты, в наборном поле 8 реализована топология графа путем соединения соответствующих информационных входов и выходов ключей 5, при этом начальная вершина графа соединена с информационным входом ключа 5, а конечная вершина - с выходом ключа 5. При поступлении пускового сигнала на вход запуска устройства блок 1 последовательно, одно за другим, выдает на свои К,выходов сочетания из К ребер графа по одному, двум и т,д. в виде единичных сигналов на соответствующие выходы, а также прямоугольный импульс на свой К + 1-й выход при выдаче каждого сочетания. Счетчик 11 выдает счет, при поступлении сигналов на единичные входы соответствующие триггеры 2 выдают единичные сигналы на управляющие входы ключей 5, которые отключают информационные входы от выходов и тем самым разрывают связи между некоторыми вершинами. Импульс, поступающий с (К+1)-го1 О пающего с К +1-го выхода блока 1 на 15 20 25 открыты единичными. сигналами триггеров 2, на входы соответствующих бло 30 35 40 45 50 55 выхода блока 1 на информационный вход ключа 5 в случае связности начальной и конечной вершин с выхода ключа 5 проходит на управляющийвход ключа 9, отключая от выхода егоинформационный вход, поэтому поступающий на информационный вход ключа9 импульс на выход ключа 9 не проходит, Задним фронтом импульса, постунулевые входы триггеров 2, они пере-.брасываются в исходное состояние,Устройство работает аналогичнодо момента, пока очередное сочетание не обусловит нарушение связности начальной и конечной вершин графа, вследствие чего поступающий на информационный вход ключа 5, импульс на выход ключа 5 к не проходит итем самым не разъединяет информационный вход и выход первого ключа 9. Тогда поступающий на информационныйвход ключа 9 прямоугольный импульспроходит через те ключи 6, которые ков 10, которые выдают веса реберданного сечения графа на входы сумматора 17. Суммарный вес сечения поступает на вход регистра 16, который его запоминает и выдает на выход в параллельном коде.При поступлении импульса на управляющий вход блок 14 сравнивает веса, поступающие на его первый и второй информационные входы, и в случае равенства весов вьщает на выход "Равно" сигнал, поступающий на управляющий вход ключа 12. Вследствие этого номер текущего сочетания с выхода счетчика 11 поступает на информационный вход блока 1.3, который запоминает каждый поступающий номер,Если вес, поступающий с выхода регистра 16 на первый информационный вход блока,14, меньше веса, поступающего на его второй информационный вход, блок 14 вьщает сигнал на выход "Меньше", который через элемент ИЛИ 18 проходит на вход формирователя 19 импульсов. Тот вьщает на выход прямоугольный импульс, который поступает,во-первых, на вход очищения блока 13 и стирает всю хранящуюся информацию, во-вторых, на вход записи регистра 15, который запоминает вес, поступающий на его информационный вход с выхода регистра 16. Кро1249527 4логично находят остальные минимальные сечения. 5 1015 25 30 35 Устройство приводят в исходное состояние, замыкают контакт 10, в счетчик 11 заносят количество импульсов, дополняющее до полной емкости счетчика один из номеров Н 40 сечений, записанных в блоке 13. По сигналу запуска блок 1 производит последовательную выдачу сочетаний, и после выдачи Н-го сочетания счетчик 11 выдает импульс переполнения через контакт 1 О и элемент ИЛИ 18 на вход формирователя 19 импульсов. Тот выдает прямоугольный импульс, передний фронт которого обнуляет триггеры 3, пройдя через ключи 4, которые открыты единичными сигналами с выходов тех триггеров 2, которые при выдаче Н-го сечения окаэалрсь в единичном состоянии, прямоугольный импульс своим задним фронтом переводит 55 в единичное состояние соответствующие триггеры 3, которые идентифицируют второе минимальное сечение. Ана 3ме того, прямоугольный импульс с выхода формирователя 19 импульсов поступает на нулевые входы триггеров 3, переводя их в нулевые состояния, и на информационные входы ключей 4. Длительность прямоугольного импульса, выдаваемого формирователем 19 импульсов, устанавливается меньшей длительности прямоугольного импульса, поступающего с К +1-го выхода блока 1. Поэтому с информационных входов тех ключей 4, которые открыты единичными сигналами, поступающими с выходов соответствующих триггеров 2, прямоугольный импульс проходит на единичные входы одноименных триггеров 3, своим задним фронтом перебрасывает их в единичное состояние и тем самым идентифицирует номера ребер текущего сече.ния графа.После перебора всех сочетаний единичное состояние тех или иных триггеров 3 идентифицирует ребра первого минимального сечения, обнаруженного в ходе работы устройства, в блоке 13 записаны номера сочетаний, образующих сечения такого же минимального веса (если, конечно, таковые в графе есть). Вес минимального сечения записан в регистре 15,При наличии других минимальных сечений идентификацию образующих их ребер производят следующим образом. Формула изобретения Устройство для определения минимальных сечений, содержащее блок перебора сочетаний, первую группу триггеров, первую и вторую группы ключей, счетчик и сумматор, причем вход блока перебора сочетаний является входом устройства, К выходов ( К - числоребер графа) блока перебора сочетаний соединены с единичными входамисоответствующих триггеров первойгруппы, управляющие входы одноименных ключей первой и второй группсоединены и подключены к выходам одноименных триггеров первой группы,о т л и ч а ю щ е е с я тем, что,с целью расширения функциональных возможностей путем нахождения двухи более минимальных сечений, в.неговведены вторая группа триггеров,третья группа ключей, наборное поле,группа блоков памяти, первый и второй ключи, блок памяти, элемент ИЛИ,формирователь импульсов, блок сравнения, замыкающий контакт и два регистра, причем нулевые входы триггеров первой группы соединены с информационными входами счетчика,первого ключа первой группы и первогоключа и подключены к К +1-у выходублока перебора сочетаний, информационные входы и выходы ключей первой группы соединены в наборном поле согласно топологии графа, выход К-го ключа первой группы подключен куправляющему входу первого ключа,информационные входы ключей второйгруппы соединены с управляющим входом блока сравнения и подключены квьгходу первого ключа, выходы ключейвторой группы соединены с входамисчитывания одноименных блоков памятигруппы, выходы которых подключены ксоответствующим входам сумматора,выход которого соединен с входом первого регистра, выход которого под-ключен к первому информационному входу блока сравнения и информационномувходу второго регистра, вход записи которого соединен с входом стиранияблока памяти, информационными входами,ключей третьей группы, нулевыми входами триггеров второй группы и подключены к выходу формирователя импульсов, вход которого соединен с1249527 Составитель А.Шеренковедактор С.Патрушева Техред О.Гортвай КоррекУ Луговаа 6/50 Тираж б 71ВНИИПИ Государственнопо делам изобретений 113035, Москва, Ж, Р Заказ 432 Подписнокомитета СССРоткрытий д. шская на Производственно-полиграфическое предприятие, г. Ужгород, ул ная выходом элемента ИЛИ, первый вход11 11 которого подключен к выходу Меньше блока сравнения, второй информационный вход которого соединен с выхон 1 дом второго регистра, выход Равно блока сравнения подключен к управляющему входу второго ключа, выход и информационный вход которого соединены соответственно с информационным входом блока памяти и выходомсчетчика, который через замыкающийконтакт соединен с вторым входомэлемента ИЛИ, единичные входы триггеров второй группы подключены квыходам одноименных ключей третьейгруппы, управляющие входы которыхсоединены с выходами одноименных 1 О триггеров первой группы,