Устройство для исследования графа
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Союз Советских
Социалистических
Республик
I // (61) Дополнительное к авт, свид-ву (51)М. Кл.2 (22) Заявлено 210378 (21) 2593083/18-24 с присоединением заявки ¹ G 06 F 15/20 Государственный комитет СССР по делам изобретений и открытий (23) Приоритет (53) УДК 681. 333 (088.8) Опубликовано 30.0680. Бюллетень ¹ 24 Дата опубликования описания 300680 (72) Авторы изобретения О.Н. Голованова, A.Ã. Додонов, В.В. Федотов, Н.В.Федотов и А.М. Щетинин Институт электродинамики АН Украинской ССР (7! ) 3 а яв итель (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ГРАФА Изобретение относится к электронному моделированию и может быть использовано для решения задач íà графах, в частности для определения функции Гранди на графе. Под функцией Гранди g (х) графа G = (х, г ) понимается значение (x;), соответствующее вершине х; g x и представляющее собой наименьшее из тех целых неотрицательных чисел, которые не принадлежат множест(в(хЯхрГк; и д(х) =о если Гх; = P где g (х;) — значение функции Гранди для вершины х;; Гх — отображение х;Ь)(, т.е. l множество вершин, достижимых из вершины х;. Для произвольной вершины х; g (х ) = О, еслиГх;= ф, а если Гх; y ф, то g (х; ) равно наименьшему неотрицательному числу, не сопоставленному никакой из вершин в Гх; . Известно устройство для определения кратчайших путей на графе, соl держащее модели узлов, модели ветвей, блоки индикации ветвей кратчайшего пути, перемейные линии задержки (1). Это устройство позволяет определить доступность графа для произвольной вершины. Наиболее близким по технической сущности к предлагаемому является устройство для исследования графов, содержащее блок управления, который своими первым и вторым .входами соединен с генератором импульсов и третьим входом соединен .с выходом сдвигового регистра, модели вершин, число которых равно числу вершин в графе, каждая из которых содержит счетчик, первьЩ, триггер, схему индикации, инвертор и элементы И, ИЛИ и своим первым входом и выходом соединена с остальными моделями вершин в соответствии с топологией заданного графа,флорой вход каждой модели вершины, имеющей связь с первой общей шиной, подключен в модели вершины через элемент И ко входу счетчика, выход которого соединен со схемой индикации, а первая шина соединена с первым выходом блока управления, третьи и четвертые входы моделей вершин объедннены на второй и третьей общей шине, послед 744593 няя из которых связана со вторым выходом блока управления (2). Известное устройство позволяет найти все отображения (Г x ) для любой вершины графа, но не позво-. ляет определить функцию Гранди, Цель изобретения — расширение функциональных воэможностей за счет определения функции Гранди. укаэанная цель достигается тем, что в устройство для исследования графа, содержащее элементы И, элементы ИЛИ, триггеры, формирователь одиночного импульса, модели вершин, соединенные между собой согласно топоЛогии исследуемого графа, регистр, один выход которого подключен к первому входу блока управления, каждая модель вершины содержит блок индикации, вход которого через счетчик импульсов подключен к выходу. первого элемента И, первый триггер, первый элемент ИЛИ и элемент НЕ, введены генератор импульсов, MHoãoâõáäîâîé элемент ИЛИ, многовходовой элемент И, а каждая модель вершины содержит формирователь временного интервала, выход которого подключен к первому входу первого триггера, выход которого соединен с первым входом первого элемента ИЛИ, второй вход которого через элемент НЕ подключен к первому входу формирователя временноrp интервала, второй вход формирователя временного интервала каждой модели вершины соединен с первым выходом блока управления, второй выход которого подключен к первому входу первого элемента И каждой модели вершины, второй вход первого элемента И каждой модели вершины соединен с выходом второго триггера, первый вход которого подключен к выходу второго элемента И, первый вход которого соединен с выходом третьего триггера, первый вход которого через многовходовой элемент ИЛИ подключен к первому входу первого триггера каждой модели вершины, второй вход первого триггера каждой модели вершины соединен с выходом формирователя одиночного импульса, вход которого подключен к вь(ходу второго элемента ИЛИ, первый выход которого через многовходовой элемент И соединен с выходом первого элемента ИЛИ каждой модели вершины, выходы генератора импульсов подключены ко второму и третьему входам блока управления, третий выход которого соединен со вторым входом второго элемента ИЛИ, выход которого подключен к второму входу второго триггера, другие выходы регистра соединены с третьим входом первого элемента И всех моделей вершин, первый выход блока управле-ния подключен ко второму входу второго элемента И, выход формирователя одиночного импульса соединен с входом регистра, второй вход третьего триггера подключен к второму выходу блока управления. На чертеже представлена блок-схема устройства. Схема содержит модели 1 ... 1 1 О вершин, блок 2 управления, регистр 3, генератор 4 импульсов, многовходовой эпемент 5 ИЛИ, второй элемент б ИЛИ, второй элемент 7 И, многовходовой () элемент 8 И, третий 9 и второй 10 триггеры, формирователь 11 одиночного импульса Каждая модель 1 вершины, число 15 которых соответствует количеству ъ ерши н моделируемого граф а, состоит из формирователя 12 временного интервала первого триггера 13, элемента 14 НЕ, первого элемента 15 ИЛИ, первого элемента 16 И, счетчика 17 20 импульсов, и блока 18 индикации. Модель 1; вершины-предназначена для формирования значения функции Гранди i-й вершины g (x;) в виде числа импульсов в счетчике 17. 5 Каждая из моделей вершин своим входом 19; и выходом 20; соединена с остальными моделями вершин в соответствии с топологией заданного графа. Вход 21; модели вершины соединен ()с разрядным выходом регистра 3,а выход 22) и 23; этой модели соединен с соответствующим входом элементов 5 .ИЛИ и 8 И соответственно. Формирователь 12 временного ин тервала каждой модели вершины выполняется на основе счетчико-регистровых структур. Он предназначен для хранения и время-импульсного моделирования заданной величины Гх Регистр 3, имеющий поразрядные ® параллельные выходы, число разрядов в котором соответствует количеству моделей вершин, предназйачен для Последовательного выбора х вершины моделируемого графа, в котором 4 определяется значение функции Гранди g (х,). Формирователь l l одиночного импульса предназначен для получения на его выходе, импульса при появлении 5р на входе разрешающего потенциала. Устройство работает следующим образом. Первоначально в регистр 3 записываются нули, счетчики 17 всех моделей вершин, триггеры 9, 10 и триггеры 13 всех моделей вершин устанавливаются в нулевое состояние (установочные шины на чертеже не показаны); Затем в формирователь 12 временного интервала каждой модели Щ вершины заносится число импульсов, пропорциональное величине Гх;, что соответствует числу вершин достижимых из выбранной вершины х;. Например, если для i-ой вершины заданного графа отображение Гх; 744593 60 состояние. С единичного выхода тригсодержит К вершин, то в формирователь 12 временного интервала мбдели 1; вершины заносится число импульсов М =tR — (к 3)) где — полная емкость формирователя, К вЂ” количество импульсов, пропорциональное велиЧине отображения, i-ой вершины. Таким образом, если отображение i-ой вершины Гх; = 0 (тупиковая вершина), то формирователь 12 временного интервала модели 1 вершины должен формировать интервал, длительность которого равна одному периоду генератора. После занесения исходной информации и начального установа на выходе 24 блока 2 управления появляется сигнал „ Пуск . Этот сигнал поступает через элемент 6 ИЛИ на единичный вход триггера 10. Единичный выход триггера 10 выдает разрешение на полюс 25 всех моделей вершин и следовательно на вход элемента 16 И. Сигнал Пуск поступает также на вход формирователя 11 одиночного импульс а. Формиров атель 1 1 Bblpa6 атывает импульс, который поступает на вход регистра 3 и устанавливает первый разряд регистра в единичное состояние. Импульс с формирователя 11 поступает также на полюс 26 всех моделей вершин. Разрешение с выхода первого разряда сдвигового регистра 3 пост упает на входы 21; — 21„ выбранной модели вершины. Если считать, что такой моделью является модель 1, то это соответствует появлению разрешения на элементе 16 И.. Кроме того,.сигнал с входа 21 проходит на выход 20, который является выходом -модели вершины. С полюса 20„ разрешение поступает на вход 19;(вход модели вершины), т. е. моделей вершин, которые входят в множество Г х т. е. связаны с первой вершиной согласно топологии графа. С входа 19; высокий потенциал дает разрешение на вход формирователя 12 временного интервала и снимает разрешение через элемент 14 НЕ с .входа элемента 15 ИЛИ. Генератор 4 импульсов вырабатывает на своих выходах серии импульсов ГИ l и ГИ 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 появляется импульс конца 20 формирования временного интервала. В случае отсутствия указанной вершины в:множестве .Гх; ни один фор° мирователь 12 не вырабатывает импульс конца временного интервала. 25 Если же тупиковая вершина есть, то сигнал с выхода формирователя 12 устанавливает триггер 13 модели вершины в единичное состояние и одно временно поступает через выход 22; 30 на соответствующий вход элемента 5 ИЛИ. С выхода элемента 5 ИЛИ сигнал конца формирования временного интервала проходит на единичный вход триггера 9. Единичное состояние триггера 9 запрещает прохождение импульса ГИ 2 через элемент 7 И. В результате этого триггер 10 остается в единичном состоянии. С поступлением следукщего импульса ГИ 1 триггер 9 устанавливается в нулевое состояние. Одновременно этот импульс поступает в счетчик 17 модели 1 вершины. Второй импульс ГИ 2 поступает в формирователи 12 тех моделей 45 вершин, которые принадлежат множеству Гx . При этом в счетчике 17 модели 1 накапливается число импульсов, характеризующих значение функции Гранди g (х } для выбранной вершины. Поступлейие импульсов ГИ 1 и ГИ 2 5О происходит до тех пор, пока на одном из тактов отсутствует импульс на выходе элемента 5 ИЛИ. Если это происходит, то триггер 9 остается в нулевом состоянии. Разрешение с нулевого выхода триггера 9 поступает на входы элемента 7 И, и импульс ГИ 2 с выхода 28 блока управления поступает на вход триггера 10 и устанавливает его в нулевое гера 10 выдается запрет на вход элемента 16 И модели 1 вершины, и импульсы ГИ 1 не поступают в счетчик 17 этой модели. В счетчике 17 модели 1 вершины хранится число им4 дой вершине, что"имеет большое практическое значение, Так, в частности, на основании функции и ее значений можно достаточно легко решать задачи упорядочения вершин графа, нахождения внутренних и внешних устойчивых множеств и ядер графа. Перечисленные задачи часто встречаются при создании вычислительных устройств и комплексов в процессе их проектирования, прн исследовании систем с внутренней сетевой структурой, при проектировании автоматизированных систем управления. Формула изобретения Устройство для исследования графа, содержашее элементы И, элементы ИЛИ, триггеры, формирователь одиночного импульса, модели вершин, соединенные между собой согласно топологии исследуемого графа, регистр, один выход которого подключен к первому входу блока управления, каждая модель вершины содержит блок индикации, вход которого через счетчик импульсов подключен к выходу первого элемента И, первый триггер, первый элемент ИЛИ и элемент НЕ, о тл и ч а к щ е е с я тем, что, с целью расширения функциональных возможностей за счет определения функции Гранди, в устрОйство введены генератор импульсов, многовходовой элемент ИЛИ, многовходовой элемент И, а каждая модель вершины содержит формирователь временного интервала, выход которого подключен к первому входу первого триггера, выход которого соединен с первым входом первого элемента ИЛИ, второй вход которого через элемент НЕ подключен к первому входу формирователя временного,интервала, второй вхОд формирователя временного интервала каждой модели вершины соединен с первым выходом блока управления, второй выход которого подключен к первому входу первого элемента И каждой модели вершины, второй вход первого элемента И каждой модели вершины соединен с выходом второго триггера, первый вход которого подключен к выходу второго элемента И, первый вход которого соединен с выходом третьего триггера, первый вход которого через многовходовой элемент ИЛИ подключен к первому входу первого триггера каждой модели вершины, второй вход первого триггера каждой модели вершины соединен с выходом формирова- теля одиночного импульса, вход которого подключен к выходу второго элемента ИЛИ, первый выход которого через многовходовой элемент И сое- динен с выходом первого элемента е 7 744593 1 пульсов, пропорциональное g (х <), что соответствует минимальному целому неотрицательному числу, не принадлежаШему множеству . д(х„Ях яГх„) Таким образом, если g {х, ) = О, то в счетчике 17 моцели 1 вершины хранится один импульс, если g(х „) к, то в счетчике 1 7 хранится (к+1) импульс. . После того, как триггер 10 устанавливается в нулевое состояние„ импульсы ГИ 2 продолжают поступать на формирователи 12 временных интервалов моделей вершин до тех пор, пока все указанные формирователи моделей 1 вершин, на входах 19 которых присутствует разрешение, не выдадут импульс конца формирования интервала. При этом на входах элемента И 8 появляется разрешение. 20 Модели вершин, не принадлежаших множеству Гх, выдают разрешение с элемента 14 НЕ через элемент l5 ИЛИ на вход 23„ . В моделях вершин, принадпежащих множеству Гх, импульс 25 конца формирования временного интер- вала устанавливает триггер 13 моделей вершин в единичйое состояние, и разрешение с выхода триггера через элемент 15 ИЛИ поступает также на выход 23. Сигнал с выхода элемента 8 И через элемент б ИЛИ устанавливает триггер 10 в единичное состояние и одновременно поступает на вход формирователя ll одиночного импульса, Импульс с выхода формирователя 11 устанавливает триггеры 13 моделей вершин по входу 2б в нулевое состояние и производит сдвиг на один раз- д ряд в регистре 3. В результате произЩ водится выборка второй модели 1 вершины. Весь процесс IToBTopReTcH аналогично описанному выше. ,Определение всех значений функции Гранди продолжается до тех пор, пока на выходе регистра 3 появляется сигнал, который поступает на вход 29 блока 2 управления. Это свидетельствует о том, что для каждой вершины заданного графа сформиро- 50 вано значение функции Гранди g(x,). Число импульсов, занесенное в счетчики 17 моделей 1 вершин соответствует значению функции Гранди g(x ) в 1 каждой вершине графа. Это значение 55 индицируется блоком 18 индикации, вход которого связан с выходом счетчика 17. Использование новых элементов двух триггеров, двух элементов И, двух элементов ИЛИ и формирователя временного интервала в модели вершины, вк оченних в соответствукщую схему, позволяет определять функцию Гранди на графе и ее значение в каж-- у (- -.", 10 744593 формирователя одиночного импульса соединен с входом регистра, второй вход третьего триггера подключен к второму выходу блока управления. Составитель И. Дубинина Редактор Л. Веселовская Техред Л.Теслюк Корректор Г. Назарова Заказ 3795/14 Тираж 751 ЦНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5 Подпис ное Филиал ППП Патент, г. Ужгород, ул. Проектная, 4 ИЛИ каждой модели вершины, выходы . генератора импульсов подключены ко второму и третьему входам блока управления, третий выход которого соединен со вторым входом второго элемента ИЛИ, выход которого подключен к второму входу второго триггера, другие выходы регистра соединены с третьим входом первого элемента И всех моделей вершин, первый выход блока управления подключен ко второму входу второго элемента И, выход Источники информации, принятые во внимание при экспертизе 1. Авторское свидетельство СССР 9 301718, G 06 G 7/48, 1971. 2. Авторское свидетельство СССР по заявке 2194669/18-24,G 06 F 15/20, 1975.
