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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИН АР 4 С 06 1 15/ САНИЕ ИЗОБРЕТЕНИЯ АТЕИТь Б,Б;".: С .:,параметованныхрасширестей за пользовано для определениров достижимости в ориентграфах, Цель изобретенияние функциональных возмож счет нахо тво, содержащеесов, первый счетлементов И, наборительно введеныппа 5 элементоворой 7 блоки памяекия мощности бавторой счетчик 11,импу СССР 976. цу 4допол2, гр6 и впредел 98 ис к вбить сГОСУДАРСТНЕННЫИ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТ(71) Институт проблем надежнодолговечности машин АН БССР(54) УСТРОЙСТВО ДЛЯ ИССЛЩОВАГРАФОВ(57) Изобретение относитсялительной технике и может го графа ивенных харатем, что вгенератор 1чик 3, матрное поле 9,элемент ИЛИИЛИ, первыйти, блок 8зы, элемент3 ил. ния баз ориентированно пределения их количест теристик - достигаетсяИзобретение относится к вычислительной технике и может быть использовано цля определения параметров достижимости в ориентированных граФах.Цель изобретения - расширение Функциональных возможностей за счет нахождения баз ориентированного граФа и определения их количественных характеристик.На Фиг,1 приведена структурная схема устройства; на Фиг.2 - граф, на примере которого описывается рабо-та устройства; на Фиг.З - временная диаграмма работы устройства при определении параметров графа, изображенного на фиг. 2.Устройство содержит генератор импульсов, элемент ИЛИ 2, первый 2 О счетчик 3 матрицу 4 элементов И, группу 5 элементов ИЛИ, первый блок 6 памяти, второй блок. 7 памяти, блок 8 определения мощности базы, набор" ное поле 9, элемент И 10, второй 25 счетчик 11.Генератор 1 предназначен для синхронизации работы устройства; счетчик 3 - дчя перебора всех подмножеств вершин исследуемого графа; кроме то О го, с разряцных ьыходов этого счетчика двоичный код выбранного подмножества поступает на. информационные входы блока б памяти и разрядные входы блока 8 определения мощности базы.Элементы И матрицы 4 предназначе 35 ны для моделирования дуг графа. Единичный уровень сигнала на первом входе элемента И матрицы 4, поступающийот наборного поля 9, определяет надиОчие соответствующей ему дуги. Единичные уровни на вторых входах этих элементов, поступающие с выходов соответствующих элементов ИЛИ группы 5, соответствуют вершинам, принадлежащим всем ориентированным дугам, которые начинаются в вершинах, проверяемых на принадлежность базе.Элементы. И 5 П 1 группы 5 предназначены для моделирования вершин графа.Единичные уровни на нулевых входахэтих элементов соответствуют вершинам, которые проверяются на принадлежность базе. Единичные уровни навходах. этих элементов поступающие955с выходов элементов И матрицы 4, соответствуют тем вершинам, в которые имеется достижимость извершин, проверяемых на.принадлежность базе,Блок 6 памяти предназначен для хранения информации о составе баз графа. В конце работы устройства по каждому адресу блока 6 памяти, задействованному в процессе работы, хранится. двоичный код, ециничные разряды которого соответствуют номерам вершин, которые образуют текущую базу. Блок 7 памяти предназначен для хранения двоичных кодов, соответствующих мощностям баз, Эти двоичные коды записываются в блок 7 памяти с выхода блока 8 определения мощности базы, Блок определения 8 мощности базы. предназначен для подсчета количества единиц в коде, поступающем со. счетчика 3, которое соответствует. количеству вершин в подмножестве, проверяемом на принадлежность базе.Наборное поле 9 предназначено для ввода топологии графа перед началом моделирования. Элемент И 10 предназначен для проверки условия, во все ли вершины графа имеется достижимость из подмножества вершин, проверяемых на принадлежность базе. Счетчик 11 предназначен для подсчета количества баз графа и Формирования соответствующих им адресов в пер" вом блоке б,памяти и во втором бло" ке 7 памяти.Устройство работает следующим образом.В соответствии с .топологией граФа посредством наборного поля 9 единичные уровни должны быть поданы на элементы И 44 э, что соответствует дугам из второй вершины в первую и из второй в третью. После введения топологии устройство инициируется путем подачи на его первый вход положительного запускающего импульса, который поступает на вход сброса счетчика 3 и вход вброса счетчика 11 и устанавливает эти счетчики в исходное нулевое) состояние. При этом на выходе переполнения счетчика 3 устанавливается единичный уровень, который подается на вход генератора 1 и разрешает его работу. В исходном состоянии на выходе генератора 1 присутствует единичный потенциал, поэтому формирование импульсной последовательности, поступающей на счетный вход счетчика 3 и вход элемента И 10, начинается с отрицательного перепада, По первому положительномуУстройство для исследования графов, содержащее матрицу элементов И,. наборное поле, генератор импульсов, первый счетчик, о т л и ч а ю щ е ес я тем, что, с целью расширекия з14517 перепаду уровня на выходе генератора 1 счетчик 3 устанавливается в состояние 001, при этом с его первого выхода единичный уровень поступает на вход 0 элемента ИЛИ 5 проходит через него и поступает на первую строку, которая образована вторымн входами элементов И 4, . Поскольку ни на одном первом входе элементов И 4первый строки матрицы не при 1сутствует единичный уровень (в соответствии с топологией графа), а единичный уровень присутствует только на первом выходе счетчика 3, то на 15 выходе элемента И 10 - низкий уровень. Это означает, что первая вершина не является базой графа, При поступлении на счетный вход счетчика 3 второго положительного перепа да счетчик устанавливается в состояние 010. При этом с второго выхода счетчика 3 высокий уровень поступает на вход 0 элемента ИЛИ 5, проходит через него и далее поступает на вто" 25 рую строку, которая образована вторыми входами элементов И 4, Поскопьку в соответствии с топологией графа на первые входы элементов И 4,ц, 4 поданы высокие уровни, то на их выходах также Формируются высокие уровни, которые поступают на вторые входы элементов ИЛИ 5, 5 э. Таким образом, на всех входах элемента И 10 присутствуют высокие уровни. Поэтому на его выходе также35 Формируется высокий уровеньПо поло.-. ,жительному перепаду уровня на.выходе элемента И 10, который поступает на,вход У записи блока 6 памяти и вход запуска блока 8 определения мощности базы, в нулевой адрес блока 6 памяти ,записывается код 010, соответствующий тому, что базой данного графа является вторая вершина. Одновремен но запускавтся блок 8 определения мощности базы, который преобразует код 010, поступающий на его входы с первого по третий, в код 001, который в двоичной форме соответствует тому, что мощность базы равна 1. По отрицательному перепаду уровкя на выходе элемента И 10, который поступает на вход записи, этот код записывается по нулевому адресу блока 7 памяти. По этому же перепаду уровня счетчик 11 с задержкой, определяемой параметрами элемента ИЛИ 2, устанавливается в следующее состояние,и спустя время 15задержки срабатывания счетчика на его выходе устанавливается следующий адрес, предназначенный для записи параметров следующей базы, Таким образом, при Формировании на выходе элемента И 10 единичного потенциала, который является признаком того, что текущее подмножество вершин является базой графа, происходит следующее: в блок 6 памяти записывается двоичный код, соответствующий составу базы, те. номера единичных разрядов этого кода соответствуют номерам вершин, образующих базу; с помощью блока 8 определения мощности. базы производится подсчет количества единиц в коде состава базы, что соответствует количеству вершин, входящих в базу, или ее мощности, При этом на выходе блока 8 .определения мощности базы формируется двоичный код, соответствующий мощности базы; с выхода блока 8 определения мощности базы двоичный код записывается.по.тому же адресу, что и код.состава базы, но в блок 7 памяти;.далее происходит. смена адреса блоков 7 и 6 памяти.Аналогичньпч образом устройство работает до тех пор, пока в счетчике 3 не будет выполнен перебор всех под" множеств вершин. После завершения перебора подмножеств вершин графа на выходе переполнения счетчика 3 устанавливается низкий потенциал, который запрещает работу генератора 1.В результате работы устройства получается. следующая информация о базах графа: состояние счетчика 11 соответствует количеству баз графа М;.по каждому адресу блока 6 памяти хранится двоичный код состава базы, номера единичных разрядов которого соответствуют номерам вершин; по.каждому адресу блока 7 памяти хранится. двоичный код мощности базы, код состава которой записан по соответствующему адресу блока 6 памяти. формула изобретения1451715 Вб,7 Ф Т Ю Ф,б б 7У люкма Оррс ФиМ ррррра аррар р р р р 1 ФАЗ рея Составитель О.Гречухина Рыбченко . . .Техред А.Кравчук Корректор В,ГирнякРедактор Заказ 7082/48НИИПИ Государственного113035,Тираж 667 Подписноеомитета по изобретениям и открытиям при ГКНТ СССР осква, Ж, Раушская наб., д. 4/5 еское Предприятие,роектная, 4 роизводственно-поли о, функциональных возможностей за счетнахождения баз ориентированного графа и определения их количественныххарактеристик, в него введены элемент ИЛИ, группа элементов ИЛИ,элемент И, второй счетчик, первый ивторой блоки памяти, блок определения мощности базы, вход синхронизации которого соединен с входами записи первого и второго блоков памяти, первым входом элемента ИЛИ и выходом элемента И, входы с первогопо К-й которого соединены с выходами соответствующих элементов ИЛИгруппы, а (К+1)-й вход соединен свыходом генератора импульсов и счетным входом первого счетчика, выходпереполнения которого соединен свходом останова генератора импульсов, а информационные выходЫ первогосчетчика соединены с информационнымивхоцами первого блока памяти и блокаопределения мощности базы, каждыйиз информационных выходов первогосчетчика соединен с первым входомсоответствующего элемента ИЛИ группи, входи с второго по К-й которогосоединены с выходами соответствующихэлементов И соответствующего столбцаматрицы,.а выход соединен с первымивходами элементов И соответствующейстроки матрицы, вторые входы элементов И матрицы соединены с соответствующими информационными выходами на борного поля, второй вход элементаИЛИ является входом считывания информации устройства, выход элементаИЛИ соединен со счетным входом второго счетчика, информационные выходы 15 которого соединены с адресными входами первого и второго блоков памяти и являются адресными выходами устройства, информационные выходы блокаопределения мощности базы соединены 20 с информационными входами второгоблока памяти, информационные выходыпервого и второго блоков памяти являются соответственно первым и вторыминформационными выходами устройства, 25 входы сброса первого и второго счетчиков соединены и являются входомсброса устройства.