Устройство для моделирования характеристик графа

 

ОП NCAHNE

ИЗОБРЕТЕНИЯ

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

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

Соцнапнстнчвскн»

Респувннк

„ц656073 (6Ö Дополнительное к авт. свид-ву(22) Зайвлено171276 (2l} 2430980/18-24 с присоединением заявки ЭЙ— (23) Приоритет—

Опубликовало 0504.79. Бюллетень % 13

Лата опубликования описания 050479 (5i) И. Кл.

4 Оо Г 1)j36

Государстееииый комитет

СССР по делам изобретений и открмтий (S3) УВК 681. 333 (088.81 (72) Автор изобретения

В.H.×åðâÿöîâ

Pl) Заявитель (54} УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ХАРАКТЕРИСТИК ГРАФА

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

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

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

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

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

° 6 ключей подключены к нулевым выходам триггеров вершин, вторые входы группы ключей соединены с единичными выходами триггеров вершин, выходы группы ключей подключены ко вторым входам ключей вершин, вторым входам элементов ИЛИ и выходам блока отображения графа, единичные входы триггеров вершин и ребер подключены к шинам результата розыгрыша вершин и ребер соответственно, нулевые входы триггеров вершин и ребер соединены с первой и второй шинами сброса соответственно 2). @ К недостатку указанного устрс>йг. тва относится невозможность определения размера подграфов, на к тторые распадается исходный граф.

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

656073 за счет учета определения размера частей графа.

Укаэанная цель достигается тем, что устройство содержит счетчик связных вершин, блок дифференцирования, ключ, элемент задержки, счетчики частей графа и распределитель, выхо- Б ды которого подключены к входам счетчиков частей графа, первый вход распределителя подключен к шине опроса, второй вход распределителя соединен с выходом счетчика свяэ- 10 ных вершин, информационные входы которого подключены к выходам ключа, информационные входы которого через блок дифференцирования соединены с нулевыми выходами соответ- 15 ствующих триггеров вершин, нход управления ключа подсоединен к

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

Функциональная схема устройства представлена на чертеже.

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

6 — - 6, группу последовательно соедийенных ключей 7 — 7>, группу ключей 8 — 8, ключи 9„ — 97, ключи ребер 10 — 10,„, триггеры 11„ — 11, вершин, триггеры 12 — 12щ ребер, блок

13 отображения графа, шийы 141 в 14 результатов розыгрыша вершин, шины

15 — 15 результатов розыгрыша реФ бер, шину 16 отсутствия вершин в розыгрыше, распределитель 17, счетчик 18 связанных нершин, элемент задержки 19, счетчики 20 — 20 частей графа, ключ 21, блок 22 дифференцирования, шину 23 опроса.

Устройство работает следующим образом. С помощью блока 13 ключи нершин 9 — 9 и ребер 101 в 10 ñîåдиняются между собой в соответствии с топологией графа. Далее устройство работает по тактам.

В такте t сигналы, поступая по шинам 4„ и 4, устанавливают триггеры 114 - . 11, 12„-: 12 ш н нулевое положение и с помощью ключа 21 отключают входы счетчика 18 от нулевых выходов триггеров ll †. 11 .

В такте 1 по 14 — 14 поступа2 4 ют сигналы результатов розыгрыша состояний вершин на входы тригеров

ll llП, а по шинам 15 - 15,п поступают сигналы результатов розыгрыша состояний ребер на входы триггepos 12„ — 12 Единичное состояние этих триггеров соответствуют наличию

ЗО

65 верши«ы или ребра н данном розыгрыше.

Между выходами ключей вершин 9„ — 9 и ключей ребер 104 в 10ш, присутствующими в данном розйгрыше, образуется электрический контакт. Если н данном розыгрыше нет ни одной вершины, на все входы элемента И 5 через элеме«ты ИЛИ 6„- 6 будут поданы сигналы с нулевых выходов триггеров 11

11П. Элемент И срабатывает и на шине

3 йоявится сигнал об отсутствии вершин в данном розыгрыше. Если в данном розыгрыше присутствует хотя бы одна вершина„ то на шине 3 нет сигнала.

В такте т> по шине 1 поступает сигнал запуска генератора импульсов 2.

Сигналы с выхода генератора импульсов поступают на вход счетчика 18 и через элемент задержки 19 на входы ключей

7„, 8 . При этом счетчик 18 очищается и подготавливается к подсчету связанных вершин. Если первая вершина присутствует в данном розыгрыше, то единичным выходом триггера 11„ открывается ключ 8 через который первый импульс с генератора поступает на вход ключа первой вершины и затем через блок отображения графа на нсе ключи вершин, связанных с первой. Одновременно зти же сигналы поступают на входы сброса соответствующих триггеров. При установке триггеров в нулевое положение с их нулевых ныходон через блок 22 и ключ 21 сигналы поступают на вход счетчика 18. Счетчик 18 подсчитывает число связан«ых верши« и подает сигнал на распределитель

17, который подключает вход соответствующего счетчика 20 — 20 к и шине 23.

В такте 4@ поступает сигнал по шине опроса 23, который фиксируется выбранным счетчиком. Если первая вершина отсутстнует н розыгрыше, сигнал с генератора поступает через ключ 7 на входы ключей 7 и 8 > и так далее.

Таким образом, первый импульс с генератора импульсов 2, проходя через ключ 7 — 7п и 8 - 8 и, обнаруживает присутствующую вершину.

Триггеры 11„ — llп, соответствующие этой вершине и нершинам, связанным с ней, перебрасываются в нулевое положение. Число таких триггеров подсчитывается счетчиком 18. На основании этого числа выбирается соответствующий счетчик 20, н котором в такте опроса записывается единица. Второй импульс с генератора импульсов очищает счетчик 18 и обнаруживает присутствующую вершину из оставшихся нершин, триггеры

11 которых находятся в еди«ич«ом положении. Импульсы с генератора импульсов поступают на ключи 7 —

7 и 8< — 8 до тех пор, пока имеети

656073 ся хотя бы одна вершина, триггер

11 которой находится в единичном положении. После того, как все триггеры 11 — 11 будут переброшены л в нулевое положение, сработает элемент И 5 и подаст по шине 3 сигнал для перехода к новому розыгрышу вершин и ребер.

Число частей, на которые распадается исходный граф по результатам данного розыгрыша вершин и pe6ep i равно сумме импульсов, подсчитанных счетчиками 20 — 20 а размеры этих частей соответствуют номерам заполненных счетчиков.

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

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

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

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

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

35 во внимание при экспертизе

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

9 433504, кл. 006 6 7/48, 1972.

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

Р 314214, кл. G06 G 7/48, )970.

656073

Составитель И.Дубинина

Редактор Э.Губницкая Техред Э.Фанта Корректор Д.Мельниченко

Заказ 1528/40 Тираж 779 Подписное

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

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

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