Устройство для исследования графов Советский патент 1986 года по МПК G06G7/122 

112

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

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

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

Устройство содержит триггер 1, ге нератор 2 импульсов, первый 3 и второй 4 элементы И, первый 5 и второй 6 переключатель и источник 7 опорно го напряжения, группу элементов НЕ 8, первую группу элементов ИЛИ 9, первую группу ключей 10, матрицу I1 моделей ребер I2, каждая из которых образована элементом И 13 и счетчиком 14, вторую группу ключей 15, вторую группу элементов ИЛИ 16, мультиплексор . I 7, третью группу элементов ИЛИ 18, группу элементов И 19, элемент ИЛИ 20, блок ключей 21, суммирующий счетчик 22 и вычитающий счетчик 23. Модели ребер 12 имеют полюса 24-28. Кроме того, на фиг.1 и 2 обозначены третий 29 и .четвертый 30 переключатели.

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

5

0

5

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

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

Пусть первым переполнится счетчик 14,2, тогда сигнал переполнения с его выхода через полюс 25, элементы ИЛИ 9 НЕ 8 , ключ 15 и полюс 28 поступает на входы разрешения счета счетчиков 14 второго столбца . матрицы 11 в виде нулевого потенциала и снимает разрешение на дальнейший счет ими импульсов (блокирует дальнейшую работу этих счетчиков). Кроме того, сигнал переполнения с выхода элемента ИЛИ 9 поступает на управляющий вход ключа 102 и открывает его для прохождения импульсов генератора 2, так что далее счет импульсов осуществляют счетчики 14 первой и второй строк матри1ц 1 1 1 (кроме счетчиков 14 , 1А ) . При переполнении любог о счетчика 14 он 5 вьщает сигнал переполнения. Далее

работа устройства протекает аналогично рассмотренному до того момента, когда переполняется какой-либо счетчик 14 и-го столбца матрицы П. Тогда сигнал переполнения через элемент ИЛИ 9, и первую секцию переключателя 6;, поступает на единичный выход триггера 1 и переводит его в единичное состояние, в результате чего закрывается элемент И 3 и открывается элемент И 4 для прохождения последующих импульсов генератора 2. Счетчик 22 прекращает счет импульсов и показывает длину кратчайшего пути.

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

. Пусть в и -м стобце матрицы 1 переполняется счетчик , и его сигнал переполнения поступает на пер0

0

5

0

5

вый вход элемента И 13

и- 1П

модели ребра 2,.,„. Кроме того, сигнал пере-.

.полнения этого же счетчика 14„ проходит через полюс 25, элемент ИЛИ 9j, , первую секцию переключателя 6 и вторую секцию переключателя 30 на и -и вход элемента Ш1И 16„ , а с его выхода через полюс 24 на вторые входы элементов И 13 И-го столбца матрицы 1I, открьшая элементы И 13 для прохождения сигналов, поступающих на их первые входы. „Тогда потенциал переполнения с выхода счетчика 14„. поступает через элемент И 13j,., и по люс 26, во-первых на (п-1)-й выход и -и группы выходов номеров ребер устройства идентифицируя ребро 12„, вошедшее в кратчайший маршрут; во-вторых, на соответствующий вход и -и группы входов мультиплексора 17; в-третьих, на и-й вход элемента ИЛИ 16,. Единич- потенциал с выхода элемента. ИЛИ 16„, через полюс 24 поступает на вторые входы элементов И 13 (n-l)-ro столбца матрицы 11, открьгеая их для прохождения потенциала переполнения с того счетчика 14 данного (п-1)-го столбца матрицы 1 1, который находится в состоянии переполнения. Далее процесс протекает аналогично, и, если, например, в (п-1)-м столбце переполняется счетчик 14,„,, то через полюс 26 потенциал переполнения поступает, во-первых на соответствующий выход из числа (п-1)-й группы выходов номеров ребер устройства, идентифицируя вошедшее в кратчайший маршрут ребро .; во-вторых, на соответствующий вход из числа (п-1)-й группы входов мультиплексора 17 (поступление потенциала на (п-1)-й вход элемента ИЛИ 16.1 значения не имеет, т.к. на первом столбце матрицы 11 нет переполнившихся счетственного

графе.

кратчайшего маршрута в

10

15

20

25

30

35

40

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

чиков 14). В результате единичные по- ментов И 13 соответствующих столбтенциалы присутствуют лишь на тех выходах устройства, которые соответствуют ребрам, вошедшим в кратчайший маршрут. Однако найденное решение является правильным лишь в том случае, если ни в одном столбце матрицы 11 не оказалось двух (или более) переполнившихся счетчиков 14; в противном случае идентифицированная со-. вокупность ребер относится уже не к одному, а к двум (или более) кратчайшим матршрутам. Дальнейшая рабо та устройства имеет целью выяцов матрицы 11. Каждый раз, когда в каком-либо столбце матрицы 11 ока зьтаются переполненными два (или более) счетчика 14, единичный потен

50 циал появляется на двух (или более) выходах мультиплексора 17 и, следов тельно, на выходе элемента ИЛИ 20. Блок 21 открывается, и код (номер) данного столбца матрицы или номер

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

вить наличие или отсутствие един- всех столбцов матрицы 11 сигнал с

ственного

графе.

кратчайшего маршрута в

0

5

0

5

0

5

0

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

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

5

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

В устройстве обеспечивается повышение точности получаемого решения путем установления факта единственности нли неединственности найденного маршрута: непоступление ни одного кода на выход номеров вершин устройства свидетельствует о наличии в графе единственного кратчайше

