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

1.1-V

113

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

Цель изобретения - снижение аппаратурных затрат путем сокращения группы счетчиков.

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

Устройство содержит группу элементов ИЛИ, группу триггеров 2, первую группу 3|-3 элементов И, блок 4 задания топологии графа, дифференцирующие элементы , первый элемент ИЛИ 6, регистр 7 сдвига,первую группу регистров (с, триггер 9, второй элемент ИЛИ 10, вход 11 установки в О устройства, первый элемент И 12, генератор 13 тактовых импульсов, второй элемейт И 14, распределитель 15 импульсов, элемент 16 задержки, вторую группу элементов И, вторую группу регистров , узлы индикации 19,-19 числ вершин, узлы индикации номеров вершин, счетчик 21.

Блок задания топологии графа содержит п одинаковых моделей вершин, каждая из которых содержит элементы И 22 и 23, элементы ИЛИ 24, эле- менты И 25-27, j-й вход 28 блока задания топологии, входы 29-32 j-й группы блока задания топологии, выход 33 блока задания топологии и элемент ИЛИ 34,

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

Перед началом работы по шине 11 на триггеры 2 ,,-2 и 9, регистр 7 сдвига, регистры 8,|-8|, распределитель 15 импульсов, который также представляет собой регистр сдвига.

счетчик 21 и регистры 18i-18 подает1 п

ся сигнал установки исходного состояния. При этом на нулевых выходах всех разрядов регистра 7 устанавливаются единичные потенциалы, которые вызывают появление единичного сигнала на выходе элемента И 14. Этот сигнал записывает единицу в первый разряд распределителя 15 и через элемент 16

0

5

0

5

0

5

задержки и элемент И.ПИ 1 задним фронтом переводит триггер 2 в единичное состояние. Единичный потенциал с выхода этого триггера поступает на вход первой вершины блока 4 задания топологии графа и появляется на выходе первой вершины и на выходах всех тех вершин, которые образуют множество связанных вершин. Через дифференцирующие элементы 5 -5 единичные импульсы с возбужденных выходов (вершин графа) блока 4 поступают через элементы ИЛИ 1j-1 на единичные вхо- 5 ды соответствующих триггеров , которые переходят в единичное состояние, фиксируют связанный подграф, Единичные импульсы с дифференцирующих элементов 5:,-5 записываются в соответствующие разряды сдвигающего регистра 7, а также регистра 8, так как в данный момент разрешающий потенциал имеется на первом выходе распределителя 15 и, кроме того, любой из этих импульсов через элемент ИЛИ 10 переводит триггер 9 в единичное состояние. При этом открывается элемент И 12 и тактовые импульсы с генератора 13 начинают поступать на сдвигающий вход регистра 7,

Каждый тактовый импульс сдвигает код регистра 7 на один разряд. При этом каждая единица с последнего разряда регистра 7 считывается в счетчик 21. Считывание происходит до тех пор, пока регистр 7 полностью не обнулится. Например, если в регистр 7 записан код 1001100, то два первых тактовых импульса записи в счетчик 21 не дают, третий и четвертый импульсы записывают две единицы, затем пятый и шестой импульсы состояние счетчика 21 также не изменяют и седьмой импульс записьтает третью единицу в счетчик 21. Это свидетельствует о том, что первый подграф состоит из трех связанных вершин, номера которых 1, 4 и 5 записаны в регистр 8,. При обнулении регистра 7 на его

нулевых выходах появляются единичные потенциалы, которые открывают элемен-. ты И 14, 17, , через которые содержимое счетчика 21 считыйается в регистр . Один тактовый импульс генератора 13„ пройдя через элемент И 14, записывает единицу во второй разряд распределителя 15 импульсов и тем самым разрешает запись в регистр 18 и регистр 8. Этот тактовый им3

пульс через элемент 16 задержки сбрсывает в О счетчик 21, а пройдя через элемент ИЛИ 6, перебрасывает триггер 9 в нулевое состояние, чем заблокируется на время прохождение тактовых импульсов на регистр 7, а через один из открытых элементов И 3,-3, устанавливает в единичное состояние тот из триггеров 2,-2 , которому предшествуют триггеры, установленные в единичное состояние ра- .нее.

В соответствии с приведенным выше примером в единичное состояние переводится триггер 2 , что позволяет выбрать новую вершину графа, не вошедшую в первый подграф, и аналогично описанному, возбудить все вершины,, образующие второй связанный подграф. При этом также происходит запись номеров вершин второго подграфа, но уже в регистр 8, В единичное состояние устанавливаются соответствующие триггеры , происходит запись кода в регистр 7 и через элемент РШИ 10 в единичное состояние устанавливается триггер 9. После этого начинается считьшание из регистра 7 в счетчик 21 числа вершин второго подграфа. После обнуления регистра 7 тактовый импульс передвигает единицу на третий выход распределителя 15 импульсов, а через элемент 16 задержки поступает на тот из непереведенных в единичное состояние триггеров 2,-2, который имеет минимальный индекс. Если все триггеры находятся в единичном состоянии, то этот- тактовый импульс появляется на выходе элемента И 3„,сигнал с которого останавливает работу устройства, заблокировав посредством элемента ИЛИ 6, триггера 9 и элемента И 12 прохождение тактовых импульсов на регистр 7, и подает сигнал разрешения на углы 19;,-19| и 20 20 индикации. При этом высвечиваются соответственно число вершин в каждом подграфе и их номера.

Блок задания топологии графа 4 позволяет передавать сигнал на выход всех связанных вершин при его наличии на входе хотя бы одной из них. Блок позволяет отображать топологию любого графа на п заданных вершинах. Для этого каждая верйина графа отображается элементом ИЛИ 34 с п-1 числом входов, элементами И 22 и 23 и эле416А94

ментом ИЛИ 24, а для отображения ребер, которые могут связывать любую вершину со всеми остальными,используется п-1 элемент И 25-27,

Если данная вершина участвует в графе, то на вход 29 необходимо подать единичный потенциал, если определенные ребра участвуют в графе, то

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

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

2Q 33 всех вершин. Б соответствии с описанным процессом работы устройства в регистре 18 фиксируются 4 вершины, которые высвечиваются на узле 19, индикации, а в регистре 8, фиксируются

25 номера вершин, которые высвечиваются на узле 20, индикации.

Структура блока задания топологии графа позволяет отображать любую топологию как ориентированных, так и

30 неориентированных графов, каждое ребро которых отображается парой встречно направленных ребер, соединяющих две вершины.

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

Устройство для определения числа вершин подграфов графа, содержащее генератор тактовых импульсов, группу

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

элементов И, выход первого элемента И

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

5, 13

к первому входу задания режима распределителя импульсов и к входу элемента задержки, выход которого подключен к первому входу, первого элемента ИЛИ, к первому входу первого элемента ИЛИ группы, к первым входам элементов И первой группы, к входам установки в О регистров первой группы, регистра сдвига, триггеров группы, к второму входу задания режима распределителя импульсов, к вто рому входу первого элемента ИЛИ и к входу установки в О устройства, i-й выход распределителя импульсов, где i 1, ..., k, подключен к первому входу i-ro элемента И второй группы и к входу чтения-записи i-ro регистра первой группы, выходы первого и второго элементов ИЛИ подключены соответственно к входу установки в О и к входу установки в 1 триггера, выход которого подключен к второму входу первого элемента И, выход j-ro элемента ИЛИ группы (j 1 , . .., п) подключен к входу установки в 1 j-ro триггера группы, выход j-ro триггера группы подключен к (j+1)-My входам элементов И с j-ro по п-й первой группы и к j-му входу блока задания топологии, выход 1-го элемента И первой группы, где 1 1,...,п--1|, подключен к первому входу (1+1)го элемента I-UDi группы, выход п-го элемента И первой группы подключен к третьему входу первого элемента ИЛИ и к управляющим входам

96

узлов индикации числа вершин и номеров вершин, j-H группа входов задания топологии графа устройства подключена к j-й группе входов блока задания топологии, j-й выход которого подключен к входу j-ro дифференцирующего элемента, выход которого подключен к информационным входам j-x разрядов регистров первой группЫд к информационному входу j-ro разряда регистра сдвига, к j-му входу второго элемента И.Ш и к второму входу элемента ИЛИ группы, выход j-ro

регистра первой группы подключен к информационному входу i-ro узла индикации номеров вершин, о т л и

чающееся

тем, что, с целью

снижения аппаратурных затрат, в устройство введены счетчик и вторая группа из k регистров 5 причем выход переноса регистра сдвига подключен к счетному входу счетчика,, i-й информационный выход которого подключен к второму входу элемента И второй группы, выход второго элемента И подключен к третьим входам элементов И второй группы, вход установки в О устройства подключен к входам установки в О счетчика и регистров второй группы, выход i-ro элемента И второй группы подключен к инфор- маизонному входу i-ro регистра второй группы , выход которого подключен к информационному, входу i-ro; узла индикации числа вершин.

Составитель В.Смирнов Редактор М.Дылын Техред М.Дидык Корректор А.Обручар

Заказ 4438/53 Тираж 672Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,

Фи.2

Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач, таких как выделение связанных подмножеств, при этом достигается сокращение аппаратурных затрат. Устройство содержит группу элементов ИЛИ 1. . .1,, группу триггеров 2. ..2,две группы элементов И 3 ...3, 17 ... 17 , блок 4 задания топологии, дифференцирующие элементы 5...5, элементы ИЛИ 6 и 10, регистр 7 сдвига, две группы регистров 8...8, 18, ... 18, , триггер 9, вход 11 установки в ноль, генератор 13 тактовых импульсов, два элемента И 12 и 14, распределитель 15 импульсов, элемент 16 задержки, узлы 19 ...19 индикации числа вершин, узлы 20 ...20 индикации номеров вершин, счетчик 21, где п - число вершин исследуемого графа, а k - число подграфов исследуемого графа. 2 ил. Ш 1(Л СА: д; ет со