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

 

0 П И С А Н И Е ()888134

ИЗОВУЕТВН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскик

Соцнапистическик

Респубики (61) Дополнительное к авт. свид-ву— (22) Заявлено 14 . О! . 80 (21) 2904682/18-24 с присоединением заявки М (23) Приоритет

Опубликовано 07.12.81. Бюллетень Ме 45

Дата опубликования описания 07.12.81 (5I)M. Кд.

G 06 F 15/36

3ЪаударетавннИ книнтвт

ССЕР ан аелна нзабретенкИ и откритнН (5з) УДК681.333 (088. 8) " Ъ с (72) Анто изобретения

В.Н.Червяцов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ МИНИИАЛЬНЬИ

СЕЧЕНИЙ ГРАФА

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

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

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

Наиболее близким к данному техническому решению является устройство для выбора сети связи 12), содержа- е щее блок управления, блок задания сети, коммутатор, логический блок, триггеры, регистры, блоки сравнения, счетчики.

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

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

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

ИЛИ, группа элементов И, группа триггеров, две группы элементов ИЛИ, регистры сдвига и блок управления, причем 1-тый (1 =I 2,....,1з-I выход первого распределителя соединен с 1-тым входом первой группы первого блока формирования топологии графа, т -тый вход второй группы которого подключен к 1 -тому выходу коммутатора и к 1-тому входу первого

888134

23 шифратора (j =),2,...,!1-1), К -тый выход которого соединен с первым входом К-того элемента И группы, второй вход которого подключен к K -тому выходу второго шифратора (k =1,2, К-2 ) 1 -тый вход которого соединен с выходом 1 -того элемента ИЛИ первой группы, выход -того элемента

И группы подключен к 1 -тому входу элемента ИЛИ, выход которого соединен с входом блока управления и первым выходом регистра сдвига, пер— вый вход которого подключен к первому выходу блока управления и входу коммутатора, 1 -тый выход которого соединен с 1-тым входом первой группы второго блока формирователя топологии графа (< =1,2,...,Й-1), К -тый вход второй группы которого подключен к +1-му выходу коммутатора (И=

=1,2,...Ì-?), вход которого соединен,. с первыми входами триггеров группы, выход -того триггера подключен к †то входу группы второго распределителя (! =1,2,.../И), выход которого соединен со вторым входом регистра сдвига, вход И -ного счетчика группы соединен с И +1-м выходом регистра сдвига (!1=1,..., М-6+1), 1-тый вход -той группы первого блока формирования топологии графа подключен к

1 -тому входу †.того элемента ИЛИ второй группы, выход которого соединен со вторым входом j -того триггера группы (1 =1,2,...18-1, ) =1,2,...,IN) вход первого распределителя подключен ко второму выходу блока управления, третий выход которого соединен со входом второго распределителя, 11-ный выход К-той группы второго блока формирования топологии графа подключен к М-ному входу К -того элемента ИЛИ первой группы Ф =

=l,2,...М-2, щ=1,2,...Я-1-К).

Блок управления содержит генератор тактовых импульсов, два тригге— ра, четыре элемента И, счетчик и дешифратор, причем выход генератора тактовых импульсов соединен с первыми входами элементов И, выходы первого, второго и третьего элементов

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

1О

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

Первый блок формирования топологии графа содержит М-1 группу эле— ментов И, причем первые входы элементов И 1 -той 1,! =1,2, ..., Я-1) группы объединены и являются -тым входом первой группы блока, вторые входы элементов И -той группы объединены и являются 1 -тым входом второй группы блока, выход -того элемента И 1-той (=1,2,...,/И)группы является l òûì выходом ) -той руппы блока.

Второй блок формирования топологии графа содержит Й-2 группы элементов И, причем первые входы всех элементов И 1-той (! =1,2,... Я-2) группы объединены и являются q -тым входом первой группы блока, вторые входы ) -тых элементов И всех групп объединены и являются --тым входом второй группы блока, выход 1 -того элемента И 1--той группы является -тым выходом (y =1,2,...,N †1 †17

1 -той группы блока.

На фиг. 1 представлена схема устройства, на фиг. 2 — схема первого блока формирования топологии, на фиг. 3 — схема блока управления; на фиг. 4 — схема второго блока формирования топологии.

Устройство содержит распределители 1,2, блок управления 3 коммутатор 4, блоки формирования топологии графа 5 и 6, шифраторы 7 и 8, триггеры 91-9щ, регистр сдвига 10, счетчики 11А -ill!!! g, элементы

ИЛИ 12 — 12Й 2, 13) — 13М, 14.

Прямой блок формирования топологии содержит элементы И 15 -15,„, 16! — 16!1, 17,!-17М, 181-18 !.

Блок управления содержит генератор тактовых импульсов 19, элементы

И 20-23, триггеры 24, 25, счетчик 26, дешифратор 27.

888134

