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

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

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

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

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

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

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

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

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

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

Целью изобретения является расширение функциональных возможностей устройства путем обеспечения определения характеристик ориентированных и неориентированных графов любо степени связности. Указанная цель достигается тем,что в устройство, содержащее ге нератор тактовых импульсов, группу элементов ИЛИ, группу триггеров, нулевые входы которых объединены и соединены с входом установки исходного состояния устройства, первую и вторую группы элементов И, причем первый вход каждого элемента И первой группы соединен с единичным выходом соответствующего триггера группы, выход i-ro элемента И. первой группы (1-1, п-1, где п - число элементов в группе, равное числу вершин в графе) соединен с первым входом (i-t-l)-ro элемента ИЛИ группы блок задания топологии графа, содер жащий п моделей вершин 1,п равно числу вершин исследуемого графа), распределитель импульсов, группу счетчиков числа вершин, группу дифференциругадих элементов, элемент задержки, введены первый и второй элементы ИЛИ, триггер, первый и второй элементы И, регистр сдвига, группа из К (К - число подграфов графа) регистров номеров вершин, узлы индикации числа вершин и узлы индикации номеров вершин, каждая модель вершины содержит два элемента ИЛИ и пять элементов И, причем выход каждого элемента ИЛИ группы соединен с единичным входом соответствующего триггера групп единичный выход каждого i-ro триггера группы (,п) соединен с 1-м входом блока задания топологии графа и входами (1+1)-го, (1+2)-го, ...,п-го элементов И первой группы, каждый шлход блока задания топопоги графа через дифференцирующий элемен группы соединен с соответствукадими информационными входами всех регист ров номеров вершин группы, соответствующим разрядом регистра сдвига, вторым входом соответствующего элемента ИЛИ группы и соответствующим входом первого элемента ИЛИ, выход которого подключен к единичному входу триггера, нулевой вход которого соединен с выходом второго эле мента ИЛИ, первый вход которого под ключен к выходу п-го элемента И первой группы, а второй вход - к входу установки исходного состояния устройства, единичный выход триггера соединен с первым входом первого элемента И, второй вход которого соединен с первым входом второго эл мента И и подключен к выходу генера тора тактовых импульсов, выход перв го элемента И соединен со сдвигающи входом регистра сдвига нулевые выхо разрядов которого соединены с вторы третьим, ..., (п+1)-м входами второго элемента И, выход которого под ключен к входу распределителя имnvnbf-DB и чеиез элемент задержки к третьему входу второго элемента ИЛИ, первому входу первого элемента ИЛИ группы и объединенным вторым, третьим, .... п-м входам соответствуюцих элементов И первой группы, каждый выход распределителя импульсов соединен с управляющим входом соответствующего регистра номеров вершин группы и с первым входом соответствующего элемента И второй группы ,вторые входы которых объединены и подключены к выходу регистра сдвига, выходы элементов И второй группы соединены с входами соответствующих счетчиков числа вершин группы, информационные выходы счетчиков числа вершин группы и информационные выходы регистров номеров вершин группы соединены с входами соответствуюш тх узлов индикации числа вершин и узлов индикации номеров вершин, управляющие входа которых объединены и подключены к выходу п-го элемента И первой группы,а входы установки в нуль счетчиков числа вepuJин группы и регистров номеров вершин группы объединены и соединены с входом установки исхолного состояния устройства, входы первого элемента ИЛИ каждой, модели вершины соединены с выходами третьих элементов И всех остальных моделей вершин, выходы первых элементов ИЛИ моделей вершин соединены с первыми входами соответствующих первых элементов И моделей вершин, выходы которых соединены с первыми входами вторых элементов ИЛИ своих моделей вершин, вторые выходы которых соединены с выходами вторых элементов И своих моделей вершин, первые входы которых являются входами моделей вершин и соединены с соответствующими входами блока задания топологии графа, вторые входа первых, вторых, третьих, четвертых и пятых элементов И моделей вершин объединены и образуют входы задания данных вершин в топопогии графа устройства, выходы вторых элементов ИЛИ моделей вершин соединены с первыми входами третьих, четвертых и пятых элементов И своих моделей вершин, являются выходами моделей вершин и соединены с соответствующими выходами блока задания топологии графа, а третьи входы третьих, четвертых и пятых элементов И являются входами задания ребер в топологии графа устройства. На фиг.1 приведена структурная схема устройства на фиг.2 - возможная реализация блока задания топологии графа; на фиг.З - граф. Устройство состоит из группы 1,-lf, элементов ИЛИ, группы триггеров , группы 3,-3f, элементов и, блока 4 задания топологии графа, группы дифференцирующих элементов, элемента ИЛИ б, регистра 7 сдвига, группы регистров. 8;|-8(; номеров вершин, триггера 9, элемента ИЛИ 10, шины 11 установки исходного состояния, элемента И 12 генератора 13 тактовых импульсов, элемента И 14, распределителя 15 импульсов, элемента 16 задержки, группы 17,-17к элементов И, группы счетчиков 18,-18|; числа . вершин , узлов индикации числа вершин, узлов индикации 20i-20j; номер вершин. Блок задания топологии графа (фиг.2) содержит N одинаковых моде лей .вершин, каждая из которых соде жит элемент ИЛИ 21, элементы И 22 и 23, элемент ИЛИ 24, элементы И 2 27f вход 28 задания топологии графа устройства, вход 29 блока задания топологии графа, входы 30-32 задания топологии графа устройства выход 33 блока задания топологии графа. Для задания топологии графа,например согласно фиг. 3, необходимо подать единичные потенциалы на входы 28, 30, 31 и 32 всех моделей вершин графа так, как это показано на фиг.2. Перед началом работы по шине 11 на триггеры и 9, регистр 7 сдвига, регистры , распредели тель 15 импульсов, который также представляет собой регистр сдвига, и счётчики 18i-18K подается сигнал установки исходного состояния. При этом на нулевых выходах всех разря дов регистра,7 устанавливаются еди ничные потенциалы, которые вызываю появление единичного сигнала на вы ходе элемента И 14. Этот сигнал записывает единицу в первый разряд распределителя 15 и через элемент задержки и элемент ИЛИ 11 задним фронтом переводит триггер 2i в единичное состояние. Единичный потенциал с выхода этого триггера поступает на вход первой вершины блока 4 задания топологии графа и появляетс на выходе первой вершины и на выход всех тех вершин, которые образуют множество свя занных вершин. Через дифферен.цирующиё элементы 5,-5f, еди ничные импульсы с возбужденных выходов (вершин графа) блока 4 поступают через элементы ИЛИ II-IM на единичные входы соответствующих триггеров ,, которые, переходя в единичное состояние., фиксируют связный подграф. Единичные импульсы с дифференцирующих элементов записываются в соответствующие разряды сдвигающего регистра 7, а также регистра 8), так как в данный момент разрешающий потенциал имеется на первом выходе распределителя 15 и, кроме того, любой из этих импульсов через элемент ИЛИ 6 переводит триггер 9 в единичное состояние. При этом открывается элемент И 12 и тактовые импульсы с генератора 13 начинают поступать -на сдвигающий вход регистра 7. Каждый тактовый импульс сдвигает код регистра 7 на один разряд. При этом каждая единица с последнего разряда регистра 7 считывается через открытый элемент 17 в счетчик 18,. Считывание происходит до тех пор, пока регистр 7 полностью не обнулится. Например, если в регистр 7 записан код 1001100, то первые два тактовые импульса записи в счетчик 18 не дают, третий и четвертый импульсы записывают две единицы, затем пятый и шестой импульсы состояние счетчика 18 также не изменяют и седьмой импульс записывает третью единицу в счетчик 18,. Это свидетельствует о том, что первый подграф состоит из трех связанных вершин, номера которых 1, 4 и 5 записаны в регистр В. При обнулении регистра 7 на его нулевых выходах появляются единичные потенциалы, которые открывают элемент И 14. Один тактовый импульс генератора 13, пройдя через элемент И 14, зТаписывает единицу во второй разряд распределителя 15 импульсов и тем caivEiM разрешает запись в счетчик 182 и регистр 82 . Этот тактовый импульс через элемент 16 задержки и элемент ИЛИ 10 перебрасывает триггер 9 в нулевое состояние, чем заблокируется на время прохождения тактовых импульсов на регистр 7, а через один из открытых элементов И ., устанавливает в единичное состояние тот из триггеров , которому предшествуют триггеры, установленные в единичное состояние ранее. В соответствии с приведенным выше примером в единичное состояние, переводится триггер 3. Этим самым выбирается новая вершина графа, не всмедшая в первый подграф, и, аналогично описанному, возбуждаются все вершины, образующие второй связанный подграф. При этом также происходит апись номеров вершин второго подо Т афа, но уже в регистр 8 . В единичное состояние устанавливаются сответствующие триггеры 2,, просходит запись кода в регистр 7 и чеез элемент ИЛИ б в единичное состояие устанавливается триггер 9. После того начинается считывание из реистра 7 в счетчик 18 числа вершин торого подографа. После обнуления регистра 7 тактовый импульс передвигает единицу на третий выход рас пределителя 15 импульсов, а через элемент 16 задержки поступает на тот из непереведенных в единичное состояние триггеров , который имеет минимальный индекс. Если все триггеры находятся в единичном состоянии, то этот тактовый импульс появляется на выходе элемента 3 сигнал с которого останавливает работу устройства, заблокировав посре ством элемента ИЛИ 10, триггера 9 и элемента И 12 прохождение тактовых импульсов на регистр 7, и подает сигнал разрешения на узлы индикации19,-19j. и , При этом высвечиваются соответственно число вершин в каждом подграфе и их номера. Блок задания топологии грифа 4 позволяет передавать сигнал на выхо всех связанных вершин при его наличии на входе хотя бы одной из них. Блок позволяет отображать топологию любого графа на п заданных вершинах Для этого каждая вершина графа ото ражается элементом ИЛИ 21 с п-1 числом входов, элементами И 22 и 2 и элементом ИЛИ 24, а для отображения ребер, которые могут связывать любую вершину со всеми остальными, используется п-1 трехвходовых элементов И 25-27. 34 Если данная вершина участвует в графе, то на вход 28 необходимо подать единичный потенциал, если определенные ребра участвуют в графе, то на соответствукщие входы 30, 31 или 32 необходимо тоже подать единичные потенциалы. При втвм элемент И 22 запрещает прохождение сигналов по ребрам с участвующей в графе вершины на неучаствующую, а элемент И 23 осуществляет запрет перебора неучаствующих в графе вершин. Единичные потенциалы подаются на те входы 28, 30, 31, 32 вершин, которые позволяют отобразить граф, представленный для примера на фиг.З. Благодаря этому, при подаче на вход 29 одной из вершин единичного потенциала он появляется на выходах 33 всех вершин. В соответствии с описанным процессом работы устройства в счетчик 18 зафиксируются 4 вершины, которые высвечиваются на узле 19 индикации, а в регистре 8) зафиксируются номера вершин,которые высвечиваются на узле 2Q индикации. Предпоженная структура блока задания топологии графа позволяет отображать любую топологию как ориентированных, так и неориентированных графов, каждое ребро которых отображается парой встречно направленных ребер, соединяющих две вершины.