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

 

Изобретение относится к области вычислительной техники и может быть использовано прн решении на графах задач нахождения кратчайших маршрутов между двумя вершинами. Целью изобретения является расширение функциональных возможностей устройства за счет определения длины кратчайшего маршрута между двумя вершинами графа, а также образую- ,щих его ребер и повышение точности получаемого решения при определении кратчайшего маршрута. Поставленная цель достигается тем, что в извест- iHoe устройство, содержащее матрицу п X п (где и - число вершин графа) моделей ребер, причем каждая модель сребра состоит из элемента И и счетчика , первую группу элементов ИЛИ, группу элементов И, триггер и генератор импульсов, введены четыре переключателя, две группы элементов ШШ, две группы ключей, группа элементов НЕ, источник опорного напряжения, два элемента И, элемент ШШ, мультиплексор , блок ключей, суммирующий и вычитаниций счетчики. В устройстве идентифицируются ребра и вершины исследуемого графа, вошедшие в кратчайший путь между двумя вершинами. 1 ил. о б (Л to 00 о 00 00 Jik

СОЮЗ СО8ЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК др 4 С 06 F 15/20

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ЙО;-.. „

ОПИСАНИЕ ИЗОБРЕТЕНИЯ И,.

Н A BTOPCHOMY СВИДЕТЕЛЬСТВУ Rt

--". (21) 3946254/24-24 (22) 19.08.85 (46) 30.12.86.Бюл. и 48 (72) С.К.Михайловский и В.А.Шингиреев (53) 681.333 (088.8) (56) Авторское свидетельство СССР

Ф 485451, кл. G 06 F 15/20, 1971.

Авторское свидетельство СССР

У 525954, кл. G 06 F 15/20, 1974. . (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к области вычислительной техники и может быть использовано при решении на графах задач нахождения кратчайших маршрутов между двумя вершинами.

Целью изобретения является расширение функциональных возможностей устройства за счет определения длины кратчайпего маршрута между двумя.Л0„„1280384 А 1 вершинами графа, а также образую,щих его ребер и повышение точности получаемого решения при определении кратчайшего марпрута. Поставленная цель достигается тем, что в извест ное устройство, содержащее матрицу n х и (где И вЂ” число вершин графа) моделей ребер, причем каждая модель ребра состоит из элемента И и счетчика, первую группу элементов ИЛИ, группу элементов И, триггер и генератор импульсов, введены четыре переключателя, две группы элементов

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

1 ил.

1280384

Изобретение относится к вычисли— тельной технике и может быть использовано при решении на графах задач нахождения кратчайших маршрутон между двумя вершинами.

Цель изобретения — расширение функциональных возможностей устройства путем определения длины кратчайшего маршрута между двумя вершина" ми графа, а также образующих его ребер и повышения точности получаемого решения при определении кратчайшего маршрута.

На фиг.! и 2 показана структурная схема устройства.

Устройство содержит триггер 1, re нератор 2 импульсов, первый 3 и второй 4 элементы И, первый 5 и второй

6 переключатель и источник 7 опорного напряжения, группу элементов НЕ

8, первую группу элементов ИЛИ 9, первую группу ключей 10, матрицу 11 моделей ребер 12, каждая из которых образована элементом И 13 и счетчиком 14, вторую группу ключей !5, вторую группу элементов ИЛИ 16, мультиплексор 17, третью группу элементов ИЛИ 18, группу элементов И 19, элемент ИЛИ 20, блок ключей 21, суммирующий счетчик 22 и вычитающий счетчик 23. Модели ребер 12 имеют полюса 24-28. Кроме того, на фиг.! и 2 обозначены третий 29 и .четвертый 30 переключатели. !

Первоначально в счетчик 23 заносится (n+1) импульсов, а в счетчик

14 каждой модели 12 - количество импульсов, дополняющее нес ребра до полной емкости счетчика. Триггер 1 и счетчик 22 обнуляются, Переключатели 5 и 29 устанавливаются в положение, соответ ствующее выбранной начальной вершине, а переключатели 6 и 30 — в положение, соответствующее выбранной конечной вершине (в качестве начальной вершины выбрана первая, а в качестве конечной — n-я вершины граAa). Ключи 10,21 закрыты, ключи 15 открыты, за исключением ключа на управляющий вход которого подается единичный потенциал источника 7 че рез переключатель 29. Соответственно на выходах всех ключей 15 присутствуют единичные потенциалы1 поступающие на управляющие входы счетчиков 14 как сигналы разрешения

Идентификация ребер кратчайшего маршрута осуществляется следующим образом.

Пусть в t1 â€,м стобце матрицы 11 переполняется счетчик 4 „ п, и его

17- сигнал переполнения поступает на первый вход элемента И 13 модели ребра 12 Ä, . Кроме того, сигнал пере-. счета, однако на выходе того ключа

15 ключ 15, на управляющий вход которого подан единичный сигнал, присутствует нулевой потенциал, не разрешающий (блокирующий) счет имцульсов счетчиками 14 столбца матрицы ll соответствующего выбранной начальной вершине графа.

При подаче пускового сигнала на вход устройства импульсы генератора

2 проходят через элемент И 3 открытый единичным потенциалом с инверсного выхода триггера 1) и переключатель 5 на счетные входы счетчиков 14 первой строки матрицы 11.

Пусть первым переполнится счетчик 14,, тогда сигнал переполнения ! с его выхода через полюс 25, элементы ИЛИ 9 НЕ 8, ключ 15 и полюс

28 поступает на входы разрешения счета счетчиков 14 второго столбца матрицы ll в виде нулевого потенциала и снимает разрешение на дальнейший счет ими импульсов блокирует дальнейшую работу этих счетчиков).