Второй блок формирования топалов гии содержит элементы И: 28 -28„,, 29,1 29М Ьэ 30,1 302, 311 °

В работе устройства следует выделитель два этапа — этап задания струк- 3 туры графа и этап вычисления числа минимальных сечений одинаковой размерности.

Рассмотрим этап задания структуры графа. Основой для задания графа в 10 устройстве является граф, имеющий

Я вершки и М ребер, в котором все элементы пронуяероваиы.

Буй э анин структуры графа на блоке форииров@ния топологии 5 под- >s готамеюак1тся ценя срабатывания элементов Н в каЖдой строке (строка ссютветствует определенной вершине) которые соатВетствуют ребрам, идентичнмм дайной верВине (всего элемен- 311 тов И s строке блока 5 столько, сколько ребер в графе). На блоке формирования топологий в каждой строке подготавливаются цепи срабатывания элементов И тех вершин, с которыми 3З данн®я (соответствующая строке) вершика иепосрадственно связана. Нервам строка баока 6 соответствует первой вершине, Вторая строка поля второй вефивМв,..., последняя строка — Я-2-ой аер@ине графа. В то же время первый элемект И первой строки соответствует второй вершине, второй элемент — третьей,..., по" следний — И-1-й ьерййяе. Аналогич3$ но первый (левый) элемент второй стуокн соответствует третьей вершина, второй — четвертой,..., последний — 1-1-вой вершине графа. Для остажных строк блока формирования топологии б назначение элементов

И подобно вышеизложенному.

Яа этапе вычисления числа минимаиъных сечений устройство работает под действиеи импульсов, наступающих от блока управления 3.

Первый импульс от генератора тактовых импульсов 19 возбуждает первый выход блока управления. Сигнал с этого выхода сбрасывает в нуль триггеры 9 -9р и считывает информаЯ 1 цию из регистра 10. В то же время сит нал, поступая на вход коммутатора

4, возбуждает его первый и второй выходы. Сигналы с выходов коммутатора

S5 поступают на блоки формирования топологии 5, 6 и шифратор 8.

Шифратор 8 при наличии сигнала на любых двух входах возбуждает первый выход, на любых трех — второй,..., на f4-1-вых входах — потенциал на

N-2-вом выходе.

Если номера возбужденных выходов коммутатора соответствуют вершинам, непосредственно связанным между собой, то через блок 6 будет возбуждено число входов шифратора 7 на один меньше, чем возбуждено выходов коммутатор 4. Шифратор 7, если возбужден адин его вход, формирует сигнал на выходе 1, если два входа— на выходе 2. .. если возбуждены все М-2 входа — сигнал íà k -- 2--м выходе °

Таким образом, если первая и вторая вершины графа связаны между собой, будут возбуждены одноименные выходы шифраторов 7 и 8. Тогда сигнал поступит на элемент И 15 и да 1 лее на элемент ИЛИ 14.

С элемента ИЛИ 14 сигнал будет подан на вход блока управления 3 и запишет единицу в нулевой разряд регистра 10.

Если на входе блока управления есть сигнал, последукпцие Я -1 импульсов будут поданы на второй выход, следующие JA импульсов — на третий выход и после прохождения g -1 и М имнульсов будет снова возбужден выход I блока управления, иначе (если нет сигнала на входе 2) второй импульс опять возбудит первый выход н заставит перейти коммутатор

4 в следующее положение.

Импульсы с выхода 2 блока управления И-1, поступающие на вход распределителя 1, возбуждают поочередно 1, 2, 3,..., И-1-вый выходы.

Так как возбуждены выходы 1 и 2 коммутатора 4, то при подаче сигнала на второй выход распределителя сигнал снимается с тех элементов И первой строки, цепи срабатывания которых подготовлены при задании структуры графа, аналогично будет при подаче сигнала на второй выход, распределителя 1. С элементов И строк блока формирования топологии 5 через элементы ИЛИ 13 сигналы поступят на единичные входы соответствующих триггеров и переведут их в единичное состояние.

Если подготовлены цепи срабатывания одноименных элементов И двух строк блока формирования топологии

5, соответствующий триггер перейдет

888134 сначала в единичное состояние, а затем вернется в нулевое, Следующие М импульсов поступают на выход 3 блока управления и далее на вход "0" распределителя 2. Распределитель 2 при поступлении на

его вход импульсов опрашивает триг4 геры 9А-9 уи при наличии единичного состояния триггера формирует импульс сдвига в параллельный регистр 10.

Таким образом, сколько триггеров будет находиться в единичном состоянии, до такого разряда будет сдвинута 1 влево ) единица в параллельном регистре 10.

Последующий импульс поступит опять на первый выход блока управления и с него — на вход "Сб" триггеров

9,1-91», вход "Сч" регистра 10, вход коммутатора 4, который, перейдя в последующее положение„ подаст сигналы на выходы 1 и 3.

