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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (sr)s G 06 F 15/419 гОсудАРстВенНОе пАтентнОе

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4905057/24 (22) 24,01,93. (46) 23.01.93. Бюл. М 3 (71) Институт проблем моделирования в энергетике AH УССР (72) О.Н, Голованова, E.A. Ралдугин и В.Д.

Бакуменко (56) Авторское свидетельство СССР

М 907552, кл. G 06 F 15/20, 1980. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к вычислитель= ной технике и может быть использовано для исследования графов и решения задач в граИзобретение относится к специализированным вычислительным устройствам и может быть использовано для исследования рафов и решения задач в графовой постановке.

Известна модель узла для исследования графа, содержащая сдвиговые регистры, триггеры, элементы И, ИЛИ. Модель может использоваться в устройствах для исследования неориентированных графов.

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

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

5U» 1789995 А1 фовой постановке. Цель изобретения — расширение функциональных воэможностей за счет осуществления поиска в ширину. Устройство содержит блок управления перебором вершин и группу моделей вершин. Блок управления перебором вершин содержит генератор импульсов, блок формирования сигналов управления, первый и второй счетчики импульсов, триггер, первый и второй элементы И, пять элементов ИЛИ, блок элементов ИЛИ. Модель вершины содеожит регистр сдвига, четыре триггера, шесть элементов И, два элемента ИЛИ, блок weментов И, 3 ил. подключен к выходу опроса блока управления перебором вершин, выход сигнала реверса, первый выход сигнала сдвига, вход осведомительного сигнала и информационный вход которого подключены соответственно к группе входов реверса, к первой группе входов сдвига, к группе осведомительных выходов и, к группе информационных выходов моделей вершин группы, а вход управления пуском блока управления перебором вершин является входом пуска устройства, причем каждая модель вершины группы содержит первый и второй регистры сдвига, триггер, первый, второй, третий и четвертый элементы И, элемент

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

1789995 сдвига, входы реверса и сдвига второго регистра сдвига являются соответственно входами реверса и сдвига модели, первый вход четвертого элемента И подключен к выходу триггера, второй выход сигнала сдвига бло- б ка управления перебором вершин подключен ко второй группе входов сдвига моделей вершин группы, группы входов задания начальной Ъершийы и заданйя кода номера вершины которой являются соответственно первой„и второй группами входов задания устройства, а выход сигнала опроса последней модели вершины группы является выходом устройства. причем дополнительно введены в каждую модель вершины первый и второй элементы НЕ, блок элементов И, выход которого является информационным выходом модели; первый вход — входом задания кода номера вершины, а второй вход подключен к выходу младшего разряда вто- 0 рого регистра сдвига, вход записи которого подключен ко второму входу элемента ИЛИ и является входом задания начальной вершины модели, а вход управленйя записью подключен к выходу четвертого элемента И, 5 второй вход которого подключен к выходу третьеГо элемента И, выход элемента ИЛИ подключен к установочному входу триггера, выход которого подключен ко второму входу первого элемента И, выход которого под- ЗО ключен к входам соответственно первого и второго элементов НЕ, выход первого из которых является осведомительным выходом модели, а выход второго подключен ко второму входу второго элемента И, выход З5 которого является выходом сйгнала опроса модели, вторым входом сдвига которой является вход первого регистра сдвига, э блок управления перебором вершин содержит блок формирования сигналов управления, 40 первый и второй элементы И, элемент ИЛИ, первый и второй счетчики импульсов, триггер, генератор импульсов, выход которого подключен соответственно к первым входам первого и второго элементов И, вторые 45 входы которых подключены соответственно к прямому и обратному-выходам триггера, выход второго элемента И подключен к входу запуска блока формирования сигналов Д управления, а выход первого элемента и 0 является вторым выходом сигнала сдвига блока и подключен к входу вычитания первого счетчика ймпульсов и ко входу второго счетчика импульсов, выход которого подключен к первому входу элемента ИЛИ, вы- 55 ход которого подключен к установочному входу триггера, второй вход является входом управления пуском блока, а третий вход подключен к выходу первого счетчика импульсов, установочный вход которого подключен к информационному входу блока формирования сигналов управления и является информационным входом блока, а вход стробирования подключен к тактовому выходу блока формирования сигналов управления, выход сброса которого подключен к входу сброса триггера, а выходы опроса, реверса, сдвига и осведомительный вход являются соответственно выходами сигнала

