Устройство для моделирования графов Советский патент 1984 года по МПК G06F15/173 

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

24318

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

УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ, содержащее блок управления, выполненный в виде счетчика и генератора тактовых импульсов, первый вход которого соединен с выходом переполнения счетчика, a второй вход с входом пуска устройства, модели вершин, соединенные согласно тополо гни исследуемого графа, регистр сдвига и группу элементов И, причем каждая модель вершины выполнена в виде первого, второго и третьего элементов Л, триггера, первого элемента НЕ, .счетчика, первого блока индикации, причем в модели вершины выход первого элемента И соединен с входом счетчика, выход которого подключен к , входу первого блока индикации, выход триггера соединен с первым входом второго элемента И, причем выход последнего разряда регистра сдвига подключен к счетному входу счетчика блока управления, a выход генератора тактовых импульсов блока управления соединен с входом сдвига регистра сдвига, отличающееся тем, что, с целью повышения точности моделирования, в устройство дополнительно введены дешифратор и регистр, a блок управления дополнительно содержит элемент задержки, дешифратор и запоминающее устройство, причем адресные входы запоминающего устройства соединены с выходом дешифратора, входы которого соединены с выходами счетчика блока управления, счетный вход которого соединен с входом эле- мента задержки, каждая модель вершины дополнительно содержит первый, второй и третий рггистры, первую, вторую и третью группы элементов И, второй элемент НЕ, второй блок инди§ кации и сумматор, причем выход первого элемента И в каждой модели верten шины соединен с первым входом третье-, го элемента И, выход которого подключен к информационному входу первого регистра, выход которого соединен с информационными входами элементов И первой группы, управляющие входы которых объединены и. соединены с входом первого элемента НЕ модели вершины, выход которого соединен с N9 первыми входами элементов И второй группы, выходы которых соединены с :о входами второго регистра, выход которого подключен к информационному эо входу второго элемента И и к информационным входам элементов И третьей группы, управляющие входы которых объединены и соединены с входом первого элемента НЕ, выходы элементов И третьей группы соединены с первой группой входов сумматора, вторая группа входов которого соединена с выходами элементов И первой группы, выход сумматора соединен с входом третьего регистра и вторьми входами

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

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

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

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

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

Недостатком известного устройства является низкая точность.

Цель изобретения - повышение точности моделирования.

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

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

На фиг. 1 представлена блок-схема предлагаемого устройства для моделирования графа; на фиг. 2 - модель вершины; на фиг. 3 - блок управления .

Устройство содержит модели вершин исследуемого графа 1, Ij, ..., 1,, блок 2 управления, регисп-р 3 сдвига, группу элементов И 4, 42, ... п регистр 5 номера вершины графа, дешифратор 6, полюса (входы и выходы) моделей вершин 7-15 и блока управления 16-19.

