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

 

Изобретение относится к области вычислительной техники и может быть использовано при решении на графах задач исследования систем связи, сетей ЭВМ и т.д. Цель изобретения состоит в расширении функциональных возможностей за счет определения существенных вершин между двумя концевыми (Л С ЧЭ 4 аяА

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

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

РЕСГ1УБЛИК (19) (В (5ц 4 С 06 Р 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 37! 7384/24-24 (22) 20.02.84 (46) 30.06.86. БА!. N- 24 (72) Е.И. Бороденко и В.Е. Назаренко (53) 681.333(088.8) (56) Авторское свидетельство СССР

Ф 943738, кл. G 06 F 15/20, 1980.

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

Ф 1!74937, кл. G 06 F 15/20, 1984.

1241252 А 1 (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к области вычислительной техники и может быть использовано при решении на графах задач исследования систем связи, сетей

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

1241252 вершинами. Устройство содержит первый

1 и второй 2 переключатели, первый

3 и второй 4 шифраторы, регистр 5, третью группу элементов б И, первую

7 и вторую 8 группы мультиплексоров, группу регистров 9, матрицу ключей

10, матрицу ll коммутирующих диодов

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

ЗВМ и т.д. 5

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

На чертеже изображена функциональная схема устройства.

Устройство содержит первый 1 и второй 2 переключатели, первый 3 и второй 4 шифраторы, регистр 5, третью группу элементов И 6, первую

7 и вторую 8 группы мультиплексоров, группу регистров 9, матрицу и и ключей 10 (n - число вершин графа), матрицу 11 коммутирующих диодов 12, первую 13 и вторую 14 группы элементов И, дешифратор 15, третий переключатель 16, элемент НЕ 17, первый

18 и второй 19 элементы И, генератор

20 тактовых импульсов и счетчик 21.

Первоначально с помощью коммутирующих диодов 12 набирается топология исследуемого графа, а подачей сигнала на установочный вход устройства обнуляются регистры 5 и 9 и счетчик 21. С помощью переключателя 1 набирается номер j-й, а с помощью переключателя 2 — номер i-й вершины, для которой определяется множество существенных вершин, принадлежащих хотя бы одному пути из х-й вершины в )-ю. С помощью переключателя !6 набирается число вершин в исследуемом графе.

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

4О реключатель lб, элемент HF. 17, первый 18 и второй 19 элементы И, генератор 20 тактовых импульсов, счетчик 21. Путем последовательного onроса матрицы 11 определяется достижимость всех. вершин графа из каждой вершины и на основе этого — совокупность существенных вершин графа.

2 ил.

После подачи единичного потенциала на пусковой вход устройства импульсы с выхода генератора 20.через элемент И 18 поступают на первый вход элемента И 19, на второй вход которого подается единичный потенциал с. выхода элемента НЕ 17. Тактовые импульсы с выхода элемента И 19 поступают,на информационный вход счетчика 21. В зависимости от состояния счетчика 21 на соответствующем выходе дешифратора 15 появляется единичный потенциал, который открывает соответствующие ключи 10 соответствую.— щего регистра 9, а также поступает на соответствующие столбцы матрицы

Il. Поскольку на вторые входы элементов И 13 подается единичный потенциал с выхода элемента НЕ 17, то единичный потенциал с соответствующего выхода дешифратора 15 через соответствующий столбец матрицы 11 и соответствующий элемент И 13 поступает на входы соответствующего элемента И 14, а также на информационные входы соответствующих ключей 10. Через ключ 10, на управляющий вход которого поступает единичный потенциал с выхода дешифратора 15,, единица записывается в соответствующий разряд соответствующего регистра 9. Если между строкой е и столбцом d матрицы 11 диод 12 установлен в проводящем направлении, что соответствует дуге из вершины е в вершину d, то единичный потенциал с выхода элеменга И 14е поступает на столбец d и через элемент И 13 записывает в ра="ðÿä d соответствующего регистра 9 единицу. Так продолжается до тех пор, пока в счетчик 21 не поступит k тактовых импульсов.

)241252 4

При этом в каждом регистре 9 будет записана соответствующая строка матрицы достижимостей исследуемого графа, а номер регистра соответствует .номеру строки этой матрицы. После по- 1 явления на k-м выходе дешифратора 15 единичного потенциала (в счетчике

21 записано число К) на вьгхдде элемента НЕ 17 появляется нулевой потенциал, который запрещает прохождение импульсов генератора 20 через элемент И 19, а в счетчике 21 фиксируется число k. Этот -же потенциал с выхода элемента НЕ 17 закрывает элементы И 13. Мультиплексоры 7 и

8 имеют по и информационных входов, подключенньгх к выходам соответствующих разрядов регистров 9 таким образом, что мультиплексоры 8 коммутируют на первые входы элементов И 6 20 разряды соответствующего регистра

9, номер которого набран переключателем 2 и преобразован в двоичный код шифратором 4 (т.е. элементы соответствующей строки матрицы достижимостей), а мультиплексоры 7 коммутируют на вторые входы элементов

И 6 соответствующие разряды регистров 9 в зависимости от номера вершины, набранного переключателем 1 и 30 преобразованного в двоичный код шифратором 3 (т.е. элементы соответствующей строки матрицы обратньгх достижимостей). После прихода k-.ãî тактового импульса в счетчик 21, на выходе переключателя 16 появляется единичный потенциал, который поступает на третьи входы элементов И 6 и разрешает перемножение элементов строк соответствующих матриц достижи-АО мостей и обратных достижимостей. Результаты перемножения записываются в соответствующие разряды регистра

5 и индицируются, например, при помощи светодиодов. 45

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

Устройство для исследования параметров графа, содержащее генератор 50 о тактовых импульсов, два элемента И, элемент НЕ, счетчик, дешифратор группу регистров, матрицу пхп ключей, (n — число вершин графа), две группьг элементов И и матрицу пхп коммути- 55 рующих диодов, строки которой через коммутирующие диоды соединены с соответствующими столбцами согласно топологии графа, причем строки матрицы комм тируюших диодов соединены с выходами одноименных элементов И первой группы, вьгходы столбцов матрицы коммутирующих диодов подключены к первым входам одноименных элементов

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

1241252

Составитель А. Шеренков

Редактор А. Пчелииская Техред В.Кадар Корректор С. Черни

Заказ 3601/45 Тираж 671 Подписное

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

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

Производственно-полиграфическое предлриятие, г. Ужгород, ул. Проектная, 4 группы объединены с входом элемента

НЕ и соединены с выходом третьего переключателя, входы которого подключены к одноименным выходам дешифратора, à i-й (i=1,n) выход j-го (j=1,n) регистра группы соединены с

i-и информационным входом )-го муль" типлексора первой группы и j-м ин5 формационным входом i -го мультиплексора второй группы.