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

Союз Советских Социалистических Республик(22) Заявлен 1.10.76 836,18-2 присоединением заявки сударствеииын комите(5 1 681.33 (088.8 о 30,11.78, Б:оллетечь М 44кования описания 30.11.78 делам изобре открыт 72) Авто(54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ НЕОРИЕНТИРОВАННЫХ ГРАФОВ рез соответств юсоединен с первым ульсов, второй вык вторым входамв. Выход каждого рой гр ппы подствующего цндцкасоединен с входом с вторыми входа- второй группы.влена структурная 1 перебо 2, запо нонки ус вую гру каторы очей 7, ш емент И ецты 11 цй счет шину 1 ра сочетамцнающце тройства в ппу управб, вторую цну 8 про, гсцеразадержкц, ик 13, выб счцтыва 25 Граф моделируется с ствующего соединения чеи б, отображающих настройки элементов 11 образом, что время задЗ 0 пропорционально весу соответых клюграфа птаким сигналатвующего помощью управляек вершины задержь ержки цл соответсИзобретение относится к вычислительной технике.Известцо устройство для поиска прадеревьев направленного графа 1, содержащее элементы И, ИЛИ, ключи.Наиболее близким техническим решением к изобретению является устройство для моделирования неориентирова нных графов 2, содержащее блок перебора сочетаний, выходами подключенный к первым входам запоминающих триггеров, одни выходы которых через первую группу управляемых ключей соединены с соответствующими входами элемента И, а другие выходы - с первыми входами управляемых ключей второй группы, и счетчики.Недостаток известных устройств состоит в том, что они не дают возможности определить суммарный вес входящих в дерево ребер.Цель изобретения - расширение функциональных возможностей устройства путем определения суммарного веса входящих в дерево ребер,Указанная цель достигается тем, что устройство содержит индикаторы, элементы задержки, суммирующий счетчик, генератор импульсов и выходной индикатор, входом через суммирующий счетчик подключенный к выходам счетчиков, вход каждого цз которых че щий элемент задержки выходом генератора имп ход которого подключен 5 запоминающих трцггеро управляемого ключа вто ключен к входу соответ тора, выход элемента И генератора импульсов ц ми управляемых ключей На чертеже и ре дстя схема устройства. Она содержит блок ний, командную шццу 15 триггеры 3, шину 4 уста исходное состояцце, пер ляемых ключей 5, пндц группу управляемых кл верки проводимости, эл 20,тор 10 импульсов, элем счетчики 12, суммцрующ ходной индикатор 14 ц ния.ребра. Устройство работает по тактам 1, 1, 1 з и 1В такте 1 по шине 4 постугает сигнал установки устройства в исходное положение, устанаВЛИВающпй В н ль запоминающие триггеры 3 и генератор 10 импульсов. При подаче сигнала на командную шину 2 блок перебора сочетаний обоазует исследо. ватсльность всевозможных сочетаний по (1 И - 1)-м ребр из У имеющихся. В каждом такте 1, на выходе блока перебора сочетаний появляется одно из сочетаний Св , которое поступает на входы запоминающих триггеров 3, соответстзуощих ребрам, ко",орые присутствуют в образованном блоком перебора сочетании ребер. Запоминающие триггеры 3 перебрась;заются в единичное состояние и в соответствии с запомненной комбинацией реоер открывают соответствующие управляемые ключи 7 и б. Между входами открыты,; управляемых ключей 7 образуется электрический контакт. Если при случайном выборе ребер блоком перебора сочетаний сочетание их. обеспечивает образование связного графа иа исследуемом множестве верши, элсктричсский контакт устанавливается между всеми управляемыми ключами б. В том случае, если выбранное сочетание ребер ооразует несколько компонент связности, электрический контакт между управляемыми ключами нарушается и они образуют две группы или оолее.В такте 1 а по шине 8 поступает сигнал проверки проводимости на вход произвольно выбранного управляемого кгиоча 5, подключенного к шине 8 проверки проводимости. В том случае, если выбранная блоком 1 перебора сочетаний комбинация ребер образует связные граф, сигнал проверки проводимости проходит через все открытые управляемые ключи б и с выхода каждого из них проходит на входы элемента И 9. Так как сигнал проверки проводимости присутствует на всех входах элемента И 9, он появляется на его выходе и проходит па открытые запоминающими триггерами 3 управляемые ключи 7, а также запускает генератор 1 О пмпульсоз О счет 1 хи 12. 11 пульсь с генерато"з 10 через элементы 11 задержки поступают на входы счетчиков 12 до тех пор, пока не сработает элемент задержки, который через время, пропорциональное весу соответствующего ребра, разорвет цепь прохождения импульсов с генератора 10. Таким образом, показания счетчика 12 пропорциональны весу соответствующего ребра.Одновременно с этим сигнал проверки проводимости, проходя через открытые уп. равляемые ключи 7, засвечивает индикаторы б, присутствующие при данном розыгрыше. В том случае, если при выборе ребер блоком перебора сочетаний получилсядвух- или более компонентный граф, си.5 нал проверки проводимости поступаеттолько на ту часть управляемых ключей б,которая оказывается связанной с подключенной к шине 8 проверки проводимостиуправляемым ключом б. В результате этого сигнал проверки проводимости появляетоя только на части входов элемента И 9и он срабатывает, т. е. выходной сигнална нем отсутствует,В такте 1, по шине 15 считывания подается сигнал считывания на счетчики 12,В результате чего информационные сгналы, соответствующие чгслам подсчитанных импульсов, поступаот на суммирующий счетчик 13 и соединенный с ним ин.20 дикатор 1-1 с ммарной длины исследуемогодереза высвечивает число импульсов, соответствую.цее суммарному весу всех зхо.дяшх з данное дерево ребер.Формула изобретенпяУстройство для моделирования неориентированных графов, содержащее блок перебора сочетаний, выходы которого под- ЗО ключены к первым входам запоминающихтриггеров, одни выходы которых через первую группу управляемых ключей соединены с соответствуощими входами элемента И, другие выходы запоминающих триг геров подключены к первым входам управляемых ключей второй группы, и счетики, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем определения сумф-" марного веса входящих в дерево ребер,оно содержит индикаторы, элементы задержки, суммирлощий счетчик, генератор импульсов и вьходной индикатор, вход которого через суммирующий счетчик псдф 5 ключен к выходам счетчиков, вход каждого из которых через соответствующий элемент задержки соединен с первым выходом генератора импульсов, второй выход которого подклОчен к вторым входам запоми нающпх триггеров, выход каждого управляемого ключа Второй группы подключен к входу соответствующего индикатора, выход элемента И соединен с входом генератора импульсов и с вторыми входами уп равляемых ключей второй группы.Источники информации, принятые зовнимание при экспертизе:1. .Вторское свидетельство СССР27.906, 6 06 С 7,48, 1970,2, Авторское свидетельство СССР329538, кл. :. 06 С 7148, 1972.Редактор И. Грузова Техред С. Антипенко 1;с:, гт, р И. Снмкина 3 аказ 843/1268 1 д с"з 74НПО Государственного комитета СССР по делзм изобретенийМосква, Ж, Рзушск; яа 5., д. 4,5 Подписноеткрытий