îпроса, сигнала реверса, первым выходом сигнала сдвига и входом осведомительного сигнала блока.

Недостаток устройства — отсутствие возможности осуществления поиска в ширину.

Цель изобретения — расширение класса решаемых задач за счет осуществления процедуры поиска в ширину.

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

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

1789995

50

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

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

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

35 которого являются соответственно выходом стробирования и информационным выходом блока управления перебором вершин, второй выход поиска, выход выделения, выход продолжения поиска, группы входов вторых и третьих осведомительных сигналов, группа входов стробирующих сигналов которого подключены соответственно к входу второго сигнала опроса первой модели вершины входам начала поиска, входам продолжения поиска, выходам вторых и третьих осведомительных сигналов, выходам стробирующих сигналов моделей вершин группы, причем каждая модель вершины группы содержит второй, третий и четвертый триггеры, пятый и шестой элементы И, второй элемент ИЛИ, первый и второй входы которого подключены соответственно к выходу пятого элемента И и к выходу шестого элемента И. к установочному входу четвертого триггера, к третьему входу первого элемента ИЛИ, выход которого подключен к второму входу блока элементов И и является выходом стробирующего сигнала модели, а также к входу сброса второго триггера, выход которого является выходом третьего осведомительного сигнала модели, а установочный вход подключен к выходу первого элемента И, к установочным входам третьего триггера и первого триггера. выход которого является выходом второго осведомительного сигнала модели, вход начала поиска и вход второго сигнала опроса которой подключены соответственно к гретьему входу первого элемента И модели и к первым входам пятого и шестого элементов И модели, вторые входы которых подкл юче н ы соответственно к прямому и обратному выходам третьего триггера, вход сброса которого подключен к выходу второго элемента ИЛИ и является выходо второго сигнала опроса модели, первый в%од четвертого элемента И является входом продолжения поиска модели, второй вход подключен к первому входу второго элемента И, а выход — к входу сброса четвертого триггера; прямой выход которого подключен к второму входу второго элемента И, а обратный выход — к второму входу третьего элемента И и является выходом первого осведомительного сигнала модели, На фиг. 1 представлена функциональная схема устройства для исследования графа; на фиг. 2 — пример исследуемого графа; на фиг. 3 — блок-схема алгоритма функционирования устройства, Устройство содержит блок 1 управления перебором вершин и модель 2 вершины, повторенный В раз ( — число вершин в графе). Здесь и далее цифрами в скобках, 1789995

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

В каждую модель 2 вершины входят регистр

3 сдвига, триггеры 4 — 7, элементы 8 — 13 И, блок 14 элементов И, элементы 15, 16 ИЛИ.

Элементы И блока 14 моделей 2 вершйн образуют матрицу из В х М элементов, остальные элементы этих моделей образуют

15 группы из В элементов, Блок 1 управления перебором вершин включает генератор 17импульсов, блокформирования сигналов управления 18, счетчики 19, 20 импульсов, триггер 21, элементы И устройства, В групп входов 31 задания кода номера вершины графа ( — число вершин в графе, М=!о92В), выходы 32, 33 соответственно первого и второго сигналов опроса моделей 2 вершины, входы 34, 35 соответственно первого и второго сигналов опроса моделей 2 вершины, вход 36 начала поиска, 30 группа из В входов 37 начальной выборки модели, с которой начинается. процедура поиска в ширину, вход 40 продолжения поиска, группа из В выходов 38, 39, 41 осведомительных сигналов, группа из В выходов

43 стробирующих сигналов, вход 42 сдвига устройства, В групп из M информационных выходов 44 моделей вершин, передающих

M-разрядные коды вершин в блок 1, группа из M информационных выходов 45 устройства, выход 46 стробирования, Блок 1 и В моделей 2 вершин образуют

40 однородную моделирующую структуру. Полюсы 36, 40, 42 являются общими для всех

В моделей 2 вершин. Полюсы 32(В) и 33(В) используются при добавлении новых моде- 45 лей 2 вершин (расширении устройства).

Регистр 3 сдвига является кольцевым с числом разрядов (В+1) и предназначен для хранейия информации о связях данной вер50 шины с другими вершинами графа. Блок 14 элементов И исйользуется для выдачи в блок 1 кода (номера) вершины, установленного на входах 31 задания кода номера вершины. Установка кода осуществляется однократно предварительной подачей на соответствующие входы блока 14 логического нуля или единицы.

