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

ОП ИСАНИЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДГЛЕЛЬСТВУ Союз Советскнк Соцнаинстнческнк Республик(6 Ц Дополнительное к авт, свид-ву(22) Зайвлено 171276 (2) 2430980(18-24с присоединением заявки ЭЙ -(51 И. Кд. Ь 06 Г 1)136 Государственный комитет СССР по делам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ХАРАКТЕРИСТИК ГРАФАУстройство относится к области вычислительной техники и может быть использовано для исследования вероятностных графов.Известно устройство для определения характеристик связности вероятностных графов, содержащие элементы И, триггеры вершин, триггеры ребер, наборное поле ключи 1 .Недостатком известного устройства является то, что характеристики связности вероятностных графов определяются беэ учета числа подграфов, на которые разбивается исходный граф.Наиболее близким по технической сущности к изобретению является устройство для моделирования характеристик графа, содержащее блок отображения графа, триггеры вершин, единичные выходы которых подключены к первым входам ключей вершин, нулевые выходы триггеров вершин соединены с первыми входами элементов ИЛИ, выходы которых подключены к соответствуюшим входам элемента И, выход которого соединен с одним входом генератора импульсов, другой вход которого полключец к шине запуска, триггеры ребер, выходы когорых соединены со входами ключей ребер, выходы ключей ребер и вершинподключены к соответствующим входамблока отображения графа, группу ф ключей и группу последовательносоединенных ключей, при этом первыевходы соответствующих ключей обеихгрупп объединены, вторые входыгруппы последовательно соединенных то ключей подключены к нулевым выходам триггеров вершин, вторые входыгруппы ключей соединены с единичными выходами триггеров вершин,выходы группы ключей подключены ко 1 ф вторым входам ключей вершин, вторымвходам элементов ИЛИ и выходам блокаотображения графа, единичные входытриггеров вершин и ребер подключены к шинам результата розыгрыша фф вершин и ребер соответственно, нулевые входы триггеров вершин и реберсоединены с первой и второй шинамисброса соответственно 2. фт К недостатку указанного устройг.тва относится невоэможцость определения размера подграфов, ца которые распадается исходный граф.Целью изобретения является рас ширение функциоцальцых в можцс стейза счет учета определения размерачастей графа.Укаэанная цель достигается тем,что устройство содержит счетчик связ"ных вершин, блок дифференцирования,ключ, элемент задержки, счетчикичастей графа и распределитель, выходы которого подключены к входамсчетчиков частей графа, первый входраспределителя подключен к шинеопроса, второй вход распределителясоединен с выходом счетчика свяэ Оных вершин, информационные входыкоторого подключены к выходам ключа, информационные входы которогочерез блок дифференцирования соединены с нулевыми выходами соответствующих триггеров вершин, нходуправления ключа подсоединен кпервой шине сброса, первые входысоответствующих ключей обеих группчерез элемент задержки подключенык выходу генератора импульсов,. выход которого соединен со входомуправления счетчика связных вершинФункциональная схема устройствапредставлена на чертеже.Устройство для исследования вероятностных графов содержит шину 1запуска генератора импульсов, генератор импульсов 2, шину 3 окончания испытания, шины 4 и 4установки триггеров вершин и ребер в исходное состояние, элементы ИЛИб - бя, группу последовательносоедийенных ключей 7 - 7 п, группуключей 8 - 8 ключи 9 - 97, ключиребер 10 - 10 триггеры 11 - 11,вершин, триггеры 12 - 12 11 ребер, блок13 отображения графа, шийы 14 - 14результатов розыгрыша вершин, шины15 - 15 результатов розыгрыша ребер, шину 16 отсутствия вершин в розыгрыше, распределитель 17, счетчик 18 связанных нершин, элементзадержки 19, счетчики 20 - 20 ячгстей графа, ключ 21, блок 22 дифференцирования, шину 23 опроса.Устройство работает следующимобразом. С помощью блока 13 ключинершин 9 - 9 п и ребер 10 - 10 соединяются между собой в соответствии с топологией графа. Далее устройство работает по тактам,В такте 1 сигналы, поступая по шинам 4 и 4, устанавливают триггеры 11 -, 11, 12 -: 12 ш н нулевое положение и с помощью ключа 21 отключают входы счетчика 18 от нулевых выходов триггеров 11 в . 11 .В такте т по 14 - 14поступа 2ют сигналы результатов розыгрыша состояний вершин на входы тригеров 11 - 11 П, а по шинам 15- 15,поступают сигналы результатов розыгрыша состояний ребер на входы триггеров 12 - 12 Единичное состояние этих триггеров соответствуют наличию 20 25 ЗО 35 40 45 50 55 бО Г 5 вершины или ребра н данном розыгрыше. Между выходами ключей вершин 9 - 9 и ключей ребер 10 - 10 ш, присутствующими в данном розйгрыше, образуется электрический контакт, Если н данном розыгрыше нет ни одной вершины, на все входы элемента И 5 через элементы ИЛИ 6- бп бУДУт поданы сигналы с нулевых выходов триггеров 11 11 П. Элемент И срабатывает и на шине 3 йоявится сигнал об отсутствии вершин в данном розыгрыше. Если в данном розыгрыше присутствует хотя бы одна вершина то на шине 3 нет сигнала.В такте т 3 по шине 1 поступает сигнал запуска генератора импульсов 2. Сигналы с выхода генератора импульсов поступают на вход счетчика 18 и через элемент задержки 19 на входы ключейся хотя бы одна вершина, триггер 11 которой находится в единичном положении. После того, как все триггеры 11 - 11 П будут переброшены в нулевое положение, сработает элемент И 5 и подаст по шине 3 сигнал для перехода к новому розыгрышу вершин и ребер.Число частей, на которые распадается исходный граф по результатам данного розыгрыша вершин и ребер равно сумме импульсов, подсчитанных счетчиками 20 - 20 и а размеры этих частей соответствуют номерам заполненных счетчиков.Формула изобретенияУстройство для моделирования характеристик графа, содержащее блок отображения графа, триггеры вершин, единичные выходы которых подключены к первым входам ключей вершин, нулевые выходы триггеров вершин соединены с первыми входами элементов ИЛИ, выходы которых подключены к соответствующим входам элемента И, выход которого соединен с одним входом генератора импульсов, другой вход которого подключен к шине запуска, триггеры ребер, выходы которых соединены со входами ключей ребер, выходы ключей ребер и вершин подключены к соответствующим входам блока отображения графа, группу ключей и группу последовательно соединенных ключей, при этом первые входы соответствующих ключей обеих групп объединены, вторые входы группы последовательно соединенных ключей подключены к нулевым выходам триггеров вершин, вторые .входы группы ключей соединены с единичнымивыходами триггеров вершин, выходыгруппы ключей подключены ко вторимвходам ключей вершин, вторым входамэлементов ИЛИ и выходам блока отоб.ражения графа, единичные входы триг геров вершин и ребер подключенык шинам результата розыгрыша вершини ребер соответственно, нулевыевходы триггеров вершин и ребер соединены с первой и второй шинами 10 сброса соответственно, о т л ич а ю щ е е с я тем, что, с цельюрасширения функциональных возможностей за счет учета определения размера частей графа, устройство содержитсчетчик связных вершин, блок дифференцирования, ключ, элемент задержки,счетчики частей графа и распределитель, выходы которого подключены квходам счетчиков частей графа, первыйвход распределителя подключен к шинеопроса, второй вход распределителясоединен с выходом счетчика связныхвершин, информационные входы которогоподключены к выходам ключа, информационные входы которого через блок 25 дифференцирования соединены с нулевыми выходами соответствующих триггероввершин, вход управления ключа подсоединен к первой шине сброса, первыевходы соответствующих ключей обеих 30 групп через элемент задержки подключены к выходу генератора импульсов,выход которого соединен со входомуправления счетчика связных вершин.Источники информации, принятые 35 во внимание при экспертизе1. Авторское свидетельство СССРР 433504, кл. 006 б 7/48, 1972.2, Авторское свидетельство СССРУ 314214, кл. 606 б 7/48, 1970,656073 Составитеицкая Тех ед Э,ф ь И.Дубининаанта Корце Д.МельниРедактор Э.ГубЙ еЭакаэ 1528/40 а ССтий 3035 лиал ППП Патент, г.ужгород, ул.Проектна Р Тираж 779 ЦнИИПИ Государс по делам изо Москва, ЖРаПодпис нного комите тений и откр кая наб. д.