блок ключей, суммирующий и вычитающий счетчики, причем в каждой модели ребер выход счетчика подключен к первому входу элемента И, вторые 5 входы элементов И всех моделей ре- рер каждого J-го столбца матрицы объединены и подключены к выходу jro элемента ИЛИ второй группы, выход элемента И каждой i-и модели ребра каждого j-го столбца матрицы подключен к т-му входу j -и группы входов с мультиплексора, которые являются группой выходов j-го ребра исследуемого графа устройства, выход

20

маршрута. Если же на этот выход пос-

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

к л-му входу 1 -го элемента ИЛИ второй группы, вход запуска генератора импульсов является пусковым входом устройства, .вьпсод переполнения вычитающего счетчика подключен к входу останова генератора импульсов и явля ется выходом окончания работы устрой25 ства, выход генератора импульсов соединен с первыми входами первого и вфорого элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам триггеможет быть найден путем поочередного оставления в состоянии переполнения каждого из одновременно переполнившихся счетчиков 14 данного столбца.

40

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

Устройство для исследования графов , содержащее матрицу п х п (где и - число вершин графа) моделей ребер, каждая модель ребра содержит счетчик и элемент И, кроме этого уст ройство содержит первую группу элементов HJIIi, группу элементов И, триггер и генератор импульсов, причем выход i-ro счетчика j-ro столбца матрицы моделей ребер подключен к i-му входу j-ro элемента ИЛИ первой группы (где 1 « 1 ,ni j l,n)j отличающееся тем, что.

3Q pa, выход первого элемента И соединен с информационными входами ключей первой группы, подвижным контактом первого переключателя и счетным входом суммирующего счетчика, счетные входы счетчиков всех моделей ребер каждой 1-и строки матрицы объединены, подключены к выходу i-ro ключа первой группы к 1-му неподвижному . контакту первого переключателя, выход каждого 1-го элемента ИЛИ первой

группы соединен со входом i -го элемента НЕ группы, с управляющим входом V-ro ключа первой группы и с т-м неподвижным контактом второго переключателя, подвижньш контакт которого подключен ко входу установки в единицу триггера и подвижному контакту третьего переключателя, каждый 1-й неподвижный контакт кото- с целью повышения точности и расшире- Q рого подключен к i -му входу f-го функциональных возможностей пу элемента И.ПИ второй группы, выход тем определения кратчайшего маршрута между двумя заданными вершинамИз в него введены вторая и третья.группы элементов ИЛИ, четыре переключателя, первая и вторая группы ключей, группа элементов НЕ, источник опорного напряжения, первый и второй элементы И, элемент ИЛИ, мультиплексор.

каждого 1 -го элемента НЕ группы соединен с информационным входом 1-го ключа второй группы, управляю- ,щий вход которого подключен к i-му неподвижному контакту четвертого переключателя, подвижный контакт которого соединен с выходом-источника опорного напряжения, выход кажблок ключей, суммирующий и вычитающий счетчики, причем в каждой модели ребер выход счетчика подключен к первому входу элемента И, вторые входы элементов И всех моделей ре- рер каждого J-го столбца матрицы объединены и подключены к выходу jro элемента ИЛИ второй группы, выход элемента И каждой i-и модели ребра каждого j-го столбца матрицы подключен к т-му входу j -и группы входов с мультиплексора, которые являются группой выходов j-го ребра исследуемого графа устройства, выход

элемента И каждой i-й модели ребра .каждой j-й строки матрицы подключен

элемента И каждой i-й модели ребра каждой j-й строки матрицы подключен

к л-му входу 1 -го элемента ИЛИ второй группы, вход запуска генератора импульсов является пусковым входом устройства, .вьпсод переполнения вычитающего счетчика подключен к входу останова генератора импульсов и является выходом окончания работы устройства, выход генератора импульсов соединен с первыми входами первого и вфорого элементов И, вторые входы которых подключены соответственно к инверсному и прямому выходам триггеpa, выход первого элемента И соединен с информационными входами ключей первой группы, подвижным контактом первого переключателя и счетным вхоом суммирующего счетчика, счетные входы счетчиков всех моделей ребер каждой 1-и строки матрицы объединены, подключены к выходу i-ro ключа первой группы к 1-му неподвижному . контакту первого переключателя, вы40

ход каждого 1-го элемента ИЛИ первой

группы соединен со входом i -го элемента НЕ группы, с управляющим входом V-ro ключа первой группы и с т-м неподвижным контактом второго переключателя, подвижньш контакт которого подключен ко входу установки в единицу триггера и подвижному контакту третьего переключателя каждый 1-й неподвижный контакт кото- Q рого подключен к i -му входу f-го элемента И.ПИ второй группы, выход

группы соединен со входом i -го элемента НЕ группы, с управляющим входом V-ro ключа первой группы и с т-м неподвижным контактом второго переключателя, подвижньш контакт которого подключен ко входу установки в единицу триггера и подвижному контакту третьего переключателя каждый 1-й неподвижный контакт кото- Q рого подключен к i -му входу f-го элемента И.ПИ второй группы, выход

каждого 1 -го элемента НЕ группы соединен с информационным входом 1-го ключа второй группы, управляю- ,щий вход которого подключен к i-му неподвижному контакту четвертого переключателя, подвижный контакт которого соединен с выходом-источника опорного напряжения, выход каж7I

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

ройства, а управляющий вход блока ключей соединен с выходом элемента ИЛИ, каждый 1 -и вход которого подключен к выходу 1-го элемента И груп- 5 пы, первый вход соединен с выходом 7 -го элемента ИЛИ третьей группы, i-й (,п) выход мультиплексора подключен к второму входу 1 -го элемента И группы и входам j-x (,n, 0 кроме j L) элементов ИЛИ третьей группы.

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

5 В Г

Я

в s г

Д Е

Ж 3 И

Г