Кроме того, сигнал переполнения с выхода элемента ИЛИ 9 поступает на управляющий вход ключа 10 и открывает его для прохождения импульсов генератора 2, так что далее счет импульсон осуществляют счетчики 14 первой и второй строк матрицы 11 (кроме счетчиков 14 >, 14 „ ) . При ! I переполнении любого счетчика 14 он

З5 выдает сигнал переполнения. Далее работа устройства протекает аналогично рассмотренному до того момента, когда переполняется какой-либо счетчик 14 и -ro столбца матрицы ll. Тогда сигнал переполнения через элемент ИЛИ 9„, и первую секцию переключателя 6„ поступает на единичный выход триггера 1 и переводит его н единичное состояние, в результате

45 чего закрывается элемент И 3 и открывается элемент И 4 для прохождения последующих импульсов генератора 2. Счетчик 22 прекращает счет импульсов и показывает длину кратчайшего пути.

1280384 полнения этого же счетчика.14„, „

i d проходит через полюс 25, элемент

ИЛИ 9„, первую секцию переключателя 6 и вторую секцию переключателя

30 на и -й вход элемента ИЛИ 16„, а с его выхода через полюс 24 на вторые входы элементов И 13 н -го столбца матрицы 11, открывая элементы

И 13 для прохождения сигналов, поступающих на их первые входы. Тогда потенциал переполнения с выхода счетчика 14„„ „поступает через эле-! мент И 13„ „„ и полюс 26, во-первых на (и-1)-й выход и -й группы выходов номеров ребер устройства идентифиf5 цируя ребро 12„ „ „, вошедшее в кратчайший маршрут; во-вторых, на соответствующий вход l1 -й группы входов мультиплексора 17; в-третьих, на

20 и-й вход элемента ИЛИ 16„,. Единичный потенциал с выхода элемента.

ИЛИ 16„ „через полюс 24 поступает на вторые входы элементов И 13 (n-1)-го столбца матрицы 11, открывая их для прохождения потенциала переполнения с того счетчика 14 данного (n-1)-го столбца матрицы 11, который находится в состоянии переполнения. Далее процесс протекает аналогично, и, если, например, в (n-1)-м столбце переполняется счетчик 14, „ „, то через

