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

 

УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ХАРАКТЕРИСТИК ГРАФА, содержащее генератор тактовых импульсов, группу элементов ИЛИ, группу триггеров, нулевые входы которых объединены и соединены с входом установки исходного состояния устройства, первую и вторую группы элементов И, причем первый вход каждого элемента И первой группы соединен с единичным выходом соответствующего триггера группы, выход i-ro элемента И первой группы (, п-1. где п - число элементов в группе, равное числу вершин в графе) соединен с первым входом (i+1)-ro элемента ИЛИ группы, блок задания топологии графа, содержащий п моделей вершин (п равно числу вершин исследуемого графа), распределитель импульсов, группу счетчиков числа вершин, группу дифференцирующих элементов, элемент задержки , отличающееся тем, что, с целью расширения функциональных возможностей устройства путем обеспечения определения характеристик ориентированных и неориентированных графов любой степени связности, в устройство введены первый и второй элементы ИЛИ, триггер, первый и второй элементы И, регистр сдвига , группа из К (К - число подграфов графа) регистров номеров вершин, узлы индикации числа вершин и узлы индикации номеров вершин, каждая модель вершины содержит два элемента ИЛИ и пять элементов И, причем выход каждого элемента ИЛИ группы соединен с единичным входом соответствующего триггера группы , единичный выход каждого i-ro триггера группы () соединен с i-M входом блока задания топологии графа и входами (i+1)-ro, (i+2)-ro ..., n-го элементов И первой группы, каждый выход блока задания топологии графа через дифференцирующий элес мент группы соединен с соответствующими информационными входами всех сл регистров номеров вершин группы, соответствующим разрядом регистра сдвига, вторым входом соответствующего элемента ИЛИ группы и соответствующим входом первого элемента ИЛИ, выход которого подключен к единичному входу триггера, нулевой вход :которого соединен с выходом второго элемента ИЛИ, первый вход которого подключен к выходу п-го элемента И первой группы, а второй вход - к входу установки исходного состояния устройства, единичный выход 00 00 триггера соединен с первым входом первого элемента И, второй вход которого соединен с первым входом второго элемента И и подключен к выходу генератора тактовглх импульсов, выход первого элемента И соединен со сдвигающим входом регистра сдвига,, нулевые выходы разрядов которого соединены с вторым, третьим, ,, . , (п+1)-м входами второго элемента И, выход которого подключен к входу распределителя импульсов и через элемент задержки - к третьему входу второго элемента ИЛИ, первому входу первого элемента ИЛИ группы и объеди

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

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

РЕСПУБЛИН (19) (11) 3(51) б 06 F 15 20

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

И ABTOPCXOMV СВИДЕТЕЛЬСТВУ

) 1

ЙЖ .

»»» «„,»

»«» »«»ыг.—.»»

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3509874/18-24 (22) 04. 11. 82 (46) 07. 07. 84. Вюп. Р 25 (72) В.М. Глушань, В.M. Курейчик, Л.И. Щербаков, Ю. E. Шведенко и В. Н. Гуров .(71) Таганрогский радиотехнический институт им. В.Д.Калмыкова (53) 681. 833(088. 8) ,(56) 1. Авторское свидетельство СССР

9 б 37822, кл. Gj 06 F 15/20, 1976, 2. Авторское свидетельство СССР

Р 656073, кл. Cj 06 F 15/36, 1976 (прототип) . (54) (57) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

ХАРАКТЕРИСТИК ГРАФА, содержащее генератор тактовых импульсов, группу элементов ИЛИ, группу триггеров, нулевые входы которых объединены и соединены с входом установки исходного состояния устройства, первую и вторую группы элементов И, причем первый вход каждого элемента

И первой группы соединен с единичным выходом соответствующего триггера группы, выход i-го элемента И первой группы (i-=1, п-1. где n — число элементов в группе, равное числу вершин в графе } соединен с первым входом (i+1)-го элемента ИЛИ группы, блок задания топологии графа, содержащий и моделей вершин (п равно числу вершин исследуемого графа), распределитель импульсов, группу счетчиков числа вершин, группу дифференцирующих элементов, элемент задержки, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем обеспечения определения характеристик ориентированных и неориентированных графов любой степени связ ности, в устройство введены первый и второй элементы ИЛИ, триггер, первый и второй элементы И, регистр сдвиra, группа из К (К вЂ” число подграфов графа) регистров номеров вершин, узлы индикации числа вершин и узлы индикации номеров вершин, каждая модель вершины содержит два элемента ИЛИ и пять элементов И, причем выход каждого элемента ИЛИ группы соединен с единичным входом соответствующего триггера груп" пы, единичный выход каждого i-го триггера группы (i =1,n) соединен с

