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

 

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

СОЮЗ COBETCHHX в с во с в со

РЕСПУЬЛИН

6% OD

315Р С 06 Р 1.5/20

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

W ДАММ ИЗО1-РКТЕНИй И ОТНРНТИй

ОПИСАНИЕ ИЗОБРЕТЕНИЯ в свтоссвовт свввстслвствт (21) 3609773/24-24 (22) 05.05.83 (46) 15.11.84. Бюл. 9 42 (72) А.И. Захаров, Ю.А. Песчанский, Г.А. Брякалов, В.В. Ковалев и В.Н. Кустов (53) 681.333.(088.8) (56) 1. Авторское свидетельство СССР

У 408312, кл. С. 06 F 15/20, 1971.

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

В 643880,кл. G 06 F 15/20, 1975 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВА-

НИЯ ГРАФОВ, содержащее блок управле-. ния, выполненный в виде счетчика и генератора тактовых импульсов, первый вход которого .соединен с выходом переполнения счетчика, а второй вход— с входом пуска устройства, модели вершин, соединенные. согласно топологии исследуемого графа, регистр сдвига и группу элементов И, причем каждая модель вершины выполнена в виде первого, второго и третьего элемен. тов Л, триггера, первого элемента НЕ,, счетчика,.первого блока индикации, причем в модели вершины выход первого элемента И соединен с входом. счетчика, выход которого подключен к . входу первого блока индикации, выхоц триггера соединен с первым входом второго элемента И, причем выход последнего разряда регистра сдвига подключен к счетному входу счетчика блока управления, а выход генератора тактовых импульсов блока управления соединен с входом сдвига регистра сдвига, о т л и ч а ю щ е е с я тем, что, с целью повышения точности моделирования, в устройство дополнительно введены дешифратор и регистр, а блок управления дополнительно содержит элемент задержки, дешифратор и запоминающее устройство, причем адресные входы запоминающего устройства соединены с выходом дешифратора, входы которого соединены с выходами счетчика блока управления, счетный вход которого соединен с входом элемента задержки, каждая модель вершины дополнительно содержит первый, второй и третий р гистры, первую, вторую и третью группы элементов И, второй элемент НЕ, второй блок .индикации и сумматор, причем выход пер- Я вого элемента И в каждой модели вершины соединен с первым входом тре ье-, го элемента И, выход которого подключен к информационному входу первого регистра, выход которого соединен .с информационными входами элементов

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

И третьей группы соединены с первой группой входов сумматора, вторая группа входов которого соединена с выходами элементов И первой группы, выход сумматора соединен с входом третьего регистра и вторыми входами

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

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

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

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

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

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

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

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

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

20

30

40

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

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

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

Устройство содержит модели вершин исследуемого графа 11, 1, ..., 1,, блок 2 управления, регистр 3 сдвига, группу элементов И 41, 4, ..., 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 модели вершин коимутируются между

1124318 собой в соответствии со структурой исследуемого графа. Регистр 3 сдвига, регистр 5 номера вершины rpa@a, регистры 26, 27 и 28, сумматоры 29, счетчики 33 числа связей, счетчик 38 циклов обнуляются, триггеры 32 всех моделей вершин устанавливаются в нулевое состояние. На регистры 27 заносятся коды весов каждой вершины исследуемого графа, а в счетчик

38 циклов — код адреса, обеспечивающего выборку из запоминающего устройства 36 кода номера вершины графа, начиная с которой необходимо качать редукцию графа. В .первый раз- IS ряд регистра 3 сдвига заносится единица. Запускается генератор 39 тактовых импульсов.

В каждом цикле работы устройства производится редукция одной вершины графа, номер которой задан в регистре 5 номера вершины графа. Цикл, в свою очередь, состоит из N+1 тактов (N рабочих и один управляющий), в . каждом из которых устанавливается наличие связи между редуцируемой и опрашиваемой вершинами, и в случае наличия такой связи она фиксируется в счетчике 33 числа связей, а вес . редуцируемой вершины суммируется с весом опрашиваемой. Такой опрос ведется для всех вершин графа, за исключением редуцируемой в данном цикле. 35

