Устройство для исследования графа Советский патент 1980 года по МПК G06F15/173 

Изобретение относится к электронному моделированию и может быть использовано для решения задач на графах, в частности для определёния функции Гранди на графе. Под функцией Гранди g (х) графа G (х, г ) понимается значение g (Xl ), соответствующее вершине Х-, е 5. и представлягадее собой наиме шее из тех целых неотрицательных iHсея, которые не принадлежат множести g(xO О , если Гх; 0 где g (х) - значение функции Гранди для вершины х;; Гу. - отображение х-,бх t т.е множество вершин, дости жимых из вершины Xj . Для произвольной вершины хg (Х( ) О, еслиГх-, 0 , а если Гх У 0 / то g (xj ) равно наименьшему неотрицательному числу, не сопоставленному никакой из вершин в Гх;. Известно устройство для определения кратчайших путей на графе, содержащее модели узлов, модели ветвей блоки индикации ветвей кратчайшего пути, переменные линии задержки 1 Это устройство позволяет определить доступность графа для произвольной вершины, Наиболее близким по технической сущности к предлагаемому является устройство для исследования графов, содержащее блок управления, который своими первым и вторым входами соединен с генератором импульсов и третьим входом соединен .с выходом сдвигового регистра, модели вершин, число которых равно числу вершин в графе, каждая из которых содержит счетчик, первы, триггер, схему индикации, HHseptop и элементы И, ИЛИ и своим первым входом и выходом соединена с остальными моделями вершин в соответствии с топологией заданного графа,второй вход каждой модели вершины, имеющей связь с первой общей шиной, подключен в модели вершины через элемент И ко входу счетчика, выход которого соединен со схемой индикации, а первая, шина соединена с первым выходом блока управления, третьи и четвертые входы моделей вершин объединены на второй и третьей общей шине, послех

няя из которых связана со вторым выходом блока управления 2.

Известное устройство позволяет найти все отображения ( Гх,) для любой вершины графа, но не позво ляет определить функцию Гранди.

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

Указанная цель достигается тем, что в устройство для исследования Графа, содержащее элементы И, элементы ИЛИ, триггеры, формирователь одиночного импульса, модели вершин, соединенные между собой согласно топологии исследуемого графа, регистр, один выход которого подключен к первому входу блока управления, каждая модель вершины содержит блок индикации, вход которого через счетчик импульсов подключен к выходу, первого элемента И, первый триггер, первый: элемент ИЛИ и элемент НЕ, . введены генератор импульсов, многовхбдоврй г элемент ИЛИ, мнозгов ходовой элемент И, а каждая модель вершины содержит формирователь временного интервала, выход которого подключен к первому входу первого триггера, выход которого соединен с первым входом первого элемента ИЛИ, второй вход которого через элемент НЕ подключен к первому входу формирователя BpeMeHHoto интервала, второй вход формирователя временного интервала каждой модели вершины соединен с первым выходом блока управления, второй выход которого подключен к первоглу входу первого элемента И каждой модели вершины, второй вход первого элемента И каждой модели вершины соединен с выходом второго триггера, первый вход которого подключен к выходу второго элемента И, первый вход которого соединен с выходом третьего триггера, первый вход которого через многовходовой элемент ИЛИ подключен к первому вхоу первого триггера каждой модели вершины, второй вход первого триггера каждой модели вершины соединен с выходом формирователя одиночного импульса, вход которого подключен к .выходу второго элемента ИЛИ, первый выход которого через многовходовой элемент И соединен с выходом первого элемента ИЛИ кговдой модели верины, выходы генератора импульсов подключены ко второму и третьему входам блока управления, третий выход которого соединен со вторым вхоом второго элемента ИЛИ, выход которого подключен к второму входу втоого триггера, дpsгиe выходы регистра соединены с третьим входом первого элемента И всех моделей вершин, первый выход блока управле- ния подключен ко второму входу втоого элемента И, выход формирователя

одиночного импульса соединен с входом регистра, второй вход третьего триггера подключен к второму выходу блока управления.

На чертеже представлена блок-схема устройства.

Схема содержит модели 1,, . .. 1 вершин, блок 2 управления, регистр 3, генератор 4 импульсов, многовходовой элемент 5 ИЛИ, второй элемент б ИЛИ, второй элемент 7 И, многовходовой

элемент 8 И, третий 9 и второй. 10 триггеры, формирователь 11 одиночного импульсаКаждая модель 1 вершины, чис-ло которых соответствует количеству

5тзершин моделируемого графа, состоит из формирователя 12 временного интервала первого триггера 13, элемента 14 НЕ, первого элемента 15 ИЛИ, первого элемента 16 И, счетчика 17

0 импульсов, и блока 18 индикации. Модель 1; вершины- предназначена для формирования значения функции Гранди 1-й вершины g (Xj) в виде числа импульсов в счетчике 17.

5 Каждая из моделей вершин своим входом 19 и выходом 20; соединена с остальными моделями вершин в соответствии с топологией заданного графа. Вход 21; модели в.ершины соединен

Q с разрядным выходом регистра 3,а выход 22i и 23 этой модели соединен с соответствующим входом элементов 5 -ИЛИ и 8 И соответственно.

Формирователь 12 временного инс тервала каждой модели вершины вы- , полняется на основе счетчико-регистровых структур. Он предназначен для хранения и время-импульсного моделирования заданной величины Гх, . Регистр 3, имеющий поразрядные

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

5 определяется значение функции Гранди g (х; ).

Формирователь 11 одиночного импульса предназначендля получения на его выходе,импульса при появлении

Q на входе разрешающего потенциала. Устройство работает следующим образом.

Первоначально в регистр 3 записываются нули, счетчики 17 всех моделей вершин, триггеры 9, 10 и

триггеры 13 всех моделей вершин устанавливаются в нулевое состояние (установочные шины на чертеже не показаны) . Затем в формирователь 12 временного интервала каждой модели

О вершины заносится число импульсов, пропорциональное величине Гх;, что соответствует числу вершин достижимых из выбранной вершины Xj .

Например, если для i-ой вершины

5 заданного графа отображение Гх,

содержит К вершин, то в формирователь 12 временного интервала мблели Ij вершины заносится число импульсов

(км) ,

где ( - полная емкость формирователя, К - количество импульсов, пропорциональное отображения, 1-ой вершины. Таким образом, если отображение i-on вершины Гх-, О (тупиковая вершина), то формирователь 12 временного интервала модели 1 вершины должен формировать интервал, длительность которого равна одному периоду , генератора.

После занесения исходной информации и начального установа на выходе 24 блока 2 управления появляется сигЭтот сигнал поступает

нал , Пуск

через элемент б ИЛИ на единичный вход триггера 10. Единичный выход триггера 10 выдает разрешение на полюс 25 всех моделей вершин и следовательно на вход элемента 16 И. Сигнал Пуск поступает также на вход формирователя 11 одиночного импульса. Формирователь 11 вырабатывает импульс, который поступает на вход регистра 3 и устанавливает перйый разряд регистра в единичное состояние. Импульс с формирователя 11 поступает также на полюс 26 всех моделей вершин. Разрешение с выхода первого разряда сдвигового регистра 3 поступает на входы 21| - 21, выбранной модели вершины. Если считать что такой моделью является модель 1д, то это соответствует появлению разрешения на элементе 16 И. Кроме того.сигнал с входа 21 проходит на в.ыход 20 , который является выходом модели вершины. С полюса 20 разрешение поступает на вход 19-, (вход модели вершины), т. е. моделей верш которые входят в множество Гх, т. е. связаны спервой вершиной согласно топологии графа. С входа 19-J высокий потенциал дает разрешение на вход формирователя 12 временного интервала и снимает разрешение через элемент 14 НЕ с .входа элемента 15 ИЛИ.

Генератор 4 импульсов вырабатыва на своих выходах серии импульсов ГИ 1 и ГИ 2, сдвинутые относительно друг друга. Импульсы ГИ 1 с выхода 27 блока 2 управления поступают на входы 27 - 27р, всех моделей вершин, но прохсяят через элемент 16 И только той модели, на которую поступает разрешение с выхода 21 от разрядного выхода регистра 3. Икшульсы ГИ 2 с выхода 28 блока 2 управления поступают на входы 28 - 28Р| моделей вершин, но проходят в формирователь 12 временного интервала только тех моделей,

на входах 19, которых присутствует разрешений.

Таким образом, первый импульс ГИ 1, поступивший на вход 27 , проходит через элекйнт 16 И модели 1 вершины и заносится в счетчик 17, так как на остальных входах элемента 16 И присутствуют разрешения с разрядного выхода 21 регистра 3 и с триггера 10. Первый импульс ГИ 2 поступает на входы формирователей 12 временных интервалов, которые начинают накапливать поступающие импульсы, однако работают формиров ателй ЧолькоГ тех моделей вершин, которые принадлежат Гх.

Предположим, что одна из вершин, имеющих связь с вершиной х , является тупиковой (ее отображение Гх; ), В этом случае на выходе формирователя 12 появляется импульс конца формирования временного интервала.

8случае отсутствия указанной вершины в Множестве -Гх; ни один формирователь 12 не вырабатывает импульс конца временного интервала. Если же тупиковая вершина есть, то сигнал с выхода формирователя 12 устанавливает триггер 13 модели вершины в единичное состояние и одновременно поступает через выход 22 на соответствукздий вход элемента

5 ИЛИ. С выхода элемента 5 ИЛИ сигнал конца формирования временного интервала проходит на единичный вход триггера 9. Единичное состояние триггера 9 за:прещает прохождение импульса ГИ 2 через элемент 7 И. В результате этого триггер 10 остается в единичном состоянии. С поступлением следующего импульса ГИ 1 тригг

9устанавливается в нулевое состояние. Одновременно этот импульс поступает в счетчик 17 модели 1 вершины. Второй импульс ГИ 2 поступает в формирователи 12 тех моделей вершин, которые принадлежат множеств Гх.. При этом в счетчике 17 модели

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

Поступление импульсов ГИ 1 и ГИ 2 происходит до тех пор, пока на одном из тактов отсутствует импульс на выходе элемента 5 ИЛИ. Если это происходит, то триггер 9 остается в Hyj;ieBOM состоянии.

Разрешение с нулевого выхода триггера 9 поступает на входы элемента 7 И, и импульс ГИ 2 с выхода 28 блок управления поступает на вход триггера 10 и устанавливает его в нулевое состояние. С единичноговыхода триггера 10 выдается запрет на вхбд элемента 16 И модели 1 вершины, и импульсы ГИ 1 не поступают в счетчик 17 этой модели. В счетчике 17 модели 1 вершины хранится число импульсов, пропорциональное g(x), что соответствуят минимальному целому неотрицательному числу, не, принадлежащему множеству -1&( Таким образом, если g (х) 0, то в счетчике 17 модели 1 вершины хранится один импульс, если д{х) к, то в счетчике 17 хранится (к+ импульс. : . После того, как триггер 10 устанавливается в нулевое состояние, импульсы ГИ 2 продолжают поступать на формирователи 12 временных интервалов моделей вершин до тех пор пока все указанные формирователи моделей 1 вершин, на входах 19 кото рых присутствует разрешение, не выдадут импульс конца форг-шрования интервала.При этом на входах элемента И 8 появляется разрешение. Модели вершин, не принадлежащих мно кёству Гх, выдают разрешение с элемента 14 НЕ черезэлемент Г5 И на вход 23(. . В моделях вершин, прин /1ежа1цих множеству Гх , импульс конца формирования временного интер вала устанавливает триггер 13 моделей вершин в единичйое состояние, и разрешение с выхода триггера через элемент 15 ИЛИ поступает также на выход 23. Сигнал с выхода элемеМта 8 И через элемент б ИЛИ устанавливает, триггер 10 в единичное состояние и одновременно поступает на вход форми рователя 11 одиночного импульса. Им пульс с выхода формирователя 11 устанавливает триггеры 13 моделей вершин по входу 26 в нулевое состоя ние и производит сдвиг на один разряд в регистре 3. В результате прои водится выборка .второй модели Ij вершины. Весь процесс повторяется аналогично описанному выше. .Определение всех значений функции Гранди продолжается до тех пор пока на выходе регистра 3 появляется сигнал, который посту пает на вход 29 блока 2 управления. Это свидетельствует о том, что для каждои вершины заданного графа сформир вано значение функции Гранди д{х;) Число импульсов, занесенное в счетч 17 моделей вершин соответствует значению функции Гранди д{х-, ) в каждой вершине графа. Это значение индицируется блоком 18 индикации, вход КОТОРОГО связан с выходом счетчика 17. .Использование новых элементов двух триггеров, двух элементов И, двух элементов ИЛИ и формирователя временного интервала в модели вершины, включенных в соотвётствугацую схему, позволяет оп;редёлять функцию Гранди на графе и ее значение дои вершине, чтоимеет большое практичёско.е значение. Так, в частности, на основании функции и ее значений можно достаточно легко решать задачи упорядочения вершин графа, нахождения внутренних и внеш-. них устойчивых множеств и ядер графа. Перечисленные задачи часто встречаются при создании вычислительных устройств и комплексов в процессе их проектирования, при исследовании систем с внутренней сетевой с.труктурой, при проектировании автоматизированных систем управления. Формула изо.бретения Устройство для исследования графа, содержащее элементы И, элементы ИЛИ, триггеры, формирователь одиночного импульса, модели вершин, соединенные между собой согласно топологии исследуемого графа, регистр, один выход которого подключен к первому входу блока управления, каждая модель вери1ины содержит блок индикации, вход которого через счетчик импульсов подключен к выходу первого элемента И, первый триггер, первый элемент ИЛИ и элемент НЕ, о тличающееся тем, что, с целью расширения функциональных возможностей за счет определения функции Гранди, в устройство введены генератор импульсов, многовходовой элемент ИЛИ, многовходовой элемент И, а каждая модель вершины содержит формирователь временного интервала, выход которого подключен к первому входу первого триггера, выход которого соединен с первым йходом первого элемента ИЛИ, второй вход которого через элемент НЕ подключен к перврму входу формирователя временного .интервала, второй вход формирователя временного интервала каждой модели вершины соединен с первым выходом блока управления,- второй выход которого подключен к первому входу первого элемента И. каждой модели вершины, второй вход первого элемента И каждой модели вершины Сое динен с выходом второго триггера, первый вход которого подключен к выходу второго элемента И, первый вход которого соединен с выходом третьего триггера, первый вход которого через многовходовой элемент ИЛИ подключен. к первому входу первого триггера каждой модели вершины, второй вход первого триггера каждой модели вершины соединен с выходом формирователя одиночного импульса, вход которого подключен к выходу второго элемента ИЛИ, первый выход которого через многовходовой элемент И сое- динен с выходом первого элемента

ИЛИ Кс1жд6й модели вершины, выходы генератора импульсов подключены ко второму и третьему входам блока управления, третий выход которого соединен со вторым входом второго элемента ИЛИ, выход которого подключен к второму входу второго триггера, другие ВЫХОДЫрёгистТра соединены с третьим входом первого элемента И всех моделей вершин, первый выход блока управления подключен ко второму входу второго элемента И, выход

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

Источники информации, принятые во внимание при экспертизе

1,Авторское свидетельство СССР № 301718, G 06. G 7/48, 1971.

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

по заявке 2194669/18-24,0 06 F 15/20, 1975.