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

(51) 4 С 06 Р 15/2 ссчет .поненГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР ОПИСАНИЕ ИЗ К АВТОРСКОМУ СВИДЕТЕ(56) Авторское свидетельство СССР Р 637822, кл. С 06 Р 15/20, 1978.Авторское свидетельство СССР Р 1174937, кл. С 06 Р 15/20, 1985 (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ ПАРАМЕТРОВ ГРАФОВ(57) Изобретение относится к вычислительной технике и может быть использовано для определения хара теристик связности графов, в част Изобретение относится к вычислительной технике и может быть использовано для определения характеристик,связности графов, в частности дляразбиения графа на сильные компоненты при структурном анализе сложныхсистем.Цель изобретения - расширениефункциональных возможностей заразбиения графа на сильные комты,На фиг,1 и 2 представлена функциональная схема устройства; на фиг.Зграф на Фиг. 4 и 5 - матрицы достижимостей (К) и контрдостижимостей,1) соответственно; на фиг. 6 - ихпрямое произведение (матрица ВЭЯ).Устройство содержит первую груп"пу элементов И 1-1, вторую группуэлементов И 2)-2)1, вход 3 сбросаАустройства, регистры,4-4, игрупп ти для разбиения графа на сильныекомпоненты при структурном анализесложных систем. 11 ель изобретениясостоит в расширении функциональныхвозможностей за счет разбиения графа на сильные компоненты. Устройствосодержит наборное поле с выпрямительными элементами, генератор тактовыхимпульсов, три счетчика, три дешифратора, шесть элементов И, четырегруппы элементов И, три элемента НЕ,две группы из п регистров (и - числовершин исследуемого графа), две матрицы пКп элементов И, икоммутато- .ров-мультиплексоров, элемент задерж-ки, б ил. элементов И 5, -5 6-бп71 7 п8-8, 9-9 д, образующих матрицу из Япп элементов И (и - число вершинграФа), .вход 10 пуска устройства,дешифратор 11, счетчик 12, первый 1 вв 6элемент И 13, элемент НЕ 14, генера- фДтор 15 тактовых импульсов, второйэлемент И 16, наборное поле 17, вып,рямительные элементы 8, третий 19 ичетвертый 20 1 элементы И, второйсчетчик 21, второй элемент НЕ 22,Жвторой дещифратор 23, пятый 24 ишестой 25 элементы И третий счетчик26, третий дешифратор 27, третийэлемент НЕ 28, вторую группу регистров 29,-29 и, и групп элементов И ыюЬ30)-30 31-31, 32)-32 д) 33-33)34) -34, образующих вторую матрицуиэ пЫ элементов И, третью группуэлементов И 35, икоммутатор-мль-.типлексор 36-36 четвертую группу8229 3 150элементов 37"37,и элемент 38 задержки.Устройство работает следующимобразом.В поле 17 набирается топологияграфа путем включения выпрямительных элементов )8. При подаче сигнала на вход 3 счетчики )2, 21 и 26и регистры 4-4 ,и 29-29 устанавливаются и нулевое состояние. Дпязапуска устройства подается потенциал "1" на вход 10 пуска устройства,через элемент И 16 тактовые импульсы с выхода генератора 15 поступаютна элемент И 13, которыи в исходномсостоянии открыт, так как на (и+1)-мвыходе дешийратора 11 присутствуетпотенциал 0, Потенциал "1" с выходаэлемента НЕ 14 открывает также элементы И 2.После записи в счетчик 12 первого импульса на первом выходе дешифратора 11 устанавливается потенциал"1",который поступает на элементыИ 5, открывает их и подключает входырегистра 4 к выходам соответствующих элементов И 2 -2,. Потенциал"1" с первого выхода дешифратора 11подается также на первый столбец наборного поля 17 и устанавливает первый разряд регистра 4в единичноесостояние.П р и м е р. Пусть исследуемыйграй имеет вид, показанный нафиг.3, На наборном поле 17 с помощьюэлементов 18 набрана структура грайа, Через элемент И 1 единичныйпотенциал поступает на первую строку наборного поля 17 и через элементы 18 и 2 устанавливает третий разряд регистра 4н "1", поступает через элемент И 1на третью строкуи через элемент 18з аписынает 1 в четвертый разряд регистра 4 , поступает через элемент И 1 на четвер-; тую строку. После прихода второго импульса уровень 1" появляется на втором выходе дешийратора 11, а на первом выходе устанавливается потенциал"0", который отключает регистр 4 от наборного поля, Одновременно снимается "1" с первого- столбца. Еди.ничный потенциал с второго выхода дешийратора 11 открывает элементы И 6, -6, а также подается на второй столбец наборного поля. Далее работа устройства аналогична описанной в 1первом такте. С приходом третьего и 10 15 20 25 30 35 40 45 50 55 четвертого тактовых импульсон информация о достижимости вершин грайа записывается в регистры 4 и 4. С приходом (и+1)-го тактового импульса на выходе элемента НЕ 14 появляется потенциал "1", который запрещает дальнейшее прохождение тактовых импульсов н счетчик 12 и закрынает элементы И 2.-2 , отключая столбцы наборного поля 17 от регистров 4"4. В результате в регистрах 4-4 содержится матрица К достижимостей исследуемого грайа. На этом заканчивается первый этап работы устройства.Как видно из йиг.4, на которой представлена матрица достижимостей К графа, на фиг5, на которой представлена матрица контрдостижимостей Я того же графа, матрицу контрдостижимостеч В. грайа можно получить из матрицы достижимостей путем замены строкна столбцы. Поэтому для того, чтобы найти прямое произведение матриц КОЯ, достаточно перемножить строки на столбцы матрицы достижимостей. Этот процесс осуществляется на вто- ром этапе работы устройстна. Напряжение на (и+1)-м выходе дешийратора 11 открывает элемент И 18 и тактовые импульсы с генератора 15 начинают поступать на элемент И 20, открытый потенциалом "1"цоступающим с выхода элемента НЕ 22. К первым входам элементов И 30,-30 подключены информационные выходы одноименных разрядов регистра 4 , в котором записа"7на первая строка матрицы достижимостей грайа, т.е. код 1011. Вторые входы элементов И 30-30подключены к выходам первых разрядов регистров 4 -4,в которых записан первый столбец матрицы достижимостей (соответствующий первой строке матрицы контрдостижимостей ), т.е, комбинация 1111. При поступлении первого тактового импульса на счетчик 21 на первом вы- ходе дешийратора 23 появляется единичный потенциал, поступающий на третьи входы элементов И 30, -30 п первой строки матрицы. При этом происходит логическое перемножение первой строки и,первого столбца матрицы достижимостей. Таким образом, в первой строке матрицы КЩО (в регистре 29) записывается комбинация 1011. При поступлении очередных тактоных импульсов происходит перемножениеоче" редных одноименных строк и столб510 15 20 25 35 40 45 50 55 5 15 цов матрицы достижимостей, что соответствует перемножению одноименных строк матриц достижимостей и контрдостижимостей К и Ч, При поступлении 5-го тактового импульса на 5-м выходе денифратора 23 появляется единичный потенциал 1 на всех остальных выходах - нулевой потенциал), который запрещает через элемент И 20 дальнейшее прохождение тактовых импульсов на счетчик 21. В регистрах 29 л -29 ц записана матрица КЩ (фиг.б). На этом заканчивается второй этап работы устройства.На третьем этапе производится разбиение графа на сильные компоненты. На первый вход элемента И 24, открытого по второму входу, поступают тактовые импульсы с генератора 15. Первые информационные входы коммутаторов-мультиплексоров подключены к соответствующим информационным выходам первого регистра 29 вторые входы - к соответствующим информационным выходам второго регистра и т,д. При поступлении первого тактового импульса на элемент И 25, открытый единичным потенциалом с выхода элемента НЕ 28, в счетчик 26 записывается "1" и на адресные входы коммутаторов- мультиплексоров поступает единичный адрес. При этом на выход коммутаторов-мультиплексоров подключены соответствующие разряды регистра 29 . Так как в первом регистре 29 записана комбинация 1011, на первые входы элементов И 371, 37, 374. подаются уровни напряжения "1", на 37 - "0".Через время= Тс /2 (где Тс период следования тактовых импульсОв) на вторые входы поступает тактовый импульс, который через элементы И 37 и 37 стирает информацию в регистрах 29 и 29 д. При поступлении второго тактового импульса на элементы И 371-37 подается комбинация 0100 во втором регистре 29 записана комбинация 0100). Через время второй тактовый импульс не стирает информацию ни в одном из регистров. Во втором регистре 29 остается комбинация 0100. Аналогично при третьем такте также не стирается информация ни в одном из регистров 29, -29 п, а в регистрах 29-294 остается комбинация 0000. С приходом четвертого тактового импульса на 4-м выходе дешифратора 27 появляется напряжение ло 08229 6 гической "1", которое через элемент28 НЕ закрывает элемент И 25. Наэтом работа устрой"тва прекращается.Элементы индикации, подключенные кинформационным выходам регистров29-29, высвечивают в первой строке комбинацию Х, Х, Хл во второй " Х. Эти вершины графа соответствуют его двум сильным компонентам -Х, Х, Х и Х. Элементы И 37 служатдля развязки управляющих входов регистров 29Формула изобретения. Устройство для исследования параметров графов, содержащее генератор тактовых импульсов, два элемента И, две, группы элементов И, матрицу и и элемен- тов И, элемент НЕ, дешифратор, счетчик, группу из и регистров (и -число вершин графа 1, наборное поле свыпрямительными элементами, причемгоризонтальные шины наборного полячерез выпрямительные элементы соедииены с соответствующими вертикальными шинами согласно топологии графа,а также соединены с одноименными вы 30 ходами элементов И первой группы,вертикальные шины наборного поляподключены к первым входам элементов И второй группы, выход каждого изэлементов И второй группы соединенс первым и вторым входом одноименного элемента И первой группы и с первыми входами элементов И одноименнойстроки матрицы, выходы элементов Истолбца матрицы соединены с входамиразрядов одноименного регистра группы, вход сброса устройства соединенс входом сброса счетчика и входамисброса регистров группы, счетныйвход счетчика подключен к выходу первого элемента И, первый вход которого соединен с выходом второго элемента И, а второй вход соединен с выходом элемента НЕ и вторыми входами элементов И второй группы, вход элемента НЕ соединен с (и+1)-м выходом дешийратора, выходы разрядов счетчика подключены к информационному входу дешифратора, первый вход второго элемента И является входом пуска устройства, второй вход первого элемента И подключен к выходу генератора тактовых импульсов, р-е выходы дешифратора (р=1,2,,и) соединены с вторыми входами элемен 1508229тов И р-го столбца матрицы, о т л ич а ю щ е е с я тем, что, с целью расширения функциональных возможностей за счет разбиения графа на сильные компоненты, в него введены третий, четвертый, пятый и шестой элементы И, второй и третий счетчики, второй и третий дешифраторы, второй и третий элементы НЕ, вторая группаиз и регистров, вторая матрица пп элементов И, третья и четвертая группы элементов И, икоммутаторов-мультиплексоров, элемент задержки, выход которого соединен с первыми входами элементов И четвертой группы, вторые входы которых соединены с выходами соответствующих коммутаторов-мультиплексоров, выход р-го элемента И четвертой группы (р 1,2 п) соединен с входом сброса (р+1)-го регистра второй группы, выходы элементов И К-й строки второй матрицы (1 с=1,2п) соединены с входами одноименных разрядов 1 с-го регистра второй группы, выход 1-го разряда -го регистра второй группы (1=1,2. п, 3+ 1п) соединен с д-м информационным входом Ц)-го коммутатора мультиплексора, адресные вхо- ды коммутаторов-мультиплексоров сое-, динены с выходом третьего счетчика, счетный вход второго подключен к выходу шестого элемента И, первый вход которого подключен к выходу пятого элемента И, а второй вход - к выходу третьего элемента НЕ, вход которо.го подключен к и-му выходу третьего дешифратора, первый вход пятого.элемента И подключен к выходу генератора тактовых импульсов, а второй вход 5подключен к (и+1)-му выходу второго дешифратора, вход которого подключен к выходу второго счетчика, счетный вход которого подключен к выходу четвертого элемента И, первый вход 10 которого подключен к выходу второгоэлемента НЕ, вход которого подключен к (и+1)-му выходу второго дешифратора, второй вход четвертого элемента И соединен с выходом третьего эле мента И, первый вход которого подключен к выходу генератора тактовых импульсов, а второй вход - к (и+1)- му выходу первого дешифратора, каждый выход второго дешифратора подклю чен к первым входам элементов И одноименной строки второй матрицы, второй вход д-го элемента И 1-й строки второй матрицы (д,= 1,2п) подключен к -му информационному выходу х-го регистра первой группы, третий вход 1.-го элемента И 1-й строки второй матрицы (д, 1 = 1,2, ,и) подключен к д-му информационному выходу -го регистра первой З 0 группы, вход элемента задержки подключен к выходу шестого элемента И, первый и второй входы элементов И третьей группы подключены к входу сброса устройства, к которому также З 5 подключены входы сброса второго итретьего счетчиков, выход элемента И третьей группы подключен к входу сброса одноименного регистра второй группы.42/51 Тираж 668 Подписноеосударственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., д. 4/5 ВКИИПИ Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101