itl- полюс 26 потенциал переполнения поступает, во-первых на соответствующий выход из числа (n-1)-й группы выходов номеров ребер устройства, идентифицируя вошедшее в кратчайший маршрут ребро 12„ „„; во-вторых,на соответствующий вход из числа (n-1)-й группы входов мультиплексора 17 40 (поступление потенциала íà (n-1)-й вход элемента ИЛИ 16.1 значения не имеет, т.к. на первом столбце матрицы 11 нет переполнившихся счетчиков 14). В результате единичные по- 45 тенциалы присутствуют лишь на тех выходах устройства, которые соответствуют ребрам, вошедшим в кратчайший маршрут. Однако найденное решение является правильным лишь в том случае, если ни в одном столбце матрицы 1! не оказалось . двух (или более) переполнившихся счетчиков 14; в противном случае идентифицированная со-. вокупность ребер относится уже не к одному, а к двум (или более) кратчайшим матршрутам. Дальнейшая рабо та устройства имеет целью выявить наличие или отсутствие единственного кратчайшего маршрута в графе °

Импульсы генератора 2 через открывшийся элемент И 4 поступают на вход вычитающего счетчика 23. При поступлении первого импульса счетчик 23 выдает на разрядный выход код (адрес) и -й вершины графа, во-первых, на информационный вход блока ключей 21; во-вторых, на адресный вход мультиплексора 17, который . подключает на свои выходы п-ю группу входов (первый вход и-й группы входов на первый выход, второй вход п-й группы входов — на второй выход и т.д.). .В результате на выходы мультиплексора 17 поступает также число единичных потенциалов, которое соответствует числу переполнившихся счетчиков в и-м столбце матрицы 11. На выходе элемента ИЛИ 20 единичный потенциал появляется лишь в случае появления на выходах мультиплексора 17 одновременно двух единичных потенциалов. Действительно, если единичный потенциал присутствует на одном (любом) выходе мультиплексора 17, то ни через один элемент И 19 он не пройдет; при наличии жЕ,единичного потенциала на двух (или более) выходах мультиплексора 17 на обоих входах хотя бы одного элемента И 19 появляется единичный потенциал, который проходит через элемент ИЛИ 20 на управляющий вход блока 21. В процессе прохождения импульсов генератора 2 на вход счетчика 23 он последовательно выдает на свой разрядный выход коды и, п-l, п-2,... вершин графа на адресный вход мультиплексора 17, который каждый раз подключает к вы1 ходам соответствующую группу своих входов и, следовательно, выходы элементов И 13 соответствующих столбцов матрицы 11. Каждый раз, когда в каком-либо столбце матрицы lt оказываются переполненными два (или более) счетчика 14, единичный потенциал появляется на двух (или более) выходах мультиплексора 17 и, следовательно, на выходе элемента ИЛИ 20.

Блок 21 открывается, и код (номер) данного столбца матрицы или номер вершины графа) с разрядного выхода счетчика 23 поступает на выход номеров вершин устройства для регистрации (индикации). После просмотра всех столбцов матрицы ll сигнал с

1280384 выхода переполнения счетчика 23 поступает на вход останова генератора 2, прекращая работу устройства, и на выход окончания работы устройства.

В устройстве обеспечивается повышение точности получаемого решения путем установления факта единственности или неединственности найденного маршрута: непоступление ни одного кода на выход номеров вершин устройства свидетельствует о наличии в графе единственного кратчайшего маршрута. Если же на этот выход поступил один или более кодов, то оператор может воспользоваться ими для последующего нахождения ребер всех (или хотя бы одного) кратчайших маршрутов, используя топологию графа (например, его графическое изображение). Если же на выход блока 21 поступил только один код, то есть лишь в одном столбце ь1атрицы 11 имеется более одного переполнившегося счетчика 14, то число кратчайших маршрутов равно числу переполнившихся счетчиков 14 в данном столбце матрицы ll. Каждый из таких маршрутов может быть найден путем поочередного оставления в состоянии переполнения каждого иэ одновременно переполнившихся счетчиков 14 данного столбца.

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

