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

 

О Il И С А Н И Е п,935966

ИЗОБРЕТЕНИЯ

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

Союз .Советских

Социалистических

Республик (6l ) Дополнительное к авт. свид-ву (22) За влево 15.07.80(2l ) 2961652/18-24 (5 ) ) Я. Кл.

G 06 F 15/20 с присоединением заявки №

1аоудвротеаеый комитет

СССР

II0 делам изобретений и открытий (23) Приоритет

Опубликовано 15.06.82. Бюллетень ¹ 22 (53).УДК 681.325 (088. 8) Дата опубликования описания 17.06.82 (72) Авторы изобретения

П. К. Павнитьев и В. А. Яирончик (7!) Заявитель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ХАРАКТЕРИСТИК

ГРАФА

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

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

И, элементы ИЛИ (1).

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

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

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

Известное устройство не позволяет определить внешне устойчивое множество графа коммуникационной сети и его мощность.

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

Поставленная цель достигается тем, что в устройство, содержащее матрицу смежности размерностью И < и,, выполненную на триггерах, единичный выход каждого .т, -го триггера соединен с пер935966 4

4$

И

И вым входом соответствующего элемента

И матрицы смежности, выход которого подключен к входу элемента ИЛИ g -ого столбца,. единичные входы всех триггеров соединены с соответствующими выходами блока начальной устандвки, 1 управляющий вход:которого является входом устройства, введены блок выбора . максимума, блок памяти, элемент И, генератор, счетчик и И мноховходовых сумматоров строк, выходы триггеров <-ой. строки подключены к входам -го многовходового сумматоре строки, выход ко-. торого соединен с 1-ым входом И-входового и и -выходного блока выбора максимума, j-ый выход которого подключен к л«ому входу И -входового блока памяти и к вторым входам эле-! ментов И мач",рицы смежности -ой строки, управляющий выход, блока начальной установки соединен с. входом запуска генератора, выход которого подключен к входу счетчика и к третьим входам всех элементов И матрицы смежности, выход каждого .g-ого эле-, мента ИЛИ столбца соединен с нулевы- ми входами триггеров ) -orq столбца, нулевые выходы диагональных -у -ых триггеров подключены к входам элемен-: та И, выход которого соединен с входом остановки генератора, На фиг. 1 представлена функцйональная схема устройства; на фиг. 2 и 3возможная реализация многовходовых сумматоров строк и блока выбора мак- симума соответственно.

Устройство содержцт .и элементов

ИЛИ 1 столбцов, п «и триггеров 2 и

И«и элементов И 3 матрицы смежности, И-многовходовых сумматоров 4 строк, блок выбора максимума 5, генератор 6, блок 7 начальной установки, счетчик 8, элемент И 9 и блок памяти 10. На фиг, 1 также обозначены щ левые выхс, ды 11 диагональных триггеров 2, выходы 12 блока выбора максимума 5, выходы 13 и вход 14 блока 7 начальной установки. Яноговходовый сумматор 4 стрэк (фиг. 2) содержит транзисторы 15 и резисторы l6. Блок выбора максимума 5 (фиг. 3) содержит реле 17 с замыкающими контактами 18, диоды 19 и резистор 20.

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

С приходом сигнала на запуск по входу 14 из блока 7 в триггеры 2 по входам 13 переписывается исходная

I матрица смежности исследуемого графа и запускается генератор 6. Сумматоры

4 совместно с блоком 5 выделяют строку с максимальным числом единиц. По соответствующему выходу 12 блока 5 в блоке памяти 10 внешне устойчивого. множества фиксируется номер строки и подготавливаются к работе элементы

И 3 данной строки. С приходом опрос10 ного импульса от генератора 6 срабатывают только те элементы И 3 рассматриваемой строки, в триггерах 2 которой записаны единицы. Сигналы с элементов И 3 через элемент ИЛИ l. обнуляют триггеры 2 соответствующих столбцов.При этом с нулевых выходов 11 диагональных триггеров 2 снимаются сигналы на элемент И 9, который фиксирует момент выделения минимального внешне устойчивого. множества графа. Если на всех входах 11 элемента И 9 имеются единичные сигналы, то на его выходе появляется импульс, отключающий генератор 6. При этом в счетчике 8 записывается число опросных импульсов, т.е. мощность минимального внешне устойчивого. множества, а в блоке памяти 10— само это множество. Если же не на всех входах 11 элемента И 9 присутствуют единичные сигналы, то устройство переходит к следующему циклу опроса.

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

Формула изобретения.Устройство для исследовании характеристик; графа, содержащее матрицу смежНости размерностью И w и, выполненную на триггерах, единичный выход каждого

j -po триггера соединен с первым входом соответствукнцего элемента И матрицы смежности, выход которого подключен к входу элемента ИЛИ j-ro столбца, единичные входы всех триггеров соединены с соответствующими выхода ми блока начальной установки, управляющий вход которого является входом .устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет возможности îïðåделения внешне устойчивого множества графа, в него введены блок выбора максимума, блок памяти, элемент И,.генератор, счетчик и 5 многовходовых суммато935966 ров строк,,выходы триггеров -й строки подключены к входам -го многовходового сумматора строки, выход которого соединен с 1 -м входом И-входового и

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

ИЛИ столбца соединен с нулевыми входаИ ми триггеров 1-ro столбца, нулевые выходы диагональных 4 g -ых триггеров

I подключены к входам элемента И, выход

S которого соединен с входом остановки генератора.

Источники информации, принятые во внимание при экспертизе

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

% 468244, кл. G 06 Р 15/20,1972.

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

N. 637822, кл. G 06 Р 15/20, 1976 (прототип).