i-м входом блока задания топологии графа и входами (i+1)-го. (i+2)-ro и-го элементов И первой группы, каждый выход блока задания топологии графа через дифференцирующий элемент группы соединен с соответствующими информационными входами всех регистров номеров вершин группы, соответствующим разрядом регистра сдвига, вторым входом соответствующего элемента ИЛИ группы и соответствующим входом первого элемента ИЛИ, выход которого подключен к единичному входу триггера, нулевой вход которого соединен с выходом второго элемента ИЛИ, первый вход которого подключен к выходу и-го элемента И первой группы, а второй вход - к входу установки исходного состояния устройства, единичный выход триггера соединен с первым входом первого элемента И, второй вход которого соединен с первым входом второго элемента И и подключен к выходу генератора тактовых импульсов, выход первого элемента И соединен со сдвигающим входом регистра сдвига,, нулевые выходы разрядов которого соединены с вторым, третьим, (и+1)-м входами второго элемента И, выход которого подключен к входу распределителя импульсов и через элемент з адержки — к третьему входу второго элемента ИЛИ, первому входу первого элемента ИЛИ группы и объеди1101834 ненным вторым, третьим, ..., n-u входам соответствующих элементов И первой группы, каждый выход распределителя импульсов соединен с управляющим входом соответствующего регистра номеров вершин группы и с первым входом соответствующего элемента И второй группы, вторые входы которых объединены и подключены к выходу регистра сдвига, выходы элементов И второй группы соединены с входами соответствующих счетчиков числа вершин группы, информационные выходы счетчиков числа вершин группы и информационные выходы регистров номеров вершин группы соединены с входами соответствующих узлов индикации числа вершин и узлов индикации номеров вершин, управляю" щие входы которых объединены и подключены к выходу n-ro элемента И первой группы, а входы установки в нуль счетчиков числа вершин группы и регистров номеров вершин группы объединены и соединены с входом установки исходного состояния устройства, входы первого элемента ИЛИ каждой модели вершины соединены с выходами третьих элементов И всех

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

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

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

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

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

1101834

Указанная цель достигается тем,что в устройство, содержащее генератор тактовых импульсов, груп.-.у элементов ИЛИ, группу триггеров, нулевые входы которых объединены и соединены с входом установки исходного состояния устройства, первую и вторую группы элементов И, причем первый вход каждого элемента И первой группы соединен с единичным выходом соответствующего триггера 10 группы, выход i-ro элемента И. первой группы (i =1, r.— 1, где n — число элементов в группе, равное числу вершин в графе) соединен с первым входом (i+1)-го элемента ИЛИ группы, 15 блок задания топологии графа, содЕржащий и моделей вершин L,n равно числу вершин исследуемого графа), распределитель импульсов, группу счетчиков числа вершин, 20 группу дифференцирующих элементов, элемент задержки, введены первый и второй элементы ИЛИ, триггер, первый и второй элементы И, регистр сдвига, группа из К (К вЂ” число подграфов графа) регистров номеров вершин, узлы индикации числа вершин и узлы индикации номеров вершин, каждая модель вершины содержит два элемента ИЛИ и пять элементов И, причем выход каждого элемента ИЛИ группы соединен с единичным входом соответствующего триггера группы, единичный выход каждого i-го триггера группы (1=l,n) соединен с i-м входом блока задания топологии графа и входами (i+1)-го, (i+2)-ro, ...,и-гo элементов И первой группы, каждый выход блока задания топологии графа через дифференцирующий элемент группы соединен с соответствующими 40 информационными входами всех регистров номеров вершин группы, соответствующим разрядом регистра сдвига, вторым входом соответствующего элемента ИЛИ группы и соответствующим 45 входом первого элемента ИЛИ, выход которого подключен к единичному входу триггера, нулевой вход которого соединен с выходом второго элемента ИЛИ, первый вход которого подключен к выходу и-го элемента И первой группы, а второй вход — к входу установки исходного состояния устройства, единичный выход триггера соединен с первым входом первого элемента И, второй вход которого соединен с первым входом второго элемента И и подключен к выходу генератора тактовых импульсов, выход первого элемента И соединен со сдвигающим входом регистра сдвига нулевые выходы60 разрядов которого соединены с вторым, третьим, ..., (n+1)-м входами второго элемента И, выход которого подключен к входу распределителя им vïü о ы чеоез элемент задержки — 65 к третьему входу второго элемента

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

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

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

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

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

