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

 

Изобретение относится к вычислительной технике, в особенности к решению на графах задач оценки пропускной способности сетей связи, а также надежности систем связи и вычислительных структур. Цель изобретения состоит в расширении функциональных возможностей путем нахождения двух и более минимальных сечений . Для достижения цели схема устройства для определения минимальных сечений, кроме блока перебора сочетаний, первой группы триггеров, .первой и второй групп ключей, счетчика и сумматора с соответствующими связями содержит вторую группу, триггеров , третью группу ключей, наборное поле, группу блоков памяти, первый и второй ключи, блок памяти, элемент ИЛИ, формирователь импуль- .сов, блок сравнения и два регистра, все блоки сое.динены между собой в соответствии с решаемой задачей. Работает устройство таким образом, что после перебори всех сочетаний единичное состояние тех или иных триггеров второй группы идентифицирует ребра первого минимального сечения , обнаруженного в ходе работы, в блоке памяти записываются номера сочетаний, образующих сечения такого же минимального веса (если таковые в графе есть). Вес минимального сечения записьшается во втором регистре . В последующем перевод в единичное состояние соответствующих триггеров второй группы идентифицирует второе (и последующие) минимальное сечение. 1 ил. i (Л 4 СО СЛ N9

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (g1) 4 G 06 F 15/20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ

lt 4

17"

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3794489/24-24 (22) 13.06 .84 .(46) 07.08.86. Бюл. У 29 (72) Г.С.Колесник (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Ф 888134, кл. G 06 Р 15/20, 1980.

Авторское свидетельство СССР

9 635490, кл. G 06 F 15/20, 1976. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

МИНИМАЛЬНЫХ СЕЧЕНИЙ (57) Изобретение относится к вычислительной технике, в особенности к решению на графах задач оценки пропускной способности сетей связи, а также надежности систем связи и вычислительных структур. Цель изобретения состоит в расширении функци-. ональных возможностей путем нахождения двух и более минимальных сечений. Для достижения цели схема устройства для определения минимальных сечений, кроме блока перебора сочетаний, первой группы триггеров, первой и второй групп ключей, счет,SU„„l248527 А1 чика и сумматора с соответствующими связями содержит вторую группу. триггеров, третью группу ключей, наборное поле, группу блоков памяти, первый и второй ключи, блок памяти, элемент ИЛИ, формирователь импульсов, блок сравнения и два регистра, все блоки соединены между собой в соответствии с решаемой задачей. Работает устройство таким образом, что после перебора всех сочетаний единичное состояние тех или иных триггеров второй группы идентифицирует ребра первого минимального сечения, обнаруженного в ходе работы, с в блоке памяти записываются номера 9 сочетаний, образующих сечения такого же минимального веса (если таковые в графе есть). Вес минимального сечения записывается во втором регистре. В последующем перевод в еди- Я ничное состояние соответствующих liaasL триггеров второй группы идентифици- с ) рует второе (и последующие) минимальное сечение. 1 ил. CO

1249527 2

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

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

На чертеже схематически изображено предлагаемое устройство.

Оно содержит, блок 1 перебора сочетаний, первую группу триггеров 2, вторую группу триггеров 3, третью группу ключей 4, первую группу ключей 5, вторую группу ключей 6, группу блоков 7 памяти, наборное поле 8, первый ключ 9, замыкающий контакт

1О, счетчик 11 второй ключ 12, блок

13 памяти, блок 14 сравнения, второй регистр 15, первый регистр 16, сумматор 17, элемент ИЛИ 18 и формирователь 19 импульсов.

Устройство работает следующим образом.

Первоначально устанавливают исходное нулевое состояние триггеров 2 и

3, в блоки 7 записывают веса К ребер графа, блоки 11, 13, 16, 17 обнуляют, во второй регистр 15 записывают единицы во все разряды. В исходном состоянии ключи 5 и 9 открыты, остальные ключи закрыты, в наборном поле 8 реализована топология графа путем соединения соответствующих информационных входов и выходов ключей 5, при этом начальная вершина графа соединена с информационным входом ключа

5„, а конечная вершина — с выходом ключа 5„..

l . При поступлении пускового сигнала на вход запуска устройства блок 1 последовательно, одно за другим, выдает на свои К,выходов сочетания из

К ребер графа по одному, двум и т.д. в виде единичных сигналов на соответствующие выходы, а также прямоугольный импульс на свой К + 1-й выход при выдаче каждого сочетания. Счетчик 11 выдает счет, при поступлении сигналов на единичные входы соответствующие триггеры 2 выдают единичные сигналы на управляющие входы ключей

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

55 ние не обусловит нарушение связности начальной и конечной вершин графа, вследствие чего поступающий на информационный вход ключа 5, импульс на выход ключа 5 не проходит и тем самым не разъединяет информационный вход и выход первого ключа 9.

Тогда поступающий на информационный вход ключа 9 прямоугольный импульс проходит через те ключи 6, которые открыты единичными сигналами триггеров 2, на входы соответствующих блоков 10, которые выдают веса ребер данного сечения графа на входы сумматора 17. Суммарный вес сечения поступает на вход регистра 16, который его запоминает и выдает на выход в параллельном коде.

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

" Равно" сигнал, поступающий на управляющий вход ключа 12. Вследствие этого номер текущего сочетания с выхода счетчика 11 поступает на информационный вход блока 1.3, который запоминает каждый поступающий номер.

Если вес, поступающий с выхода регистра 16 на первый информационный вход блока .14, меньше веса, поступающего на его второй информационный вход, блок 14 вьщает сигнал на выход

"Меньше", который через элемент ИЛИ

18 проходит на вход формирователя

19 импульсов. Тот вьщает на выход прямоугольный импульс, который поступает,во-первых, на вход очищения блока 13 и стирает всю хранящуюся информацию, во-вторых, на вход записи регистра 15, который запоминает вес, поступающий на его информационный вход с выхода регистра 16. Кровыхода блока 1 на информационный вход ключа 5,, в случае связности начальной и конечной вершин с выхода ключа 5 проходит на управляющий вход ключа 9, отключая от выхода его информационный вход, поэтому поступающий на информационный вход ключа

9 импульс на выход ключа 9 не проходит. Задним фронтом импульса, посту10 пающего с К +1-го выхода блока 1 на нулевые входы триггеров 2, они пере-брасываются в исходное состояние.

Устройство работает аналогично до момента, пока очередное сочета1249527 4 логично находят остальные минимальные сечения.

15

35

Устройство приводят в исходное состояние, замыкают контакт 10, в счетчик 11 заносят количество импульсов, дополняющее до полной емкости счетчика один из номеров Н 40 сечений, записанных в блоке 13. По сигналу запуска блок 1 производит последовательную выдачу сочетаний, и после выдачи Н-го сочетания счетчик 11 выдает импульс переполнения через контакт 10 и элемент ИЛИ 18 на вход формирователя 19 импульсов. Тот выдает прямоугольный импульс, передний фронт которого обнуляет триггеры 3, пройдя через ключи 4, которые открыты единичными сигналами с выходов тех триггеров 2, которые при выдаче Н-ro сечения окаэалрсь в единичном состоянии, прямоугольный импульс своим задним фронтом переводит 55 в единичное состояние соответствующие триггеры 3, которые идентифицируют второе минимальное сечение. Ана3 ме того, прямоугольный импульс с выхода формирователя 19 импульсов поступает на нулевые входы триггеров 3, переводя их в нулевые состояния, и на информационные входы ключей 4. Длительность прямоугольного импульса, выдаваемого формирователем

19 импульсов, устанавливается меньшей длительности прямоугольного импульса, поступающего с К +1-го выхода блока 1. Поэтому с информационных входов тех ключей 4, которые открыты единичными сигналами, поступающими с выходов соответствующих триггеров 2, прямоугольный импульс проходит на единичные входы одноименных триггеров 3, своим задним фронтом перебрасывает их в единичное состояние и тем самым идентифицирует номера ребер текущего сече.ния графа.

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

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

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

Устройство для определения минимальных сечений, содержащее блок перебора сочетаний, первую группу триггеров, первую и вторую группы ключей, счетчик и сумматор, причем вход блока перебора сочетаний является входом устройства, К выходов (К вЂ” число ребер графа) блока перебора сочета ний соединены с единичными входами соответствующих триггеров первой группы, управляющие входы одноименных ключей первой и второй групп соединены и подключены к выходам одноименных триггеров первой группы, о т л и ч а ю щ е е с я тем, что, I с целью расширения функциональных возможностей путем нахождения двух и более минимальных сечений, в.него введены вторая группа триггеров, третья группа ключей, наборное поле, группа блоков памяти, первый и второй ключи, блок памяти, элемент ИЛИ, формирователь импульсов, блок сравнения, замыкающий контакт и два регистра, причем нулевые входы триггеров первой группы соединены с информационными входами счетчика,первого ключа первой группы и первого ключа и подключены к К +1-у выходу блока перебора сочетаний, информационные входы и выходы ключей первой группы соединены в наборном поле согласно топологии графа, выход

К-ro ключа первой группы подключен к управляющему входу первого ключа, информационные входы ключей второй группы соединены с управляющим входом блока сравнения и подключены к вьгходу первого ключа, выходы ключей второй группы соединены с входами считывания одноименных блоков памяти группы, выходы которых подключены к соответствующим входам сумматора, выход которого соединен с входом первого регистра, выход которого под- ключен к первому информационному входу блока сравнения и информационному входу второго регистра, вход записи которого соединен с входом стирания блока памяти, информационными входами. ключей третьей группы, нулевыми входами триггеров второй группы и подключены к выходу формирователя импульсов, вход которого соединен с

1249527

Составитель A.Øåðåíêoâ

Редактор С.Патрушева Техред О.Гортвай Корректор О.Луговаа

Заказ 4326/50 Тираж б71 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 выходом элемента ИЛИ, первый вход .

II 11 которого подключен к выходу Меньше блока сравнения, второй информационный вход которого соединен с выхоII Il дом второго регистра, выход Равно блока сравнения подключен к управляющему входу второго ключа, выход и информационный вход которого соединены соответственно с информационным входом блока памяти и выходом счетчика, который через замыкающий контакт соединен с вторым входом элемента ИЛИ, единичные входы триггеров второй группы подключены к выходам одноименных ключей третьей группы, управляющие входы которых соединены с выходами одноименных

1Î триггеров первой группы .