Счетчик 19 импульсов предназначен для формирования временного интервала с момента начала отсчета импульсов и до мо22, 23, элементы 24 — 28 ИЛИ, блок 29 эле- 20 ментов ИЛИ. Кроме этого, на фиг. 1 цифровые обозначения имеют вход 30 пуска мента обнуления (работает на вычитание) в зависимости от кода, занесенного в него через информационные входы до начала счета. Счетчик 20 импульсов используется для восстановления исходного состояния информации, записанной в регистры 3 сдвига.

Устройство работает следующим образом.

Пусть необходимо сформировать список вершин графа, начиная с заданной, в порядке, определяемом процедурой поиска в ширину (ППШ) на графе, структура которого представлена на фиг, 2. Зададим в качестве начальной вершину с номером 1.

Перед начало работы в регистры 3 сдвига заносится информация о структуре связей в графе (матрица смежности). Триггеры

4-7устанавливаются в исходное нулевое состояние. Блок формирования сигналов управления 18 в исходном состоянии не вырабатывает никаких сигналов на своих выходах (1)-(б), Сигналом "Пуск" на полюсе 30 запускается генератор 17 импульсов, а через элемент 28 Mill блока 1 устанавливается в единицу триггер 21 блока 1, который своим единичным выходом открывает элемент 23

И, Одновременно с этим сигнал "Пуск" поступает на полюс 37(1) модели 2(1) вершины, который выбран в качестве начального и через элемент 16(1) ИЛИ поступает на вход

43(1), а также открывает блок 14 элементов

И, с выходов которых на первые входы блока

29 элементов ИЛИ передается двоичный код номера выбранной модели. С выходов блока 29 элементов ИЛИ код номера узла поступает на информационные входы счетчика 19 импульсов, Под действием сигнала на стробирующем входе, поступающем с выхода элемента 27 ИЛИ, в счетчик 19 заносится двоичный код номера узла 1, Тактовые импульсы генератора 17 через элемент 23 И поступают на вход (4) блока формирования сигналов управления 18, под действием которых блок 18 начинает формировать сигналы управления. По сигналу на.выходе (2) этого блока триггер 21 перейдет в нулевое состояние, при этом элемент 23 И закроется, а элемент 22 И откроется. Отсчитав один импульс, счетчик 19 сформирует сигнал обнуления, который через элемент 28 ИЛИ блока 1 переведет триггер 21 в единицу. На полюс 42 (вход сдвига) устройства поступит один импульс, который одновременно сдвинет все регистры 3 на один разряд. В регистрах 3 моделей (2), (3) и (4) на выходе сформируется сигнал единицы, Переключение триггера 21 в единицу продолжит работу блока 18: на выходе (5) формируется

1789995 сигнал выделения, подаваемый на полюс 36 устройства, Этот сигнал пройдет через элемент 10 И (дешифратор адреса) в моделях 2 вершины с номерами (2), (3) и (4), так как только в этих моделях в данный момент на выходе регистров 3 сформирован сигнал единицы. В тех же моделях триггеры 4, 5 и

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

Затем формируется сигнал "Поиск" на выходе (4) блока 18, который поступает на полюс 35(1). Путь прохождения этого сигнала через модели 2 вершин зависит от состояния триггера 4: если триггер 4 в "0", то

" сигнал "Поиск" проходит через элементы 8

И, 15 ИЛИ на полюс 32 и далее на полюс 35 следующей в цепи модели вершины; если триггер 4 в "1" — через элементы 9 И, 15 ИЛИ на полюс 32; устанавливает в "1" триггер 7, а также подается на вход элементы 16 ИЛИ, с выхода которого поступает на нулевой вход триггера 6 и íà входы блока 14 элементов И, разрешая передачу в блок 1 и на полюсы 45 кода номера данной вершины, установленного на полюсах 31, а также через полюс 43 и элемент 27 ИЛИ блока 1 на стробирующий вход счетчика 19 импульсов.

В исследуемом иллюстративном графе по сигналу "Поиск" на информационные выходы 45 устройства будут переданы коды номеров вершин первого уровня (2), (3) и (4), и в этих моделях 2 вершин триггеры 7 будут переэедены в "1".

