Устройство для исследования параметров графа
Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе со взвешенными вершинами . Целью изобретения является расширение функциональных возможностей устройства за счет определения величин максимальных путей в стоки графа со взвешенными вершинами. Предлагаемое устройство содержит генератор 1 серии импульсов, многоканальный таймер 2, блок 3 определения стоков, блок 4 задания матрицы смежности, вход 5 пуска устройства и выходы 6 веса пути из вершин в наиболее удаленные от них стоки графа устройства Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа, каналы многоканального таймера загружают числами, пропорциональными весам вершин графа. После подачи на вход 5 пуска устройства импульса уровня логической единицы генератор 1 формирует серию импульсов, количество которых совпадает с полной емкостью канала таймеоа 2, при этом на его информационных выходах формируют искомые веса путей. 4 ил.
СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (si)s G 06 F 15/419
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ASTOPCKOMY СВИДЕТЕЛЬСТВУ бю 2 бр (21) 4451960/24 (22) 17.05.88 (46) 07.10.91. Бюл. hh 37 (71) Уфимский авиационный институт им. Серго Орджоникидзе (72) Е.В.Яшин и Е.Ф.Друй (53) 681.333(088.8) (56) Авторское свидетельство СССР
М 862145, кл. G 06 F 15/20, 1980.
Авторское свидетельство СССР
М 1587535, кл. G 06 F 15/20, 1988. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ
ПАРАМЕТРОВ ГРАФА (57) Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе со взвешенными вершинами. Целью изобретения является расширение функциональных воэможностей устройства эа счет определения величин
Ы2, 1683036 Al максимальных путей в стоки графа со взвешенными вершинами. Предлагаемое устройство содержит генератор 1 серии импульсов, многоканальный таймер 2, блок
3 определения стоков, блок 4 задания матрицы смежности, вход 5 пуска устройства и выходы 6 веса пути из вершин в наиболее удаленные от них стоки графа устройства.
Перед началом работы в блок 4 задания матрицы смежности заносят информацию о топологии графа, каналы многоканального таймера загружают числами, пропорциональными весам вершин графа. После подачи на вход 5 пуска устройства импульса уровня логической единицы генератор 1 формирует серию импульсов, количество которых совпадает с полной емкостью канала таймера 3
2, при этом на его информационных выходах формируют искомые веса путей. 4 ил.
1683036
Изобретение относится к вычислительной технике и может быть использовано для анализа путей в графе со взвешенными вершинами.
Целью изобретения является расширение функциональных воэможностей устройства за счет определения величин максимальных путей в стоки графа со взвешенными вершинами.
На фиг.1 представлена функциональная схема устройства; на фиг.2 — функциональная схема блока определения стоков; на фиг.3 — функциональная схема блока задания матрицы смежности; на фиг.4 — функциональная схема многоканального таймера, Устройство содержит генератор 1 серии импульсов, многоканальный таймер 2, блок
3 определения стоков, блок 4 задания матрицы смежности, вход 5 пуска устройства и выходы 6 веса пути из вершин в наиболее удаленные от них стоки графа устройства.
На схеме (фиг.2) обозначены группа элементов ИЛИ-НЕ 7, входы 8 признаков наличия дуг и выходы 9 признаков принадлежности вершин массиву стоков графа, причем вход 8 признака наличия (К,M)-й дуги блока определения стоков (К= 1,...,В;
M=1,...,В, где  — количество вершин в графе) подключен к К-му входу M-го элемента
ИЛИ-НЕ 7 группы, выход которого является выходом 9 признака принадлежности М-й вершины массиву стоков графа.
На фиг.3 цифровые обозначения представляют матрицу из В х В триггеров 10, причем вход 11 задания признака наличия дуги из M-й в К-ю вершину графа блока 4 задания матрицы смежности подключен к входу установки в единицу К-го триггера 10
M-й строки матрицы, выход которого является выходом 12 признака наличия (К,М)-й дуги блока 4 задания матрицы смежности, вход 13 удаления дуг, заходящих в К-ю вершину, которого подключен к входам установки в "0" всех триггеров 10 К-го столбца матрицы.
На фиг.4 цифровые обозначения представляют группу из В,счетчиков.14, причем вход 15 разрешения работы M-го канала многоканального таймера 2 подключен к входу разрешения счета M-ro счетчика.14 группы, информационный выход которого является
M-ым информационным выходом 16 многоканального таймера 2, вычитающий вход 17 которого подключен к вычитающим входам всех счетчиков 14 группы, выход признака переполнения M-ro из которых является выходом
18 признака переполнения M-ro канала многоканального таймера 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, на входах
1683036
Ж1 . @g ф2/
71
М
7р
- 2
Фиг.2
Uz а а 4
° в ° 3
° °
° °
° Э е ° а ° ° а
° °
-а Ф ° ° °
° ° в ° в °
° °
° °
%в )2 ð .Юуу %2 gg
ФигЗ разрешения счета которых присутствует потенциал уровня логической "1", работают на вычитание, при переходе через "0" формируют сигнал переполнения и продолжают счет от своей полной емкости.
Фо р мул а и зоб рете н и я
Устройство для исследования параметров графа, содержащее блок задания матрицы смежности и генератор серии импульсов, вход пуска которого является входом пуска устройства, о т л и ч а ю щ е ес я тем, что, с целью расширения функциональных возможностей устройства за счет определения величин максимальных путей в стоки графа со взвешенными вершинами, в него введены блок определения стоков и многоканальный таймер., причем тактовый выход генератора серии импульсов подключен к вычитающему входу многоканального таймера, выход признака переполнения Кго канала которого (К = 1, „., В, где В—
5 количество вершин в графе) подключен к входу удаления дуг, заходящих в К-ную вер. шину блока задания матрицы смежности, выход признака, наличия (К,M)-й дуги которого (M = 1,...,В) подключен к одноименному
10 входу блока определения стоков, выход признака принадлежности M-й вершины массиву стоков которого подключен к входу разрешения работы М-го канала многока15 нального таймера, M-й информационный выход которого является выходом массы пути из M-й вершины в наиболее удаленный от нее сток графа устройства.
Ь 88! 888
1683036
181 !БА 182 762
788 168
° ° ° е ° е
1Ф
:- Ф
Составитель А,Мишин
Техред М.Моргентал Корректор A,Îñàóëåíêo
Редактор M,Áëàíàð
Производственно-издательский комбинат "Патент", r, Ужгород, ул.Гагарина, 101
Заказ 3415 Тираж Подписное
ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, Раушская наб., 4/5
