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

вершинами. Устройство содержит первый 1 и второй 2 переключатели, первый 3 и второй 4 шифраторы, регистр 5, третью группу элементов 6 И, первую 7 и вторую 8 группы мультиплексоров, группу регистров 9, матрицу ключей 10, матрицу 1 коммутирующих диодов 12, первую 13 и вторую 14 группы элементов И, дешифратор 15, третий пеИзобретение относится к вычислительной технике и может быть использовано при решении на графах задач исследования систем связи, сетей ЭВМ и т.д.

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

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

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

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

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

реключатель 16, элемент НЕ 17, первый 18 и второй 19 элементы И, генератор 20 тактовых импульсов, счетчик 21. Путем последовательного опроса матрицы 11 определяется дости- jKHMOCTb всех вершин графа из каждой вершины и на основе этого - совокупность существенных вершин графа, 2 ил.

После подачи единичного потенциала на пусковой вход устройства.импульсы с выхода генератора 20.через элемент И 18 поступают на первый вход элемента И 19, на второй вход которого подается единичный потенциал с выхода элемента НЕ 17. Тактовые ргмпульсы с выхода элемента И 19 TIOC- тупают да информационный вход счетчика 21. В зависимости от состояния счетчика 21 на соответствующем выходе дешифратора 15 появляется единич- ньш потенгщал, которьш открывает соответствующие ключи 10 соответствующего регистра 9, а также поступает на соответствующие столбцы матрицы I1. Поскольку на вторые входы элементов И 13 подается единичный потенциал с выхода элемента НЕ 17, то единичный потенциал с соответствующего выхода дешифратора 15 через соответствующий столбец матрицы 11 и соответствующий элемент И 13 поступает на входы соответствующего элемента И 14, а также на информсщионные входы соответствующих ключей 10. Через ключ 10, на управляющий вход которого поступает единичный потенциал с выхода дешифратора 15,, еДиница записывается в соответствующий разряд соответствующего регистра 9. Если между строкой е и столбцом d матрицы 11 диод 12 установлен в проводящем направлении, что соответствует дуге из вершины е в вершину d, то единичный потенциал с выхода элемента И 14е поступает на столбец d и через элемент И 13 записьгоает в разряд d соответствую-- щего регистра 9 единицу. Так продолжается до тех пор, пока в счетчик 21 не поступит k тактовых импульсов.

3

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

2 записано число k) на выхбде элемента НЕ 17 появляется нулевой потенциал, который запрещает прохо де- ние импульсов генератора 20 чере.з элемент И 19, а в счетчике 21 фиксируется число k. Этот-же потенциал с выхода элемента НЕ 17 закрывает элементы И 13. Мультиплексоры 7 и 8 имеют по п информационных входов, подключенных к выходам соответствующих разрядов регистров 9 таким образом, что мультиплексоры 8 коммутируют на первые входы элементов И 6 разряды соответствующего регистра 9, номер которого набран переключателем 2 и преобразован в двоичный код шифратором 4 (т.е. элементы соот ветст вующей строки матрицы достижи- мостей), а мультиплексоры 7 коммутируют на вторые входы элементов И 6 соответствующие разряды регистров 9 в зависимости от номера вершины, набранного переключателем 1 и преобразованного в двоичный код шифратором 3 (т.е. элементы соответствующей строки матрицы обратных достижимостей) . После прихода k-ro тактового импульса в счетчик 21, на выходе переключателя 16 появляется единичный потенциал, который поступает на третьи входы элементов И 6 и разрешает перемножение элементов строк соответствующих матриц достижи мостей и обратных достижимостей. Ре-- зультаты перемножения записываются в соответствующие разряды регистра 5 и индицируются, например, при помощи светодиодов.

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

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

2524

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

5 -12412526

группы объединены с входом элемента() регистра группы соединены с

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

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