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

(511 4 С 06 Р 15/20 ОПИСАНИЕ ИЗОБРЕТЕНИ ТВУ 3946254/24-2419.08.8530.12.86.Бюл. УС.К.Михайловский(21) (22) (46) (72) В,А,Ши ИЛИ ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ АВТОРСКОМУ СВИДЕТ(56) Авторское свидетельство СССУ 485451, кл. С 06 Р 15/20, 1971Авторское свидетельство СССРУ 525954, кл. С 06 Р 15/20, 1974(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯГРАФОВ(57) Изобретение относится к области вычислительной техники и можетбыть использовано при решении награфах задач нахождения кратчайшихмаршрутов между двумя вершинами,Целью изобретения является расширение функциональных возможностей усройства за счет определения длиныкратчайпего маршрута между двумя вершинами графа, а также образую,щих его ребер и повышение точности получаемого решения при определениикратчайшего марпрута. Поставленная цель достигается тем, что в известное устройство, содержащее матрицу и х и (где и - число вершин графа) моделей ребер, причем каждая модель ребра состоит из элемента И и счетчика, первую группу элементов ИЛИ, группу элементов И, триггер и генератор импульсов, введены четыре переключателя, две группы элементов, две группы ключей, группа элементов НЕ, источник опорного напряжения,с два элемента И, элемент ИЛИ, мульти- р плексор, блок ключей, суммирующий и вычитающий счетчики. В устройстве идентифицируются ребра и вершины С исследуемого графа, вошедшие в кратчайший путь между двумя вершинами. сИзобретение относится к вычисли -тельной технике и может быть использовано при решении на графах задачнахождения кратчайших маршрутон между двумя вершинами,Цель изобретения - расширениефункциональных возможностей устройства путем определения длины кратчайшего маршрута между двумя вершина"ми графа, а также образующих его ребер и повышения точности получаемогорешения при определении кратчайшегомаршрута,На фиг.и 2 показана структурная схема устройства.Устройство содержит триггер 1, ге нератор 2 импульсов, первый 3 и второй 4 элементы И, первый 5 и второй 6 переключатель и источник 7 опорного напряжения, группу элементов НЕ 8, первую группу элементов ИЛИ 9, первую группу ключей 1 О, матрицу 11 моделей ребер 12, каждая из которых образована элементом И 13 и счетчиком 14, вторую группу ключей 5, вторую группу элементов ИЛИ 16, муль. типлексор 17, третью группу элементов ИЛИ 18, группу элементов И 19, элемент ИЛИ 20, блок ключей 21, суммирующий счетчик 22 и вычитающий счетчик 23. Модели ребер 12 имеют полюса 24-28. Кроме того, на фиг, и 2 обозначены третий 29 и .четвертый 30 переключатели.Первоначально в счетчик 23 заносится (и+1) импульсов, а в счетчик 14 каждой модели 12 - количество импульсов, дополняющее нес ребра до полной емкости счетчика. Триггер 1 и счетчик 22 обнуляются, Переключатели 5 и 29 устанавливаются в положение, соответ ствующее выбранной начальной вершине, а переключатели 6 и 30 - в положение, соответствующее выбранной конечной вершине (в качестве начальной вершины выбрана первая, а в качестве конечной - ц-я вершины графа). Ключи 10,21 закрыты, ключи 15 открыты, за исключением ключа на управляющий вход которого подается единичный потенциал источника 7 через переключатель 29. Соответственно на выходах всех ключей 15 присутствуют единичные потенциалы 1 поступающие на управляющие входы счетчиков 14 как сигналы разрешения55 Идентификация ребер кратчайшего маршрута осуществляется следующим образом.Пусть в И в ,м стобце матрицы 11 переполняется счетчик 4п, и его11-сигнал переполнения поступает на первый вход элемента И 13 модели ребра 2 , . Кроме того, сигнал пере-,счета, однако на выходе того ключа15 ключ 15, на управляющий входкоторого подан единичный сигнал,присутствует нулевой потенциал, неразрешающий (блокирующий) счет имцульсов счетчиками 14 столбца матрицы 11, соответствующего выбранной начальной вершине графа.При подаче пускового сигнала навход устройства импульсы генератора2 проходят через элемент И 3открытый единичным потенциалом с инверсного выхода триггера 1) и пере "ключатель 5 на счетные входы счетчиков 14 первой строки матрицы 11,Пусть первым переполнится счетчик 14, , тогда сигнал переполненияс его выхода через полюс 25, элементы ИЛИ 9 НЕ 8 , ключ 15 и полюс28 поступает на входы разрешениясчета счетчиков 14 второго столбцаматрицы 11 в виде нулевого потенциала и снимает разрешение на дальнейший счет ими импульсов блокирует дальнейшую работу этих счетчиков).Кроме того, сигнал переполнения свыхода элемента ИЛИ 9 поступаетна управляющий вход ключа 10 иоткрывает его для прохождения импульсов генератора 2, так что далее счетимпульсон осуществляют счетчики 14первой и второй строк матрицы 1(кроме счетчиков 14 , 14) . Припереполнении любого счетчика 14 он 35 выдает сигнал переполнения. Далееработа устройства протекает аналогич. но рассмотренному до того момента,когда переполняется какой-либо счетчик 14 и -го столбца матрицы 11, Тог 4 О да сигнал переполнения через элемент ИЛИ 9, и первую секцию переключателя 6 поступает на единичныйвыход триггера 1 и переводит его нединичное состояние, в результате 45 чего закрывается элемент И 3 и Открывается элемент И 4 для прохождения последующих импульсов генератора 2. Счетчик 22 прекращает счет импульсов и показывает длину кратчайшего пути.полнения этого же счетчика.14,проходит через полюс 25, элемент ИЛИ 9 , первую секцию переключателя 6 и вторую секцию переключателя 30 на и -й вход элемента ИЛИ 16 , а с его выхода через полюс 24 на вторые входы элементов И 13 И -го столбца матрицы 11, открывая элементы И 13 для прохождения сигналов, поступающих на их первые входы. Тогда потенциал переполнения с выхода счетчика 14поступает через элемент И 13и полюс 26, во-первых на (и)-й выход и -й группы выходов номеров ребер устройства идентифи 15 цируя ребро 12, вошедшее в кратчайший маршрут; во-вторых, на соответствующий вход и -й группы входов мультиплексора 17; в-третьих, наго и-й вход элемента ИЛИ 16,. Единичный потенциал с выхода элемента. ИЛИ 16 через полюс 24 поступает на вторые входы элементов И 13 (и)го столбца матрицы 11, открывая их дляпрохождения потенциала переполненияс того счетчика 14 данного (и)-гостолбца матрицы 11, который находитсяв состоянии переполнения. Далее процесс протекает аналогично, и, если,например, в (п)-м столбце переполняется счетчик 14,, то через полюс 26 потенциал переполнения поступает, во-первых на соответствующий выход из числа (и)-й группы выходов номеров ребер устройства, идентифицируя вошедшее в кратчайший маршрут ребро 12; во-вторых,на соответствующий вход из числа (и)-й группы входов мультиплексора 17 4 О (поступление потенциала на (и)-й вход элемента ИЛИ 16.1 значения не имеет, т.к. на первом столбце матрицы 11 нет переполнившихся счетчиков 14). В результате единичные по тенциалы присутствуют лишь на тех выходах устройства, которые соответствуют ребрам, вошедшим в кратчайший маршрут. Однако найденное решение является правильным лишь в том случае, если ни в одном столбце матрицы 1 не оказалось двух (или более) переполнившихся счетчиков 14; в противном случае идентифицированная со-. вокупность ребер относится уже не к одному, а к двум (или более) кратчайшим матршрутам, Дальнейшая рабо та устройства имеет целью выявить нащщие или отсутствие единственного кратчайшего маршрута вграфе. Импульсы генератора 2 через открывшийся элемент И 4 поступают на вход вычитающего счетчика 23. При поступлении первого импульса счетчик 23 выдает на разрядный выход код(адрес) И -й вершины графа, во-первых, на информационный вход блока ключей 21; во-вторых, на адресный вход мультиплексора 17, который подключает на свои выходы п-ю группу входов (первый вход и-й группы входов в . на первый выход, второй вход п-й группы входов - на второй выход и т.д.). В результате на выходы мультиплексора 17 поступает также число единичных потенциалов, которое соответствует числу переполнившихся счетчиков в и-м столбце матрицы 11. На выходе элемента ИЛИ 20 единичный потенциал появляется лишь в случае появления на выходах мультиплексора 17 одновременно двух единичных потенциалов. Действительно, если единичный потенциал присутствует на одном (любом) выходе мультиплексора 17, то ни через один элемент И 19 он не пройдет; при наличии жЕ,единичного потенциала на двух (или более) выходах мультиплексора 17 на обоих входах хотя бы одного элемента И 19 появляется единичный потенциал, который проходит через элемент ИЛИ 20 на управляющий вход блока 21. В процессе прохождения импульсов генератора 2 на вход счетчика 23 он последовательно выдает на свой разрядный выход коды и, и, п, вершин графа на адресный вход мультиплексора 17, который каждый раз подключает к выходам соответствующую группу своих входов и, следовательно, выходы элементов И 13 соответствующих столбцов матрицы 11. Каждый раз, когда в каком-либо столбце матрицы 1 оказываются переполненными два (или более) счетчика 14, единичный потенциал появляется на двух (или более) выходах мультиплексора 17 и, следова. тельно, на выходе элемента ИЛИ 20. Блок 21 открывается, и код (номер) данного столбца матрицы или номер вершины графа) с разрядного выхода счетчика 23 поступает на выход номеров вершин устройства для регист. рации (индикации). После просмотра всех столбцов матрицы 11 сигнал свыхода переполнения счетчика 23 поступает на вход останова генератора 2, прекращая работу устройства, и на выход окончания работы устрой" ства.В устройстве обеспечивается повышение точности получаемого решения путем установления факта единственности или неединственности найденного маршрута: непоступление ни одного кода на выход номеров вершин устройства свидетельствует о наличии в графе единственного кратчайшего маршрута. Если же на этот выход поступил один или более кодов, то оператор может воспользоваться ими для последующего нахождения ребер всех (или хотя бы одного) кратчайших маршрутов, используя топологию графа (например, его графическое изображение). Если же на выход блока 21 поступил только один код, то есть лишь в одном столбце Матрицы 11 имеется более одного переполнившегося счетчика 14, то число кратчайших маршрутов равно числу переполнившихся счетчиков 14 в данном столбце матрицы 11. Каждый из таких маршрутов может быть найден путем поочередного оставления в состоянии переполнения каждого иэ одновременно переполнившихся счетчиков 14 данного столбцаФормула изобретенияУстройство для исследования графов, содержащее матрицу и х и (где и - число вершин граФа) моделей ребер, каждая модель ребра содержит счетчик и элемент И, кроме этого уст ройство содержит первую группу элементов ИЛИ, группу элементов И, триг. гер и генератор импульсов, причем выход д"го счетчика -го столбца матрицы моделей ребер подключен к х-му входу 1-го элемента ИЛИ первой .группы (где д 1,п;,1 ф 1,п), о т л и ч а ю щ е е с я тем, что, с целью повышения точности и расширения функциональных возможностей путем определения кратчайшего маршрута между двумя заданными вершинами в него введены вторая и третья. группы элементов ИЛИ, четыре переключателя, первая и вторая группы ключей, группа элементов НЕ, источник опорного напряжения, первый и второй элементы И, элемент ИЛИ, мультиплексор, 5 10 15 20 блок ключей, суммирующий и вычитающий счетчики, причем в каждой модели ребер выход счетчика подключенк первому входу элемента И, вторыевходы элементов И всех моделей реДер каждого-го столбца матрицыобъединены и подключены к выходу1-го элемента ИЛИ второй группы, выход элемента И каждой 1 -й моделиребра каждого 1 -го столбца матрицыподключен к 1-му входу-й группывходов с мультиплексора, которые являются группой выходов-го ребраисследуемого графа устройства, выходэлемента И каждой 1-й модели ребракаждой-й строки матрицы подключенк 1-му входу 1 -го элемента ИЛИ второй группы, вход запуска генератораимпульсов является пусковым входомустройствавыход переполнения вычитающего счетчика подключен к входуостанова генератора импульсов и является выходом окончания работы устрой 25 ства, выход генератора импульсов соединен с первыми входами первого ивторого элементов И, вторые входы которых подключены соответственно кинверсному и прямому выходам триггера, выход первого элемента И соеди. нен с информационными входами ключейпервой группы, подвижным контактомпервого переключателя и счетным входом суммирующего счетчика, счетныевходы счетчиков всех моделей реберкаждой 1 -й строки матрицы объединены, подключены к выходу 1-го ключапервой группы к 1-му неподвижномуконтакту первого переключателя, вы ход каждого 1-го элемента ИЛИ первойгруппы соединен со входом 1 -го элемента НЕ группы, с управляющим входом 1-го ключа первой группы и с-м неподвижным контактом второгопереключателя, подвижный контакткоторого подключен ко входу установки в единицу триггера и подвижному контакту третьего переключателя,Фкаждый 1-й неподвижный контакт кото рого подключен к-му входу 1 -гоэлемента ИЛИ второй группы, выходкаждого 1 -го элемента НЕ группысоединен с информационным входомФ1 -го ключа второй группы, управляю щий вход которого подключен к 1-мунеподвижному контакту четвертогопереключателя, подвижный контакткоторого соединен с выходом источника опорного напряжения, выход каж1280384 8 дого , -го ключа второй группы подключен ко входам разрешения счетасчетчиков всех моделей ребер -хстолбцов матрицы моделей ребер, выход второго элемента И соединен сосчетным входом вычитающего счетчика,разрядный выход которого подключенк адресному входу мультиплексора иинформационному входу блока ключей,выход которого является выходом номеров вершин, исследуемого графа устройства, а управляющий вход блокаключей соединен с выходом элементаИЛИ, каждый-й вход которого подключен к выходу 1 -го элемента И групгп, первый вход .соединен с выходом-го элемента ИЛИ третьей группы,д - й (д=1,п) выход мультиплексора подключен к второму входу-го элемента И группы и входам 1-х (1=1,п, 10 кроме= 1) элементов ИЛИ третьейгруппы..Пчелин орректор,М.Пожо Редак Тираж 671сударственного комитета СССРам иэобретений и открытийсква, Ж, Раушская наб., д 051/42ВНИИПИ Гопо дел13035, М писное акаэ 4 ектн иэводственно-полиграфическое предприятие, г.ужгород, у