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

СОЮЗ СОВЕТСНИХСОЦИАЛ ИСТИЧЕСНИРЕСПУБЛИН 671 2 АВТОРСКОМУ С ДЕТЕЛЬСТВУ ускающих теореление. Цель ние функциональет определения лъиой связнос решении з о-графовое бретения -п т адач, допредста расшире стей за с ых возможн носителеи компоне ти - достигво, содержаимпульсов,элеменвую и в.к матрицу мод введены тре элементовпы элементсчетчик, вэлемент НЕи элемент ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОбРЕТЕНИЙ И ОТНРЫТИЙ ОПИСАНИЕ ИЗОБРЕТЕН(71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) О .Н,Костюк(56) Авторское свидетельство СССР В 1124318, кл. О 06 Г 15/20, 1984.Авторское свидетельство СССР У 174937, кл, О 06 Г 15/20, 1985(54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ СВЯЗНОСТИ ГРАФОВ(57) Изобретение относится к области вычислительной техники и может быть использовано для исследования графов ется тем, что в устройстщее генератор тактовыхлемент НЕ, элемент задержИ, счетчик, дешифратор, рую группы элементов И, елей дуг, дополнительноья и четвертая группыс первой по третью групИЛИ, регистр, второйрой элемент И, второйвтброй элемент задержки ИЛИ. 2 ил.Изобретение относится к вычислительной технике и может быть использовано для исследования графов прирешении задач, допускающих теоретико-графовое представление.Цель изобретения - расширениефункциональных возможностей устройства за счет определения носителейкомпонент сильной связности, ОИнформация о. топологии исследуемого графа заносится в триггеры моделей дуг в виде матрицы смежности. Входе работы устройства на основанииэтой информации определяется состав 5носителей для каждой компоненты сильной связности исследуемого графа,т.е. осуществляется разбиение множества вершин графа на подмножества,каждое из которых образуется сильносвязными вершинами, определяется также число таких подмножеств,На фиг. 1 приведена структурнаясхема устройства; на фиг. 2 - структурная схема модели дуги.Устройство содержит генератортактовых импульсов, первый элемент И2, вход 3 пуска устройства первыйэлемент НЕ 4, дешифратор 5, выход бпризнака окончания работы устройства, 30первый счетчик 7, первую 8 и вторую9 группы элементов ИЛИ, матрицу мо-.делей 10 дуг, первую группу элементов И 11, вторую группу элементов И12, первый выход 13 моделей О дуг,второй выход 14 моделей 10 дуг, первый вход 15 моделей 10 дуг, второйвход 16 моделей 10 дуг, третью 17и четвертую 18 группы элементов И,третью группу элементов ИЛИ 19, ре Огистр 20, первые информационные выходы 21 устройства, элемент 22 ИЛИ,второй элемент НЕ 23, второй элементИ 24, элемент 25 задержки, второчсчетчик 26, выход синхронизации 27устройства, вторые информационныевыходы 28 устройства, вход, 29 начальной установки.Каждая модель 10 дуги содержиттриггер 30, первый элемент И 31, второй элемент 32 задержки.Устройство работает следующим образом.В исходном состоянии работа устройства заблокирована нулевым сигналом на входе 3 пуска устройства, всчетчиках 7, 26 и регистре 20,хранятся "О" во всех разрядах, что обеспечивается сигналом на входе 29 начальной установки. При этом сигналы опроса матрицымоделей дуг с выхода дешифратора 5 отсутствуют и на всех выходах 13, 14 моделей дуг 10,имеютсялогические "О", которые через элементы И 17 поступают на информационныйвыход устройства, на выходе элементаНЕ 4 - "1" Исходная информация о топологииисследуемого графа заносится в триггеры 30 моделей дуг, после чего устройство готово к работе,При подаче на вход 3 сигнала"Пуск", имеющего уровень "1", импульсы с генератора 1 тактовых импульсов через элемент И 2 начинают поступать к счетчику 7, состояние которого преобразуется дешифратором 5 впозиционный код. Изменение состояниясчетчика 7 изменяет положение "1" навыходах дешифратора 5, что обеспечивает последовательный опрос строк истолбцов.,матрицы моделей 10 дуг.Опрос матрицы моделей 10 дуг состоитв следующем, На такте К счетчика 7сигнал опроса в виде "1" с К-го выхода дешифратора 5 поступает через элемент ИЛИ 8 и открытый тактовым импульсом элемент И 11 на входы 15 моделей 10 дуг К-й строки матрицы, ачерез элементы ИЛИ 9 и И 12 на входы1 б моделей 10 дуг К-го столбца матрицы. При этом на выходах 13 моделей10 дуг К-й строки матрицы в триггерах30 которых содержится "1", также появляется "1", которая вызывает появление "1" на выходе элемента ИПИ 8,что приводит к появлению сигналаопроса в И-й строке матрицы моделейдуг и т,д. Наличие " на выходе соответствующего элемента ИЛИ 8 приопросе строки К означает существование в исследуемом графе пути из вершины с индексом К в вершину с индексом Р, Аналогично на выходах 14 моделей 10 дуг К-го столбца матрицы, втриггерах 30 которых содержится "1",также появляется , вызывающая появление "1" на выходах соответствующих элементов ИЛИ 9, а значит, и опрос соответствующих столбцов матрицы.Наличие "1" на выходе Р-го элементаИЛИ 9 второй группы при опросе столб-ца К означает существование пути извершины с индексом Р в вершину с индексом К. Таким образом, при опросестроки К и столбца К наличие "1" наПосле обнуления регистра 20, первого 7 и второго 26 счетчиков сигналом на входе 29 начальной установки и занесения исходной информации о 144480 выходах элементов ИЛИ 8 первой группы определяет множество вершин, связанных с вершиной К,путями, в которых К является начальной, а наличие 11 иф 51 на выходах элементов ИЛИ 9 второй группы - множество вершин, связанных путями с К, в которых К является конечнойИндексный состав этих множеств определяется соответствен О но номерами элементов ИЛИ первой 8 и второй 9 группы. Пересечение данных множеств определяет состав множества вершин, являющихся носителями компоненты сильной связности, содер жащей вершину К. Пересечение отыскивается на элементах И 18 четвертой группы и поступает в виде кода с единицами в разрядах, номера которых соответствуют индексам вершин - носи телям полученной компоненты сильной связности, на выходы 21 устройства через элементы ИЛИ 19 на входы регистра 20. Код пересечения также поступает к четвертой группе элементов И 18, в которых осуществляется его сравнение с кодами носителей компонент сильной связности, полученными на предыдущих тактах с целью исключения дублирования информации, Посколь- ЗО ку ни одна вершина графа не может одновременно принадлежать двум различным компонентам сильной связности, то при совпадении текущего кода с записанными в регистре 20 хотя бы в одном разряде на выходе элемента ИЛИ 22 появляется "1", поступающая на вход второго элемента НЕ 23 и запрещающая прохождение тактового импуль" са на выход 27 синхронизации вывода 40 и к второму счетчику 26. Тем самым блокируется появление синхросигнала, являющегося признаком вывода информа ции с выходов 21, и изменение содержимого второго счетчика 26, учитываю щего число компонент сильной связности в исследуемом графе, В случае получения информации о компоненте сильной связности, не зафиксированной на предыдущих тактах, ни в одном из 50 разрядов сравниваемых кодов совпадения не будет и на выходах всех элементов четвертой группы И 18 будут логические "0". На выходе элемента ИЛИ 22 также будет "0", который через 55 элементы НЕ 23 и 24 И разрешит прохождение тактового импульса с генератора 1 на выход синхронизации 27 и 74к второму счетчику 26. Тем самым будет подтвержден вывод информации о носителях очередной компоненты сильной связности с выходов 21 . Задержка тактового импульса с генератора 1 элементом 25 необходима для устранения влияния переходных процессов и временной задержки при опросе матрицы моделей 1 О дуг на достоверность информации. Задержанный тактовый импульс также поступает на вход записи регистра 20, что обеспечивает фиксацию новой информации. Поскольку выходы регистра 20 через элементы ИЛИ 19 третьей группы соединены с его же входами, то на каждом такте происходит поразрядное объединение текущего кода пересечения множеств с зафиксированными ранееТем самым исключается потеря информации, полученной на предыдущих тактах.Группы элементов И 11, 12 служат для предотвращения искажения результирующей информации из-за наличия обратных связей в целях опроса матрицы модели 10 дуг. При переходе тактового импульса в уровень "0" элементы И 11, 12 закрываются по второму входу, тем самым разрывая цепи опроса строк и столбцов матрицы моделей .1 О дуг и исключая прохождение сигналов уровня "1" по этим цепям с выходов элементов ИЛИ первой 8 и второй 9 групп на их же входы.Аналогичным образом в ходе последующих тактов определяются другие множества носителей по всем компонентам сильной связности исследуемого графа,При достижении первым счетчиком 7 соответствующего состояния йа последнем выходе дешифратора 5 появляется сигнал, служащий признаком окончания работы, который поступает на выход 6 устройства и на элемент НЕ 4, Нулевой сигнал с выхода элемента НЕ 4 блокирует прохождение тактовых импульсов с генератора 1.через элемент И 2. В счетчике 26 фиксируется общее число компонент сильной связности исследуемого графа. При этом работа устройства заканчивается.топологии исследуемого графа устройство готово к следующему цнклу работы. Формула изобретенияУстройство для исследования связности графов, содержащее генератор тактовых импульсов, первый элемент И, первую и вторую группы элементов И, первый элемент НЕ, дешифратор, матрицу моделей дуг первый счетчик, информационные выходы которого соединены с информационными входами дешифратора, а счетный вход соединен с выходом первого элемента И, первый вход которого является входом пуска устройства, второй вход соединен с, выходом генератора тактовых импульсов, а третий входс выходом первого элемента НЕ, вход которого соединен с (К+1)-м выходом дешифратора (где К - количества вершин в графе), отличающееся тем, что, с целью расширения функциональных возможностей за счет определения носителей компонент сильной связности в устройство введены первая, вторая и третья группы элементовИЛИ, третья и четвертая группы элементов И, регистр, второй элемент задержки, элемент ИЛИ, второй элемент НЕ, второй элемент И, второй счетчик, счетный входкоторого соединен с выходом второго элемента И, первый вход которого соединен с выходом второго элемента НЕ, вход которого соединен с выходом элемента ИЛИ, входы которого соединены с выходами соответствующих элементов И четвертой группы, первые входы которых соединены с первыми входами соответствующих элементов ИЛИ третьей группы, выходами соответствующих элементов И и являются первой группой информационных выходов устройства, информационные выходы второго счетчика являются вторыми информационными выходами устрой 5 10 15 20 25 30 35 40 45 ства, счетный вход второго счетчикаявляется тактовым выходом устройства,а вход сброса второго счетчика соединен с входами сброса первого счетчика и регистра и является входомсброса устройства, вход первого элемента НЕ соединен с выходом признакаокончания цикла работы устройства,информационные выходы регистра соединены с вторыми входами соответствующих элементов И четвертой группыи элементов ИЛИ третьей группы, выходы элементов ИЛИ третьей группы соединены с соответствующими информационными входами регистра, вход записи которого соединен с вторым входомвторого элемента И и выходом второгоэлемента задержки, вход которого соединен с выходом первого элемента И,первые входы элементов И первой ивторой групп объединены и соединеныс выходом первого элемента И, М-йвыход дешифратора (где М=1 К)соединен с первыми входами М-х .элементов ИЛИ первой и второй групп,входы с второго по К-й М-го элементаИЛИ первой группы соединены с первыми выходами соответствующих им моделей дуг М-го столбца матрицы, выходМ-го элемента ИЛИ первой группы соединен с вторыми входами соответствующих М-х элементов И"первой и третьейгрупп, выход М-го элемента И первойгруппы соединен с первыми входамимоделей дуг М-й строки матрицы, выходМ-го элемента ИЛИ второй группы соединен с первым входом соответствующего М-го элемента И третьей группыи вторым входом соответствующего М-гоэлемента И третьей группы, входы свторого по К-й М-го элемента ИЛИ второй группы соединены с вторыми выходами соответствующих моделей дуг М-йстроки матрицы, выход М-го элементаИ второй группы соединен с вторымивходами моделей дуг М-го столбца матрицы.Заказ 6508/50 Ужгород, ул, Проектная,ственно-полиграфическое предприя 1 ро Тираж704 ВНИИПИ Государстве по делам изобре 035, Москва,.Ж, Подписого комитета СССРний и, открытийаушская наб., д. 4/5