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

д 679993

ОП ИСАНИ Е

ИЗОБРЕТЕН ИЯ

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

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

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

Ресяублнк (61) Дополнительное к авт. свид-ву № 329538 (22) Заявлено04.05.77 (2i)2482570/18-24 с присоединением заявки Ие (23) Приоритет— (51) М. Кл.

4 06 О 7/48

Государственный комитет

СССР но делам изобретений н открытий.Опубликовано15.08.79. Бюллетень № 30 (53) УДК 681.333. .001.57 (088.8) Дата опубликования описания 20.08.79 (72) Автор изобретения

M. А. Климовицкий

Украинский государственный проектный институт

"Металлург авт оматик а (71) Заявитель (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА ДЕРЕВЪЕВ

ГРАФА

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

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

2 подключен к первому входу соответствукьmего ключа, выход схемы И через схему

НЕ подключен ко вторым входам всех ключей, а выход каждого ключа подключен к входу соответствуюшего счетчика (1).

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

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

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

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

На чертеже представлена блок-схема устройства для определения числа деревьев графа.

Устройство содержит блок 1 перебора сочетаний, запоминающие триггеры 2, управляемые ключевые схемы 3, схему И

4, схему НЕ 5, шину 6 установки устройства в исходное состояние, командную, 10 шину 7, шину 8 проверки проводимости, ключи 9, счетчики дуг 10, счетчики цепей 1 1, блэк сравнения 12, схемы HJIH

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

Работа устройства основана на том, что проверяется связность всех М узлов сети при различных сочетаниях из А дуг 20 сети, по (Й -1) дуг, так как последовательность узлов "åòè Х Е N обладающая тем свойством, что (Х,Х +„) при каждом 1 + 1 ееа И -1 является цепыэ: она ведет из Х„в Х .После каждого испы- 5 тания количество узлов сети уменьшается до момента, когда из Х В Х нет ни одного пу;ги, т. е. до получения разреза сети, содержащего минимальное количество дуг. Устройство работает по так- ЗО

"в шине 6 через схемы ИЛИ поступает сит нал установки триггеров и счетчиков в нулевое положение. В каждом такте на выходе блока перебора сочетания по- 35 является одно из сочетаний С 1 послеА довательности дуг, ведущих через узлы

И из Х< Ь N.п;которое поступает на аходы заломинаюших триггеров 2 и перебрасывает их в единичное состояние.

Триггеры запоминают полученную комбинацию дуг и открывают соответствующие управляемые ключевые схемы. Между ахэдами открытых управляемых ключевых схем 3 образуется электрический 4 контакт. В такте 4> по шине 8 поступает сигнал проверки прэводимости, который подается на аходы управляемых ключевых . схем.. 3. Вход одной из ключевых схем отображает узел Х4 сети. Вторые вхо- 0 ды управляемых ключевых схем, отображающих цепи из оставшихся (l4-1) узлов, выведены на аходы схемы И.

Если все узлы сети связаны, тэ на всех входах схемы И появляются сигналы, и данное сочетание узлов и дуг образует цепь. Схема И срабатывает, и сигнал с нее через с.хему НЕ поступает

4 на счетчик 11, а через ключи, открытые единичным аходам запоминающих триггеров, на счетчики 10, соответствующие дугам, которые образуют данную цепь.

После выдачи всех возможных сочетани» блоком 1 по шине 7 поступает сигнал окончания испытания. Результаты испытания определяются по показаниям счет» чика 11, который показывает общее количество цепей сети, и по показаниям счетчиков 10, которые показывают число цепей сети, образованных с участием соответствующей дуги.

В такте "4. блок сравнения 12 проверяет наличие показаний на счетчике 11 и сравнивает показания счетчиков 10.

При атом, если показания счетчика 11 не равны нулю, то блок сравнения 12 выбирает счетчик 1 0 с наибольшими и ок аз аниями и на соответствующем ему выходе

14 формирует единичный сигнал. Этот сигнаЛ через схему ИЛИ 13 и. запоминающий триггер 2 запирает соответствующую ключевую схему 3 и ключ 9 счетчика 10. Получен разрез моделируемой сети.

Затем проводятся контрольные испытания полученной сети по тактам t4,тg t,Если в результате очередного испытания показания счетчика 11 оказались равными нулю, то цикл испытаний закончен и полученный разрез сети является минимальным. Результат фиксируется по порядку отключения счетчиков 10.

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

Формула изобретения

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

ИЛИ, первые входы которых подключены к шине установки устройства в нулевое .. состояние, выходы элементов ИЛИ соединены со входами установки в нулевое сОстояние соответствующих триггеров, ВТо679998

5 рые входы элементов ИЛИ подключены K соответствующим выходам блока сравнения, входы которых соединены с выходами всех счетчиков.

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

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

14 329538, G 06 G 7/48 1970(прототип), Составитель И. Дубинина

Редактор Н. Белявская Техред Э. Чужик Корректор екто А. Г иценко

3аказ 4796/45 Тираж 780 Подписное

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

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

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