Устройство состоит из группы

1, -1 элементов ИЛИ, группы триггеров 2, -2р, группы 3«элемен1101834 тов И, блока 4 задания топологии графа, группы 5! -5q дифференцирующих элементов, элемента ИЛИ 6, регистра 7 сдвига, группы регистров

8 -8» номеров вершин, триггера 9, элемента ИЛИ 10, шины 11 установки исходного состояния, элемента И 12, генератора 13 тактовых импульсов, элемента И 14, распределителя 15 импульсов, элемента 16 задержки, группы 17„-17» элементов И, группы счетчиков 18,-18» числа вершин, узлов индикации 19 -19» числа вершин, узлов индикации 20 -20» номеров вершин.

Блок задания топологии графа (фиг.2) содержит N одинаковых моделей вершин, каждая из которых содержит элемент ИЛИ 21, элементы И 22 и 23, элемент ИЛИ 24, элементы И 25—

27, вход 28 задания топологии графа устройства, вход 29 блока задания топологии графа, входы 30-32 задания топологии графа устройства, выход 33 блока задания топологии графа.

Для з адания топологии графа, например согласно фиг. 3, необходимо подат ь еди ни ч ные и оте нци алы н а входы 28, 30 „31 и 32 всех моделей вершин графа так, как это показано на фиг.2.!

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

35 представляет собой регистр сдвига, и счетчики 18„-18» подается сигнал установки исходного состояния. При этом на нулевых выходах всех разря-. дов регистра 7 устанавливаются еди- 40 ничные потенциалы, которые вызывают появление единичного сигнала на выходе элемента И 14. Этот сигнал записывает единицу в первый разряд распределителя 15 и через элемент 16 задержки и элемент ИЛИ 11 задним фронтом переводит триггер 2 в единичное состояние. Единичный потенциал с выхода этого триггера поступает на вход первой вершины блока 4 задания топологии графа и появляется на выходе первой вершины и на выходах всех тех вершин, которые образуют множество связанных вершин. Через дифференцирующие элементы 5, -5q единичные импульсы с возбужденных выходов (вершин графа) блока 4 поступают через элементы ИЛИ 1,-1 на единичные входы соответствующих триггеров 2 -2д, которые, переходя в единичное состояние., фиксируют 60 связный подграф. Единичные импульсы с дифференцирующих элементов

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

И 12 и тактовые импульсы с генератора 13 начинают поступать на сдвигающий вход регистра 7.

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

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

1, 4 и 5 записаны в регистр 8 .

При обнулении регистра 7 íà его нулевых выходах появляются единичные потенциалы, которые открывают элемент И 14. Один тактовый импульс генератора 13, пройдя через элемент

И 14, записывает единицу во второй разряд распределителя 15 импульсов и тем самым разрешает запись в счетчик 18 и регистр 8 . Этот тактовый импульс через элемент 16 задержки и элемент ИЛИ 10 перебрасывает триггер 9 в нулевое состояние, чем заблокируется на время прохождения тактовых импульсов на регистр 7, а через один из открытых элементов И 3 -3, устанавливает в единичное состояние тот из триггеров 2q-2д, которому предшествуют триггеры, установленные в единичное состояние ранее.

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

1101834 регистра 7 тактовый импульс передвигает единицу на третий выход распределителя 15 импульсов, а через элемент 16 задержки поступает на

toT из непереведенных в единичное состояние триггеров 2 -2, который имеет минимальный индекс. Если все триггеры находятся в единичном состоянии, то этот тактовый импульс появляется на выходе элемента 3>, сигнал с которого останавливает работу устройства, заблокировав посредством элемента HJIH 10, триггера 9 и элемента И 12 прохождение тактовых импульсов на регистр 7, и подает сигнал разрешения на узлы индикации19 -19 и 20 -20 . При этом высвечиваются соответственно число вершин в каждом подграфе и их номера.

Блок задания топологии графа 4 позволяет передавать сигнап на выход всех связанных вершин при его наличии на входе хотя бы одной из них.

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

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

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

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

Единичные потенциалы подаются на те входы 28, 30, 31, 32 вершин, которые позволяют отобРазить граф, представленный для примера на фиг. 3.

Благодаря этому, при подаче на вход 29 одной из вершин единичного потенциала он появляется на выходах

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

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

1101834

Сост авит ель С. Н аз аров

Техред А. Бабинец

Корректор О.Тигор

Редактор В.Иванова

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

Заказ 4769/33 Тираж 699 Подписное

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

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