(54) УСТРОЙСТВО ДЛЯ ИССЖДОБАНИЯ-ХАРАКТЕРИСТИК
ГРАФА
I
Изобретение относится к вычислительной технике и может быть использовано для определения минимального внешне . устойчивогч множества графа и его мощности, необходимых для решения многих прикладных задач, ипользуюших теоретикографовые модели.
Известно устройство для определения связности вероятностного графа, содержащее .матричную модель графа, элементы И, элементы ИЛИ ij
Известное устройство позволяет определять связность графа, но. не обеспечивает определения минимального внешне устойчивого множества, необходимого, например, при решении задач размещения пунктов управления и обслуживания в коммуникационных сетях различного назначения.
Наиболее близким к изобретению по технической сущности является устройство для исследования связности вероятного графа, содержащее матрицу смежности графа размерностью И-vи, выполненную на триггерах, единичный выход каждого 1 -ого триггера соединен с перBbiM входом соответствующего элемента И матрицы смежности, выход которого подключен к входу элемента ИЛИ j -ого столбца, единичные входы всех триггеров соединены с соответствующими выходами блока начальной установки, упр&вляющий вход которого является входом устройства .
10
Известное устройство не позволяет определить внешне устойчивое мноэкество графа коммуникационной сети и его мощность.
Цель изобретения - расширение функ.15циональных возможностей за счет возможности определения внешне устойчивого множества графа коммуникационной сети.
Поставленная цель достигается тем,
20 что в устройство, содержащее матрицу смежности размерностью И И ,. вьшолненную на триггерах, единичный выход каждого -i, j -го триггера соединен с пер.. вым входом соответствующего элемента И матрицысмежности, выход которого подключен к входу ИЛИ г/ -ого столбца,. единичные входы всех тригге ров соединены с соответствующими вь ходами блока начальной устанбвки, , у1фавляюший вход .которого является входом устройства, введены блсж выбора максимума, блок памяти, элемент И, ге нератор, счетчик и VI мноховходрвых сум строк, выходы триггеров i-ой строки подключены к входам -го мног вхсдового сумматсфа строки, выход ко торого соединен с 1-ым входом и-вхо дового и У1-выходного блока выбора максимума; f -ый выход которого подйлючен к i-ому входу и-входового блока памяти и к вторым входам элеМ.ентов И матрицы смежности -ой Строки, у1фавляющий выход .блока начальной установки соединен с входом запуска генератора, выход которого подключен к входу счетчика и к третьим йходаМ всех элементов Ц матрицы смежности, выход каждогр «J-oro элемента ИЛИ столбца соединен С нулевыми входами тригг ов j-orq столбца, нулевые выходы диагональных -ых триггеров подключены к входам элемен та И, выход которого соединенс входом остановки генератора. На фиг. 1 представлена функциональная схема устройства; на фиг. 2 и 3 возможная реализация многовходовых сумматоров строк и блока Bbi6qpa максимума соответственно. Устройство содерж и элементов ИЛИ 1 столбцов, и И триггеров 2 и элементов И 3 матрицы смежности, Я-многовходовых cyuMuTOpoR 4 строк, блок выбора максимума 5, генератор 6, блок 7 начальной установки, счетчик 8, элеменгг И 9 и блок памяти ДО. На фиг, 1 также обозначены н гпевые выхс ды И диагональньистриггеров 2, выходы 12 блока Выбора максимума 5, выходы 13 и вход 14 блока 7 начальной установки. Мнсговходовый сумматор 4 стрФк (фиг. 2) содержит транзисторы 1 и резисторы 16. Блок выбора максимума S (фиг. 3) содержит реле 17 с замыкающими контактами 18, диоды 19 и реййстор 20.i Устройство работает следу ощим образом. С приходом сигнала на запуск по входу 14 из блока 7 в триггеры 2 по входам 13 переписывается исходная матрица смежности исследуемого графа и запускается генератор 6. Сумматоры 4 совместдо с блоком 5 вьщеляют строку с максимальным числом единиц. По соответствующему выходу 12 блока 5 в блоке памяти 10 внешне устойчивого множества фиксируется номер строки и подготавливаются к работе элементы И 3 данной строки. С гфиходом опросного импульса от генератора 6 срабатывают только те элементы И 3 рассматриваемой строки, в триггерах 2 которой записаны единицы. Сигналы с элементов И 3 через элемент ИЛИ 1 обнуляют триггеры 2 соответствующих столбдов.При этом с нулевых выходов 11 диагональных триггеров 2 снимаются сигналы на элемеиг И 9, который фиксирует момент вьщеления минимального внешне устойчивого множества графа. Если на jacex входах 11 9леме1гга И 9 имеются единичные сигналы, то на его выходе появляется импульс, отключающий генератор 6. При этом в счетчике 8 записывается число опросных импульсов, т.е. мощность минимального внещне устойчивого множества, а в блоке памяти 1О само это множество. Если же не на всех входах 11 элемента И 9 присутствуют единичные сигналы, то устройство переходит к следующему циклу oipoca. Введение дополнительных элементов и связей позволяет решить задачу нахождения как числа доминирования -графа, так и его минимального внещне устойчивого множества. Формула изобретения Устройство для исследования характериЬтик: графа, содержащее матрицу смежности размерностью И и , вьшолнвнную на триггерах, единичный выход каждого /1 j -ро триггера соединен с первым входом соответствукицего элемента И матрицы смежности, выход которого подключен к входу элемента ИЛИ j-ro столбца, единичные входы всех триггеров соединены с соответствующими выходами блока начальной установки, управляющий вход является входом устройства, отличающееся тем, что, с целью расширевяя функциональных возможностей за счет возможности oipeделения внещне устойчивого множества графа, в него введены блок выбора максимума, блок памяти, элемент И, генератор, счетчик и У многовходовых сумматоров строк, ВЫХОДЫ триггеров i -и строки подключены к входам -го многовходового сумматсра строки, выход которого соединен с i -м .входом И-входового и h-выходного блока выбора i максимума, л -и выход котор ого подключен к -му Bjto ду И -входового блока памяти и к вторым Ъходам элементов И матрицы смежности /i -и строки, управляющий выход блока начальной установки соединен с входом запуска генератора, выход которого подключен к входу счетчика и к третьим входам всех элементов И матрицы смеж кости, выход каждого j-го элемента. 9 в66 ИЛИ столбца соединен с нулевыми входами триггеров -i -го столбца, нулевые выходы диагональных V -ых триггеров подключены к входам элемента И, выход которого соединен с вхоаом остановке генератора. Источники инфс ма1ши, 1фшштые во внимание гфи экспертизе 1.Авторское свидетельство СССР М 468244, кл. Q 06 F 15/2ОД972. 2.Авторское свидетельство СССР N 637822, кл. Gr Об F 15/2О, 1976 (прототип).
/5
17 IS
16
W 4Z
16
18