Пусть в качестве редуцируемой выбрана вершина графа с номером 1 (т.е. ее модель 11). В регистре 5 номера вершины графа находится дво40 ичный код ее номера, а на соответст- i вующем выходе дешифратора 6 — единич» ный сигнал. Этот сигнал поступает на второй вход элемента И 41, на первый вход которого через полюс 13 (выход 1) модели вершины 1I подает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 и описанный процесс повторяется для очередной модели вершины.

Последовательное поступление N сигналов с генератора 39 тактовых импульсов на вход сдвига регистра 3 сдвига обеспечивает подключение И моделей вершин.и, следовательно, осуществляется последовательный просмотр всех вершин исследуемого графа.

Очередной (N+1)-й сигнал сдвига с генератора 39 тактовых импульсов поступает на вход регистра 3 сдвига и обуславливает появление единичного сигнала на выходе последнего

1124 (0+1)-го разряда регистра, подключенного к полюсам 10 (входам 4) моделей вершин и полюсу 16 (входу) блока

2 управления.

Укаэанный сигнал, поданный на 5 полюс 11 модели вершин, проходит палее на первые входы элементов И 22 и 23 первой и третьей групп и вход элемента НЕ 31 ° В результате этого, коды весов редуцируемой и опрашивае,мой вершин .с регистров 26 и 27 поступают на сумматор 29, где суммируются, и далее код суммы весов вершин поступает на регистр 28 и затем в блок 35 индикации. Одновременно сигнал с выхода элемента НЕ 31 подается на второй вход элементов И 25 группы и блокирует поступление кода с регистра 28 на регистр 27. На третий вход элементов И 25 группы пода- 20 ется .сигнал с сумматора 29, который блокирует передачу кода из регистра

28 в регистр 27 при нулевой сумме в сумматоре.

Кроме того, сигнал с выхода последнего (N+1)-го разряда регистра 3 через полюс 16 блока 2 управления поступает на входы счетчика 38 циклов и элемента 40 задержки. Содержимое счетчика циклов увеличивается на единицу, и в запоминающем устройстве 36 выбирается очередная ячейка, в которой записан код номера следующей редуцируемой вершины.

Сигнал с выхода элемента 40 эа- .

3$ держки через полюс 18 (выход 2) блока 2 управления поступает на полюса

7 (входы 1) всех моделей вершин и далее в каждой модели на вход установки нуля регистра 26, устанавливая его в нулевое состояние.

Так завершается один цикл редукции. В результате его реализации осуществляется последовательный просмотр всех вершин графа, в регистрах 28 моделей вершин записаны коды их новых весов с учетом веса редуци318

8 руемой в этом цикле вершины и нали-. чия связей опрашиваемой вершины с редуцируемой. В счетчике 33 числа

)связей содержится код числа связей учитывающий число сворачиваемых связей в цикле редукции. Информация о весах вершин и числе связей редуцированного графа в данном цикле редукции отражается соответственно в бло-. ках 35 и 34 индикации.

Очередной тактовый сигнал с генератора 39 импульсов начинает новый цикл редукции. Эт т сигнал приводит в исходное состояние регистр 3 сдвига. В результате, сигнал на выходе (N+l)-го разряда становится нулевым.

Он поступает на входы элементов И 22 и 23 и элемента НЕ 31. Сигнал с выхода элемента НЕ 31 разблокирует элементы И 25 группы, и новый код веса данной вершины с регистра 28 переписывается в регистр 27. После этого осуществляется редукция очередной вершины графа, номер которой поступил в регистр 5 номера вершины графа из ячейки запоминающего устройства 36 через полюс 19 (выход 3) блока

2 управления. Дальнейшая последовательность операций соответствует рассмотренной.

Устройство позволяет управлять глубиной редукции по усмотрению пользователя. В конце последнего цик-. ла редукции сигнал подается на вход счетчика 38 циклов и переполняет его, появляясь на выходе переполнения (управляющем выходе), откуда он поступает на вход останова генератора тактовых импульсов. На этом работа схемы устройства прекращает-. ся. После окончания M циклов редукции рассматриваемый граф в соответствии с его топологией можно представить в виде числа независимых сегментов.

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

1124318

1124318

1124318

Составитель А. Колчин

Редактор Л. Алексеенко Техред А.Бабинец Корректор В.

Заказ 8282/39 Тиран 698 Подписное

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

113О35, Москва, Ж-.35, Раушская наб;, д. 4/5

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