Затем триггер 21 снова переводится в чулевое состояние и импульсы генератора

17 вновь поступают на входы счетчиков 19, 20 и HG полюс 42 сдвига устройства с целью восстановления исходного состояния регистров 3, Одновременно сигнал "Поиск" распространяется по цепи, образованной последовательным соединением полюсов

32 и 35. Сигнал переполнения счетчика 20 переводит триггер 21 в "1", и работа блока

18 продолжается, Анализируется уровень сигнала на входе (2) блока 18. Нулевой сигнал на этом входе означает, что передача кодов номеров вершин первого уровня (2), (3), (4) в блок 1 закончена. блок 18 опрашивает свой вход (2) до появления на.нем сигнала нулевого уровня, что произойдет тогда, когда все триггеры будут переведены в "0", т.е. все вершины первого уровня просмотрены. Затем анализируется сигнал на входе (1) блока 18: если

"0", то все вершины графа просмотрены (все триггеры 5 уже установлены в "1" и их "0" выходы сформируют на выходе элемента 24

ИЛИ нулевой. сигнал) и процесс поиска за5

55 вершен. Если на входе (1) сигнал равен "1", то на выходе (3) блока 18 устанавливается единичный потенциал, который поступает на полюс 34(1).

С помощью этого сигнала отыскивается первая (с наименьшим номером) вершина из множества вершин (2), (3), (4) от которых теперь продолжается поиск вершин второго уровня. Путь прохождения потенциала с по-, люса 34(1) через модели 2 вершин зависит от состояния триггера 7: если триггер 7 в "0", то сигнал через элемент 12 И поступает на полюс 33 и далее к следующей модели, если триггер 7 в "1", то сигнал. к следующей модели не проходит, а через элементы 13 И, 16

ИЛИ поступает в блок 14 и передает в блок

1 код номера вершины первого уровня (в нашем примере вершина (2)), от которой продолжается поиск вершин следующего (второго) уровня.

Затем начинается новый цикл сдвига регистров 3, Через два импульса выходным сигналом счетчика 19 будет восстановлена

"1" состояние триггера 21 и блок 18 сформирует сигнал выделения на своем выходе (5).

Вершина (3) уже просматривалась ранее и ее элемент 10 И закрыт "0" выходом триггера 5. После этого сигнал нэ выходе (6) блока

18 через общий полюс 40 поступит на все модели 2 вершин на вход элементов 11. В модели 2 вершины (1) он подтвердит "0" состояние триггера 7(1), пройдя через элемент 11(1). С выхода элемента 11(2) сигнал, поданный на общий полюс 40 устройства, переведет в "0" триггер 7(2), Это откроет элемент 12(2) и единичный потенциал с полюса 33(2) перейдет к элементам И 11(3) и

12(3) следующей в цепи модели 2(3) вершины, где будет оставлен, так как и его триггер

7(3) стоит в "1" (вершина (3) входит в подмножество вершин первого уровня). Через элемент 13(3) И и 16(3) ИЛИ пришедший единичный потенциал передаст в счетчик 19 импульсов блока 1 управления код номера вершины (3).

Затем блок 18 переводит триггер 21 в

"0" и организует как и ранее регенерацию регистров 3. Выходной сигнал счетчика 20 восстанавливает "1" состояние триггера 21 и опрашивается на входе (3) блока 18. Так как триггер 7(3) вершины (3) еще сохраняет состояние "1", то сигнал на входе (3) блока

18 равен 1. Начинается сдвиг регистров 3, Через три импульса сдвига выходной сигнал счетчика 19 переводит триггер 21 в "1", 3атем вырабатывается сигнал выделения на полюсе 36, который выделит в подмножество второго уровня вершину (6), связанную с вершиной (3) первого уровня. После этого

1789995

12 цепочка действий: подача сигнала на полюс

40 и сброс триггера 7/3 в "0", регенерация регистров 3, выявление единичного сигнала на входе (3) блока 18; запись кода номера вершины (4) в счетчик 19, сдвиг регистров 3 на четыре разряда и подача сигнала на полюс 36 — приведет к выделению в подмно>кество второго уровня вершины (5), связанной с вершиной (4). Вершина (6), тоже связанная с вершиной (4), не выделяется, т.к. она уже была выделена в процессе поиска от вершины (3). После этого блок 18 формирует сигнал на выходе (6), который переведет в "0" триггер 7(4). Анализ сигнала на входе (3) блока 18 покажет, что триггеров

