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

З СОВЕТСНИСОЦИАЛИСТИЧЕСН СПУБЛИК 80146235 06 Р 1520 ВСЕСКГИАЯщцд ,;,; ц; БЙБЛЩ,ОПИСАНИЕ ИЗОБРЕТЕНИ ьинй о СССР1986.СССР1986.ЕЛЕНИЯ ПУТ к вычислиь испольГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(54) УСТРОЙСТВО ДЛЯ ОПРЕДВ ГРАФЕ(57) Изобретение относитсятельной технике и может быт эовано для решения комбинированныхи оптимизационных задач на графах.Цель изобретения - расширение функциональных воэможностей - достигаетсяэа счет преобразования графа, заданного матрицей инциденций или весов вдерево всех путей в графе. Для этогов устройство, содержащее генератор 1импульсов и блок 4 матричной моделидерева путей графа, дополнительновведены блок 2 управления и блок 3переименования вершин, и кроме того,блок 4 матричной модели дерева путейграфа содержит матрицу блоков формирования путей. 4 нл.Изобретение относится к вычислительной технике и может быть использовано для решения комбинированныхи оптимизационных задач на графах.Цель изобретения - расширениефункциональных возможностей устройства путем преобразования произвольного графа, заданного матрицей инциденций или весов в дерево всех путей в 10, графе.На фиг. 1 и 2 показана функциональная схема устройства для опреде 3 тения путей в графе; на фиг. 3 функциональная схема блока управления; на фиг.4 - функциональная схема специализированного процессора.Устройство содержит генератор 1. переименования вершин и блок 4 матричной модели дерева путей графа.Генератор 1 импульсов подает на,вход блока 2 управления последовательность тактовых импульсов, управляющих работой блоков устройства.Блок 2 управления предназначен. для записи выбранной корневой вершины, списка ребер исследуемого графа,т.е. установления необходимой коммурции между специализированными процессорами блока 4 матричной моделидерева путей графа в соответствии сосвязями, существующими между вершинамн.Блок 3 переименования вершин служит для выбора корневой вершины,Блок 4 матричной модели дерева путей графа предусмотрен для формирования и записи всех возможных путей висследуемом графе. 40Блок 3 переименования вершин(фиг.1) состоит из регистров 5 и схем6 формирования номеров вершин, включающих схему 7 сравнения, триггер 8,сборки 9 и 10 элементов И и сборку 11 45элементов ИЛИ.Регистры 5 предназначены для записи номеров вершин исследуемого графа.Схема 7 сравнения служит для сравнения номера вершины, записанного врегистре 5, с номером корневойвершины,В исходном состоянии в регистры 5записаны номера вершин графа с 1-йпо И-ую, На выходе схемы 7 сравнения нулевой потенциал, триггер 8 - в единичном состоянии. Сборки 9 элементовИ открыты, сборки 10 элементов И закрыты. На выходе сборки 11 элементов ИЛИ - код, соответствующий номеру вершины, записанной в регистре 5Блок 4 матричной модели дерева путей графа (фиг. 2) состоит из блоков 12 - 15 формирования путей, количество которых по столбцам и строкам одинаково и равно К -1, где К - число вершин в графе.Входы и выходы устройства обозначень следующим образом: 16 - тактовый вход блока управления; 17 - выход номера корневой вершины; 18 - группа информационных входов блока управления; 19 - группа управляющих выходов блока управления.Блок 2 управления состоит из регистра 20 количества вершин, счетчика 21, схемы 22 сравнения, элемента 23 "Запрет", счетчика 24, регистра 25, схемы 26 сравнения, элемента 27 "Запрет", элемента И 28, схемы 29, которая содержит регистр 30, коммутатор 31, регистр 32, схему 33 сравнения, схему 34 сравнения, сборки 35 и 36 элементов И, сборку 37 элементов ИЛИ и распределитель 38 импульсов, кроме этого, в блок 2 управления входят регистр 39, коммутатор 40, а также регистры 41 и 42.Регистр 20 служит для записи количества вершин исследуемого графа.Счетчик 21 предназначен для подсчета количества просмотренных ярусов,Элемент 23 "Запрет" управляет прохожде 1 ием импульсов от генератора 1 на устройство. Дпя досчитывания импульсов, пришедших от генератора 1, служит счетчик 24. В регистр 25 записывается максимальная степень вершины в исследуемом графе. В схеме 26 сравнения сравнивается содержимое регистра 25 и счетчика 24, и в случае совпадения их содержимого на выходе схемы 26 появляется сигнал, который поступает на элемент 27 "Запрет" и элемент И 28, Элемент 27 "Запрет" управляет поступлением импульсов на входы коммутаторов 31 схем 29 и коммутатора 40. Элемент И 28 предназначен Для управления поступлением импульсов на вход коммутаторов 31 и распределителей 38 импульсов схем 29. Схема 29 служит для формирования пакета сигналов, поступающих на вход блока 4 матричной модели дерева путей графа. Для записи номеров тех вершин, с которыми связана данная вершина, предусмотрен регистр 30. Ре1462352 Блоки 12 - 15 состоят иэ схем 43,которые включают в себя регистр 44,сборку 45 элементов "Запрет" и схему 46 сравнения, элемента ИПИ 47, схем48 сравнения, элемента ИЛИ 49 и схе- .мы 50, которая состоит из сборок 51элементов И.Регистры 44 служат для записи номеров вершин, входящих в соответствуаций путь.Сборка 45 элементов "Запрет" управляет поступлением сигналов на сборки 51 элементов И.Схема 46 сравнения сравнивает содержнмое регистра 44 с номером вершины, переданным из блока 2 управления. Схемы 48 сравнения предназначены для сравнения номеров вершин, переданных из блоков 2 и 3 управления и переименования вершин,В исходном состоянии все регистры 44 обнулены. Блок 2 управления работает следующим образом. Первый импульс от генератора 1 импульсов через открытыйэлемент 23 "Запрет" поступает навходы счетчика 24, элемента 27 "Зап-рет" и элемента И 28. В счетчике 24 записывается "1". Через открытый элемент 27 "Запрет" импульс поступаетна входы коммутаторов 31 и 40. Коммутатор 31 подключает первый выходрегистра 30, соответствующий номеру В исходном состоянии в регистр 20 записано число, соответствующее количеству вершин исследуемого графа. В регистр 25 записано число, соответ" ствующее максимальной степени вершины исследуемого графа. В регистрах 30 и регистре 39 записаны числа, соответ ствующие номерам тех вершин, с которыми существует связь данной вершины, номер которой записан в регистрах 32 и регистре 41. В регистре 42 записано число, соответствующее номеру корневой вершины графа, Счетчики импульсов 21 и 24 - в нулевом состоянии.Элементы 23 и 27 "Запрет" открыты.На выходах схем 22 и 26 сравнения - низкий потенциал. Если номер вершины, 50 записанный в регистры 32, совпадает с номером, поступающим из соответствующей схемы б блока 3, то на выходе схемы 33 сравнения присутствует высокий потенциал, если нет - низкий.Если номер вершины совпадает с номером, записанным в регистре 41, то на выходе схемы 34 сравнения появляется высокий потенциал, если нет - низкий. первой из записанных вершин в регистре 30, к входу сборки 35 элементов И. Аналогично коммутатор 40 подключает первый выход регистра 39 к входу сборки 36 элементов И. Через сборку 37 элементов ИЛИ от сборки 35 или 36 сигнал поступает на вход распределителя 38 импульсов. Распределитель 38 импульсов подает на свой первый выход число, соответствующее но-.меру первой вершины, с которой естьсвязь у данной вершины. Этот сигнал,выдается в блок 4. При приходе второго импульса от генератора 1 импульсов схема работает аналогичным образом, только происходит передача чисра, соответствующего номеру второйвершины, с которой есть связь. Такимобразом схема работает до тех пор,пока содержимое счетчика 24 не сравняется с содержимым регистра 25. Вэтом случае на выходе схемы 26 сравнения появляется высокий потенщал,который закрывает элемент 27 "Запрет"и открывает элемент И 28. Новый имгистр 32 служит для записи номера соответствующей вершины. Схема 33 . сравнения предназначена дпя сравнения номера вершины, записанного в регистре 32, с номером вершины, запи" санным в блоке 3 переименования вершин, Схема 34 сравнения служит для сравнения номера К-й вершины, записанного в регистре 4 1, с номером вер шины, записанным в блоке 3 переименования вершин. Сборки 35 и 36 элементов И предназначены для управления поступлением сигналов, соответствующих номерам вершин, с которыми су ществует связь данной вершины, через сборку 37 элементов ИЛИ на распределитель 38 импульсов. Распределитель 38 импульсов служит для управления передачей сигналов, соответствующих 20 номерам вершин, с которыми существует связь данной вершины, на соответствующие выходы распределителя 38. Для записи связей К-й вершины предназначен регистр 39. Коммутатор 40 предус мотрен для подключения выходов ре" гистра 39 к входам соответствующих сборок 36 элементов И схем 29. Регистр 41 служит для записи номера последней вершины, Для записи номера З 0 корневой вершины предназначен регистр 42.5 14623 пульс. проходит через элемент И 28 на вход счетчика 21 и записывает там "1",обнуляет счетчик 24,при этом на выходе схемы 26 сравнения появляется низкий потенциал, который открывает элемент 27 "Запрет" и закрывает элемент И 28. ,Кроме этого, импульс поступает на вход коммутатора 31, обнуляя его, и на вход распределителя 38 импульсов, подсоединяя его второй выход к выходу 19.2 блока 2 управления. Далее блок работает аналогично описанному. Как только чийто, записанное в счетчике 21, совпадет с числом, записанным в регистре 20, на выходе схемы 22 появЛяется высокий потенциал, который запрещает прохождение импульсов от генератора 1 импульсов. Устройство заканчивает свою работу.Блок 3 переименования вершин работает следующим образом. При записи в блоке 2 управления информации о корневой вершине в схемах 7 сравнения происходит сравнение чисел, записанных в регистрах 5 и блоке 2 управления. Нри несовпадении этих чисел триггер 8 остается в единичном состоянии. Содержимое регистра 5 данной строки через открьггую сборку 9 элементов И и сборку 11 элементов ИЛИ поступает на соответствующий выход блока 3 переименования вершин. При совпадении этих чисел на выходе схемы 7 появляется сигнал, который поступает на вход триггера 8 и на его нулевом выходе появляется высокий потенциал, Сборка 9 элементов И закрьвается, а сборка 10 открьвается.Содержимое последнего регистра 5 пос;40 тупает на вход сборки 11 элементов ИЛИ и через нее на соответствующий выход блока 3. Формула из обр ет ения Блок 13 работает следующим образом,. С предыдущего блока 12 в регист ры 44 записываются числа, соответствующие номерам вершин, которые входят в соответствующий путь, причем в регистр 44 последней схемы 43 инфор" мация записьвается из блока 3 переи- менования вершин. При приходе из блока 2 управления информации о выбранной вершине срабатывают схемы 46 и 48 сравнения. Схемы 46 сравнивают с содержимым регистров 44 число, переданное с соответствующего выхода 19, а схема 48 - с числами, переданными с соответствукзцих выходов 18. В том случае, когда содержимое одного из 52 6регистров 44 совпадает с величиной числа, переданного с соответствующего выхода 19, на выходе соответствующей схемы 46 сравнения появляется высокий потенциал, который через элемент ИЛИ 42 запрещает прохождение сигнала через сборки 45. Если в схеме 48 произойдет совпадение сравниваемых числе, то высокий потенциал через элемент ИПИ 49 поступает на вход сборок 45 и разрешает прохождение через них сигналаОдновременно высокий потенциал поступает на вход соответствую" щей сборки 51 элементов И. В том случае, если на выходе элемента ИЛИ 47 присутствует низкий потенциал, а на выходе элемента 49 ИЛИ - высокий, сборки 45 открыты и сигнал, соответствующий содержимому регистров 44, поступает на входы сборок 51 элементов И, Если на выходе одной или нескольких схем 48 сравнения присутствует высокий потенциал, то соответствующие сборки 51 элементов И открьггы и информация о пути поступает в адрес соответствующего блока 13 следующего столбца. Все остальные блоки 12 - 15 работают аналогично, только в блоки 12 запись первого элемента осуществляется с блока 2 управления путем выбора номера корневой вершины.Устройство для определения путей в графе работает следующим образом.Первоначально в блок 2 управления заносится информация о корневой вершине, максимальной степени вершины (исключая корневую), список ребер, в блок 3 переименования вершин записываются номера вершин графа с 1-й по К-ю. При поступлении от генератора 1 импульсов серии импульсов с 1-го по Р-й (где Р - максимальная степень вершины, не считая корневую) в блока 12 формируются пути дерева путей ран. - га 2, которые записываются в блоки 13. При поступлении второй серии импульсов от генератора 1 в блоках 13 формируется дерево путей ранга 3, которое записывается в блоки 13 следующе" го столбца. При записи всех ветвей дерева путей в последнем столбце блока 4 устройство для определения путей в графе прекращает свою работу. Устройство для определения путей в графе, содержащее генератор импульсов и блок матричной модели дерева путей графа, о т л и ч а ю щ е е с я тем, что, с .целью расширения функциональных возможностей за счет преобра 5 зования произвольного графа, заданного матрицей инциденций или весов в дерево всех путей графа, в него введены блок переименования вершин .и блок управления, а блок матричной модели дерева 10 путей графа содержит матрицу (Р)х ф (Р) блоков формирования путей, где Р - число вершин в исследуемом графе, входы первой группы каждого блока формирования путей матрицы со единены с входами первой группы блока матричной модели дерева путей графа, с входами кода для сравнения группы блока управления и информаци.онными выходами группы блока переи ;менования вершин соответственно, входы второй группы каждого блока формирования путей матрицы соединены свходами второй группы блока матричной модели дерева путей графа и с управляюцими выходами группы блока управления соответственно, выход (К,М)блока формирования путей (где К и Мизменяются от 1 до Р) соединен ссоответствующим входом третьей группы каждого блока формирования путей(М+1)-го столбца матрицы, вход блоков формирования путей первого столбца матрицы соединен с входом корневой вершины блока матричной моделидерева путей графа, который соединенс входом корневой вершины блока переименования вершин и выходом корневойвершины блока управления, тактовыйвход которого соединен с выходом генератора импульсов.1462352 Жив. ФСоставитель О.Гречухинаедактор А.Огар Техред Л.Олийнык Корректор И.Муска,при ГЕНТ СССР ете нно-издательский комбинат "Патент", г. Ужгород, улПроизводственноарина аз 715(49 Тирам 667НИИПИ Государственного комитета по изобр113035, Москва Ж, Раую Подписноем и открытия наб д. 4(5