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

11 элементов И второй группы, третьи входы которых соединены с входами второго блока индикации и подключены к выходу третьего регистра, выход триггера модели вершины через второй элемент НЕ соединен с первым входом первого элемента И модели вершины, выходы запоминающего устройства блока управления соединены с установочными входами регистра, выходы разрядов которого через дешифратор соответственно соединены с управляющими входами элементов И группы, информационные входы которых соединены с выходами вторых элементов НЕ соответствующих моделей вершин, выходы 24318элементов И группы подключены к входам триггеров соответствующих моделей вершин, вьмодьг всех разрядов регистра сдвига, кроме последнего, соединены с вторыми входами первых элементов И соответствующих моделей вершин, выход последнего разряда сдвига соединен с управляющими входами элементов И первой группы всех моделей вершин, управляющие входы первьм регистров всех моделей вершин объединеныи подключенык выходу элемента задержки блока управления, выход второго элемента И каждой модели вершин соединен с вторым входом третьего элемента И соответствующей модели вершин, Изобретение относится к электронному моделированию и может быть использовано для решения задач на графах, в частности для нахождения максимальных сильно связанных подграфов, а также для нахождения весов редуцированного графа на всех этапах редукции и подсчета числа связей каждой вершины с ее, предшественниками. 0Известно устройство для исследования графов, содержащее модели вершин, соединенные между собой согласно топологии графа, регистры, блок управления, группу элементов И, 15 триггеры, элементы ИЛИ И .Недостатком известного устройства является невозможность организации процесса разложения графа на мак" симальные сильно связанные подграфы, 20 Наиболее близким к предлагаемому. по технической сущности является уст" ройство, содержащее модели вершин, соединенные между собой согласно то пологии исследуемого графа, регистр, вход и первый выход которого подключены к первому выходу и входу блока управлейия, второй, третий и четвертый выходы которого соединены соответственно с первым, вторым и третьим входами моделей вершин, информационные выходы регистра соединены с первыми входами элементов И группы, второй вход каждого из которых подключен к первому выходу соответствующей модели вершины, выходы элементов И группы подключены соответственно к четвертым входам моделей вершин, каждая из которых содержит первый и второй триггеры, первый и второй элементы ИЛИ, первый и второй формирователи импульсов, первый шестой элементы И, элемент НЕ, счетчик импульсов, блок индикации 2 .Недостатком известного устройства является низкая точность. Цель изобретения - повьппение точности моделирования.Поставленная цель достигается тем, что в устройство для моделирования графов, содержащее блок управления, выполненный в виде счетчика и генератора тактовых импульсов, первый вход которого соединен с выходом переполнения счетчика, а второй вход - с входом пуска устройства, модели вершин, соединенные сог" ласно топологии исследуемого графа, регистр сдвига и группу элементов И, причем каждая модель вершины выполнена в виде первого, второго и третьего элементов И, триггера, первого элемента НЕ, счетчика, первого блока индикации, причем в модели вершины выход первого элемента И соединен с входом счетчика, выход которого под10 15 20 15 30 35 40 45 50 55 з 11 ключен к входу первого блока индикацйи, выход триггера соединен с первым входом второго элемента И, причем выход последнего разряда регистра сдвига подключен к счетному входу счетчика блока управления, а выход генератора тактовых имйульсов блока управления соединен с входом сдвига регистра сдвига, дополнительно введены дешифратор и регистр, а блок управления дополнительно содержит элемент задержки, дешифратор и запоминающее устройство, причем адресные входы запоминающего устройства соединены с выходом дешифратора, входы которого соединены с выходами счетчика блока упр,"вления, счетный вход которого соединен с входом элемента задержки, каждая модель вершины дополнительно содержит первый, второй и третий регистры, первую, вторую и третью группы элементов И, второй элемент НЕ, второй блок индикации и сумматор, причем выход первого элемента И в каждой модели вершины соединен с первым входом третьего элемента И, выход которого подключен к информационному входу первого регистра, выход которого соединен с информационными входами элементов И первой группы, управляющие входы которых объединены и соединены с входом первого элемента НЕ модели вершины, выход которого соединен с первыми входами элементов И второй группы, выходы которых соединены с входами второго регистра, выход которого подключен к информационному входу второго элемента И и к информационным входам элементов И третьей группы, управляющие входы которыхобъединены и соединены с входомпервого элемента НЕ, выходы элементов И третьей группы соединены спервой группой входов сумматора,вторая группа входов которого соединена с выходами элементов И первойгруппы, выход сумматора соединен свходом третьего регистра и вторымивходами элементов И второй группы,третьи входы которых соединены свходами второго блока индикации иподключены к выходу третьего регистра, выход триггера модели вершинычерез второй элемент НЕ соединен спервым входом первого элемента И модели верд,ны, выходы запоминающегоустройства блока управления соедине 24318 4 ны с установочными входами регистра,выходы разрядов которого через дешифратор соответственно соединены суправляющими входами элементов Игруппы, информационные входы которых соединены с выходами вторыхэлементов НЕ соответствующих моделейвершин, выходы элементов И группыподключены к входам триггеров соответствующих моделей вершин, выходывсех разрядов регистра сдвига, кромепоследнего, соединены с вторымивходами первых элементов И соответствующих моделей вершин, выход последнего разряда регистра сдвигасоединен с управляющими входамиэлементов И первой группы всех моделей вершин, управляющие входы первыхрегистров всех моделей вершин объединены и подключены к выходу элементазадержки блока управления, выход вто"рого элемента И каждой модели вершины соединен с вторым входом третьегоэлемента И соответствующей моделивершин,На фиг, 1 представлена блок-схе-ма предлагаемого устройства для моделирования графа; на фиг. 2 - модель вершины; на фиг. 3 - блок управления.Устройство содержит модели вершинисследуемого графа 11, 1,., 1 я,блок 2 управления, регистр 3 сдвига,группу элементов И 41, 4 2 , 4 прегистр 5 номера вершины графа, дедифратор 6, полюса (входы и выходы)моделей вершин 7-15 и блока управления 16-19.В состав каждой модели вершины11, , 1 входят (фиг, 2) третий ипервый элементы И 20 и 21, перваяи третья группа элементов И 22 и 23,второй элемент И 24, вторая группаэлементов И 25, первый, второй итретий регистры 26-28, сумматор 29,второй и первый элементы НЕ 30 и 31,триггер 32, счетчик 33 числа связей,первый и второй блоки 34 и 35 индикации. В состав блока 2 управления входят (фиг, 3) запоминающее устройство 36, дешифратор 37, счетчик 38 циклов, генератор 39 тактовых импульсов и элемент 40 задержки.Устройство работает следующим образом.Посредством полюсов 11, 15 и 12, 14 модели вершин коимутируются междусобой в соответствии со структуройисследуемого графа. Регистр 3 сдвига, регистр 5 номера вершины графа,регистры 26, 27 и 28, сумматоры 29,счетчики 33 числа связей, счетчик 38 5циклов обнуляются, триггеры 32 всехмоделей вершин устанавливаются внулевое состояние. На регистры 27заносятся коды весов каждой вершины исследуемого графа, а в счетчик 1038 циклов - код адреса, обеспечивающего выборку из запоминающего устройства 36 кода номера вершины графа, начиная с которой необходимокачать редукцию графа, В .первый разряд регистра 3 сдвига заноситсяединица. Запускается генератор 39тактовых импульсов. В каждом цикле работы устройства производится редукция одной вершины графа, номер которой задан в регистре 5 номера вершины графа. Цикл, в свою очередь, состоит из Я+1 тактов (Я рабочих и один управляющий), в каждом из которых устанавливается наличие связи между редуцируемой и опрашиваемой вершинами, и в случае наличия такой связи она Фиксируется в счетчике 33 числа связей, а вес . редуцируемой вершины суммируется с весом опрашиваемой. Такой опрос ведется для всех вершин графа, за исключением редуцирудмой в данном цикле.35Пусть в качестве редуцируемой выбрана вершина графа с номером 1 (т.е. ее модель 11). В регистре 5 номера вершины графа находится дво 40 ичный код ее номера, а на соответст-вующем выходе дешифратора 6 - единичный сигнал. Этот сигнал поступает на второй вход элемента И 41, на первый вход которого через полюс 13 (выход 1) модели вершины 11 подает 45 ся единичный сигнал с выхода элемента НЕ 30. Сигнал с выхода элемента И 4 1 через полюс 8 (вход 2) модели вершины 11 поступает на единичный вход триггера 32 и устанавливает его в единичное состояние, В результате, единичный сигнал с выхода триггера 32 появляется на полюсе 14 (выход 2) модели вершины 11, а код веса, приписанного этой вершине, с регистра 27 через элемент И 24 поступает на полюс 15 (выхоп 3) модели вершины 1 . В то же время генератор 39 тактовых импульсов ввщает тактовые сигналы сдвига, которыепоступают на полюс 17 (выход 1) блока 2 управления и далее на вход сдвига регистра 3 сдвига. В каждом такте работы единичный сигнал с соответствующего разряда регистра сдвига, начиная с первого, поступает последовательно через полюса 9 (входы 3) моделей вершин на второй вход элемента И 21.. При наличии связи опрашиваемой вершины с редуцируемой (через полюса. 12 и 14 в соответствии с топологией графа) на первый вход элемента И 21 также поступает единичный сигнал с полюса 12. На третий вход элемента И 21 единичный сигнал поступает с выхода элемента НЕ 30. Если номера опрашиваемой и редуцируемой вершин совпадают, то с выхода элемента НЕ 30 на третий вход элемента И 21 поступает нулевой сигнал и сигнал опроса не проходит. При открытом элементе И 21 сигнал опроса поступает на второй вход элемента И 20, на первый вход которого через полюс 11 (вход 5) модели вершины поступает код веса редуцируемой вершины. При открытом элементе И 20 код веса редуцируемой вершины с ее выхода поступает на вход регистра 26 модело вершины, Одновременно по сигналу с выхода эле" мента И 21 в счетчике 33 осуществля ется подсчет связей опрашиваемой вершины с.редуцируемой, а информация об этом отражается в блоке 34 индикации.Приход очередного тактового сигнала с генератора 39 тактового ймпульса на вход сдвига регистра 3 сдвига приводит к появлению единичного сигнала на выходе следующего старшего разряда регистра 3 и описанный процесс повторяется для очередной модели вершины. Последовательное поступление В сигналов с генератора 39 тактовых импульсов на вход сдвига регистра 3 сдвига обеспечивает подключение И моделей вершин.и, следовательно, осуществляется последовательный просмотр всех вершин исследуемого графа,Очередной (0+1)-й сигнал сдвига с генератора 39 тактовых импульсов поступает на вход регистра 3 сдвига и обуславливает появление еднричного сигнала на выходе последнего1124 Я+1)-го разряда регистра, подключенного к полюсам 10 (входам 4) моделей вершин и полюсу 16 (входу) блока 2 управления.Укаэанный сигнал, поданный на 5 полюс 11 модели вершин, проходит палее на первые входы элементов И 22 и 23 первой и третьей групп и вход элемента НЕ 31В результате этого, коды весов редуцируемой и опрашивае ,мой вершин .с регистров 26 и 27 поступают на сумматор 29, где суммируются, и далее код суммы весов вершин поступает на регистр 28 и затем в блок 35 индикации. Одновременно 15 сигнал с выхода элемента НЕ 31 подается на второй вход элементов И 25 группы и блокирует поступление кода с регистра 28 на регистр 27. На третий вход элементов И 25 группы пода ется .сигнал с сумматора 29, который блокирует передачу кода из регистра 28 в регистр 27 при нулевой сумме в сумматоре. 25Кроме того, сигнал с выхода последнего (В+1)-го разряда регистра 3через полюс 16 блока 2 управленияпоступает на входы счетчика 38 циклов и элемента 40 задержки. Содержи- З 0мое счетчика циклов увеличивается наединицу, и в запоминающем устройстве 36 выбирается очередная ячейка,в которой записан код номера следующей редуцируемой вершины,Сигнал с выхода элемента 40 эа- .Идержки через полюс 18 (выход 2) блока 2 управления поступает на полюса7 (входы 1) всех моделей вершин идалее в каждой модели на вход установки нуля регистра 26, устанавливаяего в нулевое состояние. Так завершается один цикл редукции. В результате его реализации осуществляется последовательный просмотр всех вершин графа, в регистрах 28 моделей вершин записаны коды их новых весов .с учетом веса редуци 3188руемой в этом цикле вершины и наличия связей опрашиваемой вершины с редуцируемой. В счетчике 33 чцсла связей содержится код числа связей учитывающий число сворачиваемых свя" зей в цикле редукции. Информация о весах вершин и числе связей редуцированного графа в данном цикле редук. ции отражается соответственно в блоках 35 и 34 индикации.Очередной тактовый сигнал с генератора 39 импульсов начинает новый цикл редукции. Эт,т сигнал приводит в исходное состояние регистр 3 сдвига. В результате, сигнал на выходе (Я+1)-го разряда становится нулевым, Он поступает на входы элементов И 22 и 23 и элемента НЕ 31, Сигнал с выхода элемента НЕ 31 разблокирует элементы И 25 группы, и новый код веса данной вершины с регистра 28 переписывается в регистр 27. После этого осуществляется редукция очередной вершины графа, номер которой поступил в регистр 5 номера вершины графа из ячейки запоминающего устройства 36 через полюс 19 (выход 3) блока 2 управления. Дальнейшая последовательность операций соответствует рассмотренной.Устройство позволяет управлять глубиной редукции по усмотрению пользователя. В конце последнего цик-. ла редукции сигнал подается на вход счетчика 38 циклов и переполняет его, появляясь на выходе переполнения (управляющем выходе), откуда он поступает на вход останова генератора тактовых импульсов. На этом работа схемы устройства прекращается. После окончания М циклов редукции рассматриваемый граф в соответствии с его топологией можно представить в виде числа независимых сегментов.Таким образом, введение в устройство новых блоков и связей между ними позволяет повысить точность моделирования графов.1124318 Составитель А. КолчинРедактор Л, Апексеенко Техред А.Бабинец Гирняк рек аз 8282/39 Тиран 698 ударстюенного комитета С изобретений и открытий" а, Ж-.35, Раушская наб;, дПо СС ое ВНИИПИ Гос по, делам 113 О 35, Москв