7, имеющих состояние "1", больше нет. Теперь устройство выдает коды номеров вершин второго уровня, Для этого блок 1 переводит в "0" сигнал на полюсе 34(1) и подает импульсный сигнал на полюс 35(1).

Под его действием на информационные выходы 45 устройства будут переданы коды номеров вершин, у которых триггеры 4 находятся в "1", т,е. (5), (6), (8), (9). После перевода в "0" триггера 6{9) сигнал на входе (2) блока 18 станет нулевым, что свидетельствует об окончании выдачи кодов номеров вершин второго уровня на выходы 45 устройства. Так как еще есть непросмотренные вершины (7), (10), то сигнал на входе (1) блока 18 равен "1". Поэтому процедура поиска продолжается. При этом в качестве исходных для продолжения поиска выступают вершины второго уровня (5), (6), (8), (9). Поиск вершин третьего уровня (7) и (10) начинается с формирования на полюсе 34(1) единичного потенциала. Дальнейшие действия аналогичны. После выдачи номерОв кодов вершин (7) и (10) все триггеры 5 окажутся в "1". Эту ситуацию характеризует сигнал "0" на входе (1) блока 18, после выявления которого на одном из этапов алгоритма устройство остановит решение. Таким образом, в ходе описанной процедуры для иллюстративного графа на выходы 45 будет выданы коды номеров вершин в такой последовательности: (1), (2), (3), (4), (5), (6), (8), (9), (10), причем появление кода номера верШины на полюсах 45 Сопрово>кдается импульсом синхронизации на полюсе 46, На фиг, 3 представлена блок-схема алгоритма функционирования устройства для исследования графа, реализующего процедуру поиска в ширину на графе.

5 Начало — инициализация устройства и формирование сигнала пуска.

Блок 47 — запись кода номера начальной вершины в счетчик 19 блока 1 управления.

Блок 48 — сдвиг информации в кольце10 вых регистрах 3, Блок 49 — подача сигнала, выделения вершин 1-го уровня на полюс 36.

Блок 50 — подача сигнала на полюс 35(1) и формирования кодов номеров вершин 1-го

15 уровня на выходных полюсах 45, Блок 51 — восстановление (регенерация) информации в регистрах 3.

Блок 52- проверка состояния триггеров

6 (сигнал на входе (2) блока 18.

20 Блок 53 — проверка состояния триггеров

5 (сигнал на входе (1) блока 18).

Блок 54 — подача потенциала "1" на полюс 34(1) для записи в счетчик 19 блока 1. управления кода номера текущей вершины

25 1-го уровня, с которой продолжается поиск вершин (i+1) уровня.

Блок 55 — сдвиг информации в кольцевых регистрах 3, Блок 56 — подача сигнала выделения

30 вершин (i+1) уровня, связанных с текущей вершиной i-го уровня (полюс 36), Блок 57 — подача сигнала (полюс 40 записи в счетчик 19 блока 1 управления кода номера следующей (текущей) вершины. I-го

35 уровня и регенерация регистров 3.

Блок 58 — проверка наличия ewe не использованных вершин 1-го уровня для отыскания вершин (i+1) уровня: анели; состояния триггеров 7;

40 Блок 59 — снять сигналы с полюса 34(1) — установить потенциал "0".

Блок 60 — подача сигнала на полюс 35(1) и формирование кодов номеров вершим (i+1) уровня.

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

Формула изобретения

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

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

1789995

16 четвертого элемента И является входом продолжения поиска модели, второй вход подключен к первому входу второго элемента и, а выход — к входу сброса четвертого триггера, прямой выход которого подключен к второму входу второго элемента и, а обратный выход — к второму входу третьего элемента И и является выходом первого осведомительного сигнала модели, а в блок управления перебором вершин дополнительно: введены второй, третий, четвертый и пятый элементы ИЛИ, блок элементов

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

1789995

ЯРф7уд, .

1 ф

L фиг 2

4u z

Составитель О.Голованова

Техред М.Моргентал Корректор М.Шароши

Редактор Л.Пигина

Заказ 350 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г, Ужгород. ул.Гагарина, 101