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

 

Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач , таких как выделение связанных подмножеств, при этом достигается сокращение аппаратурных затрат. Устройство содержит группу элементов ИЛИ 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(Л СА: д; ет со

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

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

РЕСПУБЛИК (19) (11) (5D4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4066094/24-24 (22) 13.05.86 (46) 30,09.87. Бюл, Р 36 (71) Ленинградский электротехнический институт им. В.И,Ульянова (Ленина) (72) Т.В.Волченская, В.С.Князьков, В.С.Дудкин и Д.П.Пуолокайнен (53) 681.333 (088.8) (56) Авторское свидетельство СССР

У 656073, кл, G 06 F 15/36, 1976.

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

И 1101834е кл. G 06 F 15/20, 1982, (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА

ВЕРШИН ПОДГРАФОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для решения комбинаторных задач, таких как выделение связанных подмножеств, при этом достигается сокращение аппаратурных затрат, Устройство содержит группу элементов ИЛИ

1, ° ° .1, группу триггеров 2„...2„,две группы элементов И 3, ...3„, 17

17, блок 4 задания топологии, диффек 1 ренцирующие элементы 5 ...5, элементы ИЛИ 6 и 10, регистр 7 сдвига, две группы регистров 81...8, 18, ...18„,, триггер 9, вход 11 установки в ноль, генератор 13 тактовых импульсов, два элемента И 12 и 14, распределитель

15 импульсов, элемент 16 задержки, узлы 19 ...19„ индикации числа вер1 шин, узлы 20 ...20„ индикации номеров вершин, счетчик 21, где n — число вершин исследуемого графа, a k— число подграфов исследуемого графа.

2 ил.

1 134164

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

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

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

Устройство содержит группу 1,; -1„ элементов ИЛИ, группу триггеров 2,—

2„,- первую группу 3 -3„ элементов И, блок 4 задания топологии графа, дифференцирующие элементы 5,-5„, первый элемент ИЛИ 6, регистр 7 сдвига,первую группу регистров 8 -8, триггер

9, второй элемент ИЛИ 10, вход 11 установки в "0" устройства, первый элемент И 12, генератор 13 тактовых импульсов, второй элемент И 14, распределитель 15 импульсов,, элемент 16 задержки, вторую группу 17„ -17„ элементов И, вторую группу регистров

18,-18„, узлы индикации 19, -19 числа вершин, узлы индикации 20,-20 номеров вершин, счетчик 21 °

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

Перед началом работы по шине 11 на триггеры 2,„-2Ä и 9, регистр 7 сдвига, регистры 8,,-8, распределитель 15 импульсов, который также представляет собой регистр сдвига, счетчик 21 и регистры 18 -18. подаетн ся сигнал установки исходного состояния. При этом на нулевых выходах всех разрядов регистра 7 устанавливаются единичные потенциалы, которые

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

9 2 задержки и элемент ИЛИ 1 задним фрон1 том переводит триггер 2„ в единичное состояние, Единичный потенциал с вы— хода этого триггера поступает на вход первой вершины блока 4 задания топологии графа и появляется на выходе первой вершины и на выходах всех тех вершин, которые образуют множество связанных вершин, Через дифференцирующие элементы 5 -5 единичные им1 tl пульсы с возбужденных выходов (вершин графа) блока 4 поступают через элементы ИЛИ 11 -1„ на единичные входы соответствующих триггеров 2,-2„, которые переходят в единичное состояние, фиксируют связанный подграф, Единичные импульсы с дифференцирующих элементов 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 считывается в регистр 18, . Один тактовый импульс генератора 13„ прокдя через элемент И

14, записывает единицу во второй разряд распределителя 15 импульсов и тем самым разрешает запись в регистр

18 и регистр 8 . Этот тактовый им1341649 пульс через элемент 16 задержки сбрасывает в "0" счетчик 21, а пройдя через элемент ИЛИ 6, перебрасывает триггер 9 в нулевое состояние, чем заблокируется на время прохождение тактовых импульсов на регистр 7, а через один из открытых элементов И

3,"3„ устанавливает в единичное состояние тот из триггеров 2 -2 ко! И У торому предшествуют триггеры, установленные в единичное состояние ра,нее.

В соответствии с приведенным выше примером в единичное состояние переводится триггер 2, что позволяет выбрать новую вершину графа, не вошедшую в первый подграф, и аналогично описанному, возбудить все вершины,. образующие второй связанный подграф. При этом также происходит запись номеров вершин второго подграфа, но уже в регистр 8, В единичное состояние устанавливаются соответствующие триггеры 2,-2 „, происходит запись кода в регистр 7 и через элемент ИЛИ 10 в единичное состояние устанавливается триггер 9.

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

Блок позволяет отображать топологию любого графа на и заданных вершинах.

Для этого каждая верШина графа отображается элементом ИЛИ 34 с и-1 числом входов, элементами И 22 и 23 и элементом ИЛИ 24, а для отображения ребер, которые могут связывать любую вершину со всеми остальными, используется и-1 элемент И 25-27.

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

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

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

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

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

13416 9 к первому входу задания режима распределителя импульсов и к входу элемента задержки, выход которого подключен к первому входу первого элемента ИЛИ, к первому входу первого элемента ИЛИ группы, к первым входам элементов И первой группы, к вхо. дам установки н "0" регистров первой группы, регистра сдвига, триггеров группы, к второму входу задания режима распределителя импульсов, к вто рому входу первого элемента ИЛИ и к входу установки в 0 устройства, 1-й выход распределителя импульсов, где i = i, ..., k, подключен к первому входу i-го элемента И второй группы и к входу чтения-записи i-го регистра первой группы, выходы первого и второго элементов ИЛИ подключены соответственно к входу установки в "0" и к входу установки в 1 триггера, выход которого подключен к второму входу первого элемента И, выход j ãî элемента ИЛИ группы (j

1,..., и) подключен к входу установки н "1" j-го триггера группы, выход j-го триггера группы подключен к (j+1) му входам элементов И с j-го по п-й первой группы и к j-му входу блока задания топологии, выход 1-го элемента И первой группы, где 1

1,...,n-1, подключен к первому входу (1+1)-го элемента ИЛИ группы, выход и-го элемента И перной группы подключен к третьему входу первого элемента ИЛИ и к управляющим входам узлов индикации числа вершин и номеров вершин, j-я группа входов задания топологии графа устройства подключена к 1-й группе нходон блока. за5 дания топологии, j-й выход которого подключен к входу j-го дифференцирующего элемента, выход которого подключен к информационным входам j-x разрядов регистров первой группы, к информационному входу j-го разряда регистра сдвига., к j -му входу второго элемента ИЛИ и к второму входу

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

7 второму входу i-ro элемента И второй группы, выход второго элемента И подключен к третьим входам элементов И второй группы, вход установки н "0 устройства подключен к входам установки в 0" счетчика и регистров второй группы, выход i-ra элемента И второй группы подключен к информационному входу -го регистра

Второи х руппы Выхоц ко IopoI Î подключен к информ а ционному н хо—

35 ду 1-го узла индикации числа

BepUIHH, Составитель В.Смирнов

Редактор M.Äbëûí Техред M.Äèäûê Корректор А.Обручар

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

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

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

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