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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 1683036 А 51)5 6 06 Е 15/419 ПИСАНИЕ ИЗОБРЕТЕНИЯ ОО бв 2 бр ОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР К АВТОРСКОМУ СВИДЕТЕЛЬСТВ(71) Уфимский авиационный институт им. Серго Орджоникидзе .(56) Авторское свидетельство СССР М 862145, кл. 6 06 Р 15/20, 1980.Авторское свидетельство СССР М 1587535, кл, 6 06 Е 15/20, 1988.(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФА(57) Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе со взвешенными вершинами. Целью изобретения является расширение функциональных воэможностей устройства эа счет определения величин максимальных путей в стоки графа со взвешенными вершинами. Предлагаемое устройство содержит генератор 1 серии импульсов, многоканальный таймер 2, блок 3 определения стоков, блок 4 задания матрицы смежности, вход 5 пуска устройства и выходы б веса пути из вершин в наиболее удаленные от них стоки графа устройства. Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа, каналы многоканального таймера загружают числами, пропорциональными весам вершин графа. После подачи на вход 5 пуска устройства импульса уровня логической единицы генератор 1 формирует серию импульсов, количество которых совпадает с полной емкостью канала таймера 3 2, при этом на его информационных выходах формируют искомые веса путей. 4 ил.Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе со взвешенными вершинами.Целью изобретения является расширение функциональных воэможностей устройства за счет определения величин максимальных путей в стоки графа со взвешенными вершинами.На фиг.1 представлена функциональная схема устройства; на Фиг.2 - функциональная схема блока определения стоков; на фиг.З - Функциональная схема блока задания матрицы смежности; на фиг,4 - функциональная схема многоканального таймера,Устройство содержит генератор 1 серии импульсов, многоканальный таймер 2, блок 3 определения стоков, блок 4 задания матрицы смежности, вход 5 пуска устройства и выходы 6 веса пути из вершин в наиболее удаленные от них стоки графа устройства,На схеме (фиг.2) обозначены группа элементов ИЛИ-НЕ 7, входы 8 признаков наличия дуг и выходы 9 признаков принадлежности вершин массиву стоков графа, причем вход 8 признака наличия (К,М)-й дуги блока определения стоков (К= 1В; М=1В, где В - количество вершин в графе) подключен к К-му входу М-го элемента ИЛИ-НЕ 7 группы, выход которого является выходом 9 признака принадлежности М-й вершины массиву стоков графа,На Фиг.З цифровые обозначения представляют матрицу из В х В триггеров 10, причем вход 11 задания признака наличия дуги из М-й в К-ю вершину графа блока 4 задания матрицы смежности подключен к входу установки в единицу К-го триггера 10 М-й строки матрицы, выход которого является выходом 12 признака наличия (К,М)-й дуги блока 4 задания матрицы смежности, вход 13 удаления дуг, заходящих в К-ю вершину, которого подключен к входам установки в "0" всех триггеров 10 К-го столбца матрицы,На фиг.4 цифровые обозначения представляют группу из В,счетчиков 14, причем вход 15 разрешения работы М-го канала многоканального таймера 2 подключен к входу разрешения счета М-го счетчика 14 группы, информационный выход которого является М-ым информационным выходом 16 многоканального таймера 2, вычитающий вход 17 которого подключен к вычитающим входам всех счетчиков 14 группы, выход признака переполнения М-го из которых является выходом 18 признака переполнения М-го канала многоканального таймера 2.Устройство работает следующим образом,Перед началом работы в блок 4 заданияматрицы смежности заносят информацию отопологии графа, каналы многоканальноготаймера 2 загружаются числами, пропорци 5 ональными весам вершин графа (при этомпредполагается, что емкости всех каналовтаймера 2 одинаковые и превышают весмаксимального пути).На вход 5 пуска устройства подают им 10 пульсный сигнал уровня логической "1", Приэтом генератор 1 формирует серию импульсов, количество которых совпадает с полнойемкостью канала таймера 2. При поступлении на вычитающий вход таймера 2 импуль 15 сов уровня логической "1" те его каналы,работа которых разрешена потенциаламиуровня логической "1" с выходов блока 3определения стоков, работают на вычитание. В момент перехода через "0" канал20 таймера 2 формирует импульсный сигналуровня логической "1" (признак окончания.моделирования вершины, номер которойсовпадает с номером канала таймера). Приэтом блок 4 задания матрицы смежности25 удаляет дуги, заходящие в вершину, соответствующий номеру которой канал таймера 2 сформировал сигнал переполнения.При этом разрешается работа следующихканалов таймера 2 и т.д., причем те его ка 30 налы, которые сформировали сигналы йереполнения, продолжают счет, начиная сосвоей полной емкости. После поступленияна вычитающий вход таймера 2 последнегоимпульса серии на его информационных вы 35 ходах сформированы веса длиннейших путей иэ вершин графа в наиболее удаленныеот них стоки,Устройство можно использовать для определения весов кратчайших путей из вер 40 шин в ближайшие к ним стоки графа, Дляэтого матрицу смежности перед началом ра-,боты необходимо транспонировать относительно главной диагонали.Блок 4 задания матрицы смежности ра 45 ботает следующим образом,Перед началом работы обнуляют триггеры 10 матрицы и по входам 11 заносят инФормацию о топологии графа, Припоступлении на входы 13 импульсов уровня50 логической "1" триггеры 10 соответствующих им столбцов устанавливаются в "0" (темсамым удаляются дуги, заходящие в вершины, номера которых совпадают с номерамистолбцов),55 Многоканальный таймер 2 работаетследующим образом.Перед началом работы в счетчики 14заносят информацию о весах вершин. Припоступлении на вход 17 импульсов уровнялогической "1" те счетчики 14, на входахразрешения счета которых присутствует потенциал уровня логической "1", работают на вычитание, при переходе через "0" формируют сигнал переполнения и продолжают счет от своей полной емкости.Формула изобретения Устройство для исследования параметров графа, содержащее блок задания матрицы смежности и генератор серии импульсов, вход пуска которого является входом пуска устройства, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройства за счет определения величин максимальных путей в стоки графа со взвешенными вершинами, в него введены блок определения стоков и многоканальный таймер., причем тактовый выход генератора серии импульсов подключен к вычитающему входу многоканального таймера, выход признака переполнения К- го канала которого (К = 1, ., В, где В - 5 количество вершин в графе) подключен квходу удаления дуг, заходящих в К-ную вер.шину блока задания матрицы смежности, выход признака, наличия (К,М)-й дуги которого (М = 1В) подключен к одноименному 10 входу блока определения стоков, выход признака принадлежности М-й вершины массиву стоков которого подключен к входу разрешения работы М-го канала многока нэльного таймера, М-й информационныйвыход которого является выходом массы пути из М-й вершины в наиболее удаленный от нее сток графа устройства. фл Ь Ьв1683036 Ь Му )8, 76 788 768е Составитель А,МишинТехред М.Моргентал Корректор А,Осауленк Редактор М,Бланар Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101 каз 3415 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб., 4/5