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

Изобретение относится к вычислительной технике и может быть использовано для решения задач на графах, связанных с определением достижимости вершин ориентированных графов, являющихся математическими моделями сетей связи, информационнорасчетных систем и т.д. Цель изобретения - расширение функциональных возможностей за счет определения достижимости вершин ори ентированного графа. На чертеже представлена структурная схема устройства. Устройство содержит первую группу элементов И 1(-1„, вторую группу элементов И , выход 3 останова устройства, регистры , in групп элементов И ,, 6,-бп,..., образукицих матрицу из п. г элементов И (п - число вершин графа), вход ( 10пуска устройства, дешифратор П, счетчик 12, второй элемент И 13, элемент НЕ 14, генератор 15 тактовых импульсов, первый элемент И 16, наборное поле.17, выпрямительные элементы 18. Устройство работает следующим образом. На наборном поле 17 набирается топология графа путем включения выпрямительных элементов 18 в проводяЕ1ем направлении между i -и строко и j -м столбцом при наличии связи между 1 -и и j -и вершинами. Путем подачи сигнала на вход 3 счетчик 12 и регистры 4 устанавливаются в нулевое состояние. Для запуска устройстна подают потенциал на вход 10 пуска, тогда через элемент И 16 тактовые импульсы с выхода генерато ра 15 поступают на вторую схему И 1 которая открыта напряжением логичес кой единицы с выхода инвертора 14, так как на выходе п +1 дешифратора 11присутствует напряжение логическ го нуля. Напряжение логической 1 выхода инвертора 14 открьгаает также элементы И 2. После записи в счётчик 12 первог импульса на первом выходе дешифратора 11 появляется напряжение логи172 ческой 1, которое поступает на элементы И 5, открывает их и подключает входы регистра 4) к выходам соответствующих элементов И . Напряжение логической I с первого выхода дешифратора 11 подается также на первый столбец наборного роля 17 и записывает в первый разряд регистра 4, единицу. Рассмотрим работу устройства на примере включения в наборное поле 17 трех диодов 18. Через элемент И единичное напряжение поступает на первую строку наборного поля 17 и через диод 8 и элемент И 2 записывает в третий разряд регистра 4( единицу, поступает через элемент И 1 на третью строку и через диод 18 записывает в четвертый разряд регистра 44 единицу, поступает через элемент И 1, на четвертую строку. После прихода второго импульса напряжение логической 1 появляется на втором выходе дешифратора 11j а на первом выходе будет логический О, который поступает на вторые входы элементов И 5)-5, и отключает регистр 4 I от наборного поля; одновременноснимается напряжение логической 1 с первого столбца. Единичное напряжение с второго выхода дешифратора 11 открывает элементы И 6|-6h, подключая тем самым регистр 4 к наборному полю 17, а также подается на второй столбец. Далее работа устройства аналогична работе в первом такте. После записи информации в регистр 4 и прихода третьего и четвертого тактовых импульсов аналогично информации о достижимости вершин графа записьюается в регистры 4 -j. и 4 . С приходом (h+l)-ro тактового импульса на выходе инвертора 14 появляется напряжение логической 1, которое запрещает да-пьнейшее прохождение тактовых импульсов в счетчик 12 и закрьшает элементы И ), отключая тем самым столбцы наборного поля 17 от регистров 4 ,-4 f,. В результате в регистрах 4 -4 у, содержится информация о достижимости вершин графа.

УСТРОЙСТВО ДПЯ ОПРЕДЕЛЕНИЯ СВЯЗНОСТИ ОРИЕ,НТИРОВАННОГО ГРАФА, содержащее генератор тактовых импульсов, два элемента И, две группы по п элементов И, матрицу Пп элементов И, элемент НЕ, дешифратор и счетчик, выход которого подключен к входу дешифргтора, первый вход первого элемента И является входом пуска устройства, второй вход первого элемента И подключен к выходу генератора тактовых импульсов, а i -и ( l,2,...,yi) выход дешифратора соединен с первыми входами элементов И 1 -го столбца матрицы п h элементов И, отличаю щ есе с я тем, что, с целью расширения функциональных возможностей за счет определения достижимости вершин, в него введены П регистров, выходы которых являются выходами устройства, выпрямительные элементы, наборное поле, строки которого через вьшрямительные элементы соединены с соответствующими столбцами в соответствии с топологией графа, причем строки наборного поля соединены с выходами одноименных элементов И первой группы, выходы столбцов наборного поля подключены к первым входам элементов И второй группы, выход 1 -го элемента И второй группы соединен с входом одноименного элемента И первой группы и подключен к вторым входам элементов И i -и строки матрицы D элементов S И, выходы элементов И i -го столбца (Л которой соединены с .одноименными информационными входами -го регистра, управляющий вход счетчика, соединен с управляющими входами регистров и является входом остано.ва устройства, суммирующий вход счетчика подключен к выходу второ го элемента И, первый и второй входы 4 которого соединены соответственно с СО со выходом первого элемента И и выходом элемента НЕ, который подключен также к вторым входам элементов И второй группы, а вход элемента НЕ соединен с (п+1)-м выходом дешифратора.