Устройство для определения минимальных сечений Советский патент 1986 года по МПК G06F15/173 

1

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

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

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

Оно содержит, блок 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) ..

V

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

249327

выхода блока вход ключа 5, и

10

15

20

25

30

35

40

45

50

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

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

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

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

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

19импульсов. Тот вьщает на выход прямоугольный импульс, который посту пае т, во-первых, на вход очищения блока 13 и стирает всю хранящуюся

55 информацию, во-вторых, на вход записи регистра 15, который запоминает вес, поступающий на его информационный вход с выхода регистра 16. КроI

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

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

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

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

1249527

логично находят ные сечения.

остальные минималь10

f5

20

25

30

5

0

5

0

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

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

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

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

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

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