В состав каждой модели вершины Ц, ... Ц входят (фиг. 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ЧИсла связей, счетчик 3 циклов обнуляются, триггеры 32 всех моделей вершин устанавливаются в нулевое состояние. На регистры 27 заносятся коды весов каждой вершины исследуемого графа, а в счетчик 38 циклов - код адреса, обеспечиваю щего выборку из запоминающего устройства 36 кода номера вершины графа, начиная с которой необходимо начать редукцию графа. В jiepBbrii раз ряд регистра 3 сдвига заносится единица. Запускается генератор 39 тактовых импульсов. В кдждом цикле работы устройства производится редукция одной вершины графа, номер которой задан в регист ре 5 номера вершины графа. Цикл, в свою очередь, состоит из N+1 тактов (N рабочих и один управляющий), в каждом из которых устанавливается наличие связи между редуцируемой и опрашиваемой вершинами, и в случае наличия такой связи она фиксируется в счетчике 33 числа связей, а ве редуцируемой вершины суммируется с весом опрашиваемой. Такой опрос ведется для всех вершин графа, за исключением редуцируемой в данном цик ле. Пусть в качестве редуцируемой выбрана вершина графа с номером 1 (т.е. ее модель 1j). В регистре 5 номера вершины графа находится двоичный код ее номера, а на соответст вующем выходе дешифратора 6 - едини ный сигнал. Этот сигнал поступает на второй вход элемента И 4|, на пе вый вход которого через полюс 13 (выход 1) модели вершины 1 подается единичный сигнал с выхода элемен та НЕ 30. Сигнал с выхода элемента И 4 через полюс 8 (вход 2) модели вершины If поступает на единичный вход триггера 32 и устанавливает его в единичное состояние. В резуль тате, единичный сигнал с выхода три гера 32 появляется на полюсе 14 (выход 2) модели вершины 1j, а код веса, приписанного этой вершине, с регистра 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 и описанный процесс повторяется для очередной модели вершины. Последовательное поступление N сигналов с генератора 39 тактовых импульсов на вход сдвига регистра 3 сдвига обеспечивает подключение N моделей вершин и, следовательно, осуществляется последовательный просмотр всех вершин исследуемого графа. Очередной (Нн-1)-й сигнал сдвига с генератора 39 тактовых импульсов поступает на вход регистра 3 сдвига и обуславливает появление единичного сигнала на выходе последнего (N-fl)-ro разряда регистра, подключен ного к полюсам 10 (входам 4) моделей верпшн и полюсу 16 (входу) блока 2 управления. Указанный сигнал, поданный на полюс 11 модели вершин, проходит далее на первые входы элементов И 22 и 23 первой и третьей групп и вход элемента НЕ 31; В результате этого, коды весов редуцируемой и опрашиваемой вершин с регистров 26 и 27 посту пают на сумматор 29, где суммируются, и далее код суммы весов вершин поступает на регистр 28 и затем в блок 35 индикации. Одновременно сигнал с выхода элемента НЕ 31 подается на второй вход элементов И 25 группы и блокирует поступление кода с регистра 28 на регистр 27. На третий вход элементов И 25 группы подается сигнал с сумматора 29,- который блокирует передачу кода из регистра 28 в регистр 27 при нулевой сумме в сумматоре. Кроме того, сигнал с выхода последнего (N-fl)-ro разряда регистра 3 через полюс 16 блока 2 управления поступает на входы счетчика 38 циклов и элемента 40 задержки. Содержимое счетчика циклов увеличивается нь единицу, и в запоминающем устройстве 36 выбирается очередная ячейка, в которой записан код номера следующей редуцируемой вершины. Сигнал с выхода элемента 40 задержки через полюс 18 (выход 2) блока 2 управления поступает на полюса 7 (входы 1) всех моделей вершин и далее в каждой модели на вход устано ки нуля регистра 26, устанавливая его в нулевое состояние. Так завершается один цикл редукции. В результате его реализации осуществляется последовательный просмотр всех вершин графа, в регистрах 28 моделей вершин записаны коды их новых весов с учетом веса редуци18вруемой в этом цикле вершины и наличия связей опрашиваемой вершины с редуцируемой. В счетчике 33 числа связей содержится код числа связей, учитывающий число сворачиваемых связей в цикле редукции. Информация о весах вершин и числе связей редуцированного графа в данном цикле редукции отражается соответственно в бло-ках 35 и 34 индикации. Очередной тактовый сигнал с генератора 39 импульсов начинает новый цикл редукции. Этот сигнал приводит в исходное состояние регистр 3 сдвига. В результате, сигнал на выходе (N+1)-ro разряда становится нулевьм. Он поступает на входы элементов И 22 и 23 и элемента НЕ 31. Сигнал с выхода элемента НЕ 31 разблокирует элементы И 25 группы, и новый код веса данной вершины с регистря 28 переписывается в регистр 27. После этого осуществляется редукция очередной вершины графа, номер которой поступил в регистр 5 номера вершины графа из ячейки запоминающего устройства 36 через полюс 19 (выход 3) блока 2 управления. Дальнейшая последовательность операций соответствует рассмо тренн ой. Устройство позволяет управлять глубиной редукции по усмотрению пользователя. В конце последнего цикла редукции сигнал подается на вход счетчика 38 циклов и переполняет его, появляясь на выходе переполнения (управляющем выходе), откуда он поступает на вход останова генератора тактовых импульсов. На этом работа схемы устройства прекращается. После окончания М циклов редукции рассматриваемый граф в соответствии с его топологией можно предста- : ВИТЬ в виде числа независимых сегментов. Таким образом, введение в устройство новых блоков и связей между ними позволяет повысить точность моделирования графов.

7

I

-«W

1,

15

12

12

.0.

«X

19

fn

n

n

Д

3

и

f

19

It

II

ГТ1 m

I I у A.JLJ

16 О

M:mD

38

J7

Останов.

Пуск

39

/7Ь

иг.З

19

-о