С поступлением третьего импульса на вход коммутатора 4 возбуждаются выходы 1 и 4, далее 1 и 5, 1 и 6..., 1 и Й-l, затем 2и 3, 2 и 4,...2 и Я-l, 3 и 4,..., И-2 и 1 1-1, в дальнейшем 1,2и 3; 1,2и4,... итд. до 1,2 3,..., N — 1.

После обработки цикла с возбужденными 1,2,3,..., И-1 выходами коммутатора 4, коммутатор примет исходное состояние, и устройства закончит подсчет минимальных сечений графа.

Показания счетчиков 111-11„ 4равны числу минимальных сечений, размерность сечения совпадает с номером счетчика.

Устройство позволяет упростить процесс выделения минимальных сечений графа при исследовании надежности систем.

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

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

Ъ

2. Устройство по и. 1, о т л и ч а ю щ е е с я тем, что блок управления содержит генератор тактовых импульсов, два триггера, четыре элемента группа триггеров, две группы элементов ИЛИ, регистры сдвига и блок управления, причем 1 -тый (1 =1,2,... g — 1) выход первого распределителя соединен с 1 -тым входом первой группы первого блока формирования топологии графа, 1 -тый вход второй группы которого подключен к -тому выходу коммутатора и к 1 -тому входу первого

1р шифратора (1 =1 2,...,Я -1), К вЂ” тый выход которого соединен с первым входом К-того элемента И группы, второй вход которого подключен к К -тому вы- . ходу второго шифратора (K=l,2,...>Я-2)

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

ИЛИ, выход которого соединен с входом блока управления и первым выходом ре— гистра сдвига, первый вход которого подключен к первому выходу блока управления и входу коммутатора, 1 -тый выход которого соединен с q --тым входом первой группы второго блока формирователя топологии графа (1

=1,2,..., Я -1), К -тый вход второй группы которого подключен к К +1-му выходу коммутатора (К =1,2,..., N — 2), вход которого соединен с первыми входами триггеров группы, выход -того триггера подключен к 1 -тому входу группы второго распределителя (j

=1,2,..., Я), выход которого соединен со вторым входом регистра сдвига, 35 вход 1-ного счетчика группы соединен с И +1-м выходом регистра сдвига (у1 =1,..., )N-й +1, j тый выход 1 -той группы первого блока формирования топологии графа подключен

40 к 1-тому входу 4 -того элемента ИЛИ второй группы, выход которого соедиВ нен со вторым входом )-того триггера группы (4 =1;2,..., Я-1 g

1,2,..., М) вход йервого распре45 делителя подключен ко вгораму выходу блока управления, третий выход которого соединен со входом второго распределителя, Щ- ный выход К-той группы второго блока формирования то- пологии rpaAa подключен к Al-ному входу К -того элемента ИЛИ первой группы (K,=1,2,..., Я-2, И=1,2,..., М—

1 — К).

8881

И, счетчик и дешифратор, причем выход генератора тактовых импульсов соединен с первыми входами элементов И, выходы первого, второго и третьего элементов И являются соответственно первым, вторым и третьим выходами блока, выход четвертого элемента И подключен к первому входу счетчика, выходы которого соединены с соответствующими входами де- 1О шифратора, первый выход которого подключен к первому входу первого триггера и второму входу счетчика, третий вход которого соединен с выходом первого элемента И, второй вход которого подключен к вторым входам второго и четвертого элементов И и выходу второго Уфиггера, первый вход которого является входом блока, второй вход второго триггера соединен со вторым входом третьего элемента И, вторым выходом дешифратора и вторым входом первого триггера, выход которого соединен с третьими входами второго и третье- д го элементов И.

3. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что первый блок формирования топологии графа содержит Я-1 группу элементов И, при34 1О чем первые входы элементов И q -той (1 =1, 2,..., N ) группы объединены и являются 1 -тым входом первой группы блока, вторые входы элементов И

1 -той группы объединены и являются -тым входом второй группы блока, выход -того элемента И 1-той (=

=1,2,..., М) группы является -тым выходом 1-той группы блока.

4. Устройство по п. 1, о т л и— ч а ю щ е е с я тем, что второй блок формирования топологии графа содержит

Я -2 группы элементов И, причем первые входы всех элементов И 1 -той

{ 1=1,2,..., tN-2) группы объединены и являются 1 -тым входом первой груп- пы блока, вторые входы 1 -тых элементов И всех групп объединены и являются -тым входом второй группы блока, выход q -того элемента И

-той группы является 1 -тым выхо.,дом (j =1,2,..., К -l- 6 ) j -той группы блока.

Источники информации, принятые во внимание при экспертизе

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

Ф 468244, кл. G Об F 15/36, 1971, 2. Авторское свидетельства СССР па заявке У 2414862/18-24, кл. G 06 F 15/36, 1976 (прототип).

888134

Составитель Л.Терехов

Редактор В.Федотов Техред Т.Наточка Корректор С.Шекмар

Заказ 10726/14 Тираж 748 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4