Устройство для исследования графов, содержащее матрицу и х и (где

1 — число вершин графа) моделей ребер, каждая модель ребра содержит счетчик и элемент И, кроме этого уст ройство содержит первую группу элементов ИЛИ, группу элементов И, триг. гер и генератор импульсов, причем выход i"ro счетчика j-ro столбца матрицы моделей ребер подключен к

i-му входу 1-ro элемента ИЛИ первой .группы (где i l,n; j - "l,n), о т л и ч а ю щ е е с я тем, что, с целью повышения точности и расширения функциональных возможностей путем определения кратчайшего маршрута между двумя заданными вершинами, в него введены вторая и третья. группы элементов ИЛИ, четыре переключателя, первая и вторая группы ключей, группа элементов НЕ, источник опорI ного напряжения, первый и второй элементы И, элемент ИЛИ, мультиплексор, t

10 15

20 блок ключей, суммирующий и вычитающий счетчики, причем в каждой модели ребер выход счетчика подключен к первому входу элемента И, вторые входы элементов И всех моделей реpep каждого J -ro столбца матрицы объединены и подключены к выходу

J-го элемента ИЛИ второй группы, выход элемента И каждой 1 -й модели ребра каждого J -ro столбца матрицы подключен к l му входу 1 -й группы входов с мультиплексора, которые являются группой выходов 1 -ro ребра исследуемого графа устройства, выход элемента И каждой 1-й модели ребра каждой -й строки матрицы подключен к 1-му входу 1 -ro элемента ИЛИ вто1 рой группы, вход запуска генератора импульсов является пусковым входом устройства,,выход переполнения вычитающего счетчика подключен к входу останова генератора импульсов и является выходом окончания работы устрой25 ства, выход генератора импульсов соединен с первыми входами первого и второго элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам триггера, выход первого элемента И соеди. нен с информационными входами ключей первой группы, подвижным контактом первого переключателя и счетным входом суммирующего счетчика, счетные входы счетчиков всех моделей ребер каждой 1 -й строки матрицы объединены, подключены к выходу 1-ro ключа первой группы к 1 -му неподвижному контакту первого переключателя, вы40 ход каждого i-го элемента ИЛИ первой группы соединен со входом 1 -го элемента НЕ группы, c У:.правляющим вхоt дом 1-го ключа первой группы и с -м неподвижным контактом второго переключателя, подвижный контакт которого подключен ко входу установки в единицу триггера и подвижному контакту третьего переключателя, Ф каждый 1-й неподвижный контакт кото50 рого подключен к -му входу 1 --го элемента ИЛИ второй группы, выход каждого 1 -го элемента НЕ группы соединен с информационным входом

q --го ключа второй группы, управляю55 щий вход которого подключен к 1-му неподвижному контакту четвертого переключателя, подвижный контакт которого соединен с выходом источника опорного напряжения, выход каж1280384

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

ИЛИ, каждый -й вход которого подключен к выходу -ro элемента И групгп|, первый вход .соединен с выходом

-ro элемента ИЛИ третьей группы, i — и (i=1 и) выход мультиплексора подключен к второму входу i -го элемента И группы и входам j --x (j=l,ï, кроме j = 4) элементов ИЛИ третьей группы.

1280384

Составитель Т. Сапунова

Редактор Л. Пчелинская Техред Л. Олейник Корректор. N, Пожо

Закаэ 7051/42 Тираж 671

ВНИИПИ Государственного комитета СССР по делам иэобретений и открытий

113035, Москва, Ж-35, Раушская наб., д.4/5

Подписное

Проиэводственно-полиграфическое предприятие, г.ужгород, ул. Проектная,4