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

СХ)

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

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

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

На фиг. 1 приведена структурная схема устройства; на фиг. 2 - структурная схема модели дуги.

Устройство содержит генератор 1 тактовых импульсов, первьй элемент И 2, вход 3 пуска устройства, первый элемент НЕ 4, дешифратор 5, выход 6 признака окончания работы устройства первый счетчик 7, первую 8 и вторую 9 группы элементов ИЛИ, матрицу моделей 10 дуг, первую группу элементов И 11, вторую группу элементов И 12, первый выход 13 моделей 10 дуг, второй выход 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 начапь

10

15

20

25

30

35

-40

45

50

55

ной установки. При этом сигналы опроса матрицы моделей дуг с выхода дешифратора 5 отсутствуют и на всех выходах 13, 14 моделей дуг i О, имеются логические О, которые через элементы И 17 поступают на информационный выход устройства, на выходе элемента НЕ 4 - 1.

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

При подаче на вход 3 сигнала Пуск, имеющего уровень 1, импульсы с генератора 1 тактовых импульсов через элемент И 2 начиншот поступать к счетчику 7, состояние которого преобразуется дешифратором 5 в позиционный код. Изменение состояния счетчика 7 изменяет положение 1 на выходах дешифратора 5, что обеспечивает последовательный опрос строк и столбцов;, матрицы моделей 10 дуг. Опрос матрицы моделей 10 дуг состоит в следующем. На такте К счетчика 7 сигнал опроса в виде 1 с К-го выхода дешифратора 5 поступает через элемент ИЛИ 8 и открытый тактовым им- пульсрм элемент И 11 на входы 15 моделей 10 дуг К-й строки матрицы, а через элементы ИЛИ 9 и И 12 на входы 16 моделей 0 дуг К-го столбца матрицы. При этом на выходах 13 моделей 10 дуг К-й строки матрицы в триггерах 30 которых содержится 1, также появляется 1, которая вызывает появление 1 на выходе элемента ИЛИ 8, что приводит к появлению сигнала опроса в М-й строке матрицы моделей дуг и т.д. Наличие 1 на выходе соответствующего элемента ИЛИ 8 при опросе строки К означает существование в исследуемом графе пути из вершины с индексом К в верпшну с индексом Р. Аналогично на выходах 14 моделей 10 дуг К-го столбца матрицы, в триггерах 30 которых содержится 1, также появляется 1, вызьшающая появление 1 на выходах соответствую- ших элементов ИЛИ 9, а значит, и опрос соответствуюш 1Х столбцов матрицы. Наличие 1 на вьпсоде Р-го элемента ИЛИ 9 второй группы при опросе столб-г ца К означает существование пути из вершины с индексом Р в вершину с индексом К.. Таким образом, при опросе строки К и столбца К наличие 1 на

выходах элементов ИЛИ 8 первой группы определяет множество вершин, связанных с вершиной К путями, в которых К является начальной, а наличие 1 на выходах элементов ИЛИ 9 второй группы - множество вершин, связанных путями с К; в которых К является конечной. Индексньй состав этих множеств определяется соответственно номерами элементов ИЛИ первой 8 и второй 9 группы. Пересечение данны множеств определяет состав множества вершин, являющихся носителями компоненты сильной связности, содержащей вершину К.Пересечение отыскиваете на элементах И 18 четвертой группы и поступает в виде кода с единицами в разрядах, номера которых

к второму счетчику 26. Тем самым будет подтвержден вывод информации о носителях очередной компоненты сильной свяэности с выходов 21 . Задержка тактового импульса с генератора 1 элементом 25 необходима для устранения влияния переходных процессов и временной задержки при опросе матрицы моделей 10 дуг на достоверность информации. Задержанный тактовый импульс также поступает на вход записи регистра 20, что обеспечивает фиксацию новой информации. Поскольку выходы регистра 20 через элементы ИЛИ 19 третьей группы соединены с его же входами, то на каждом такте происходит поразрядное объединение текущего кода пересечения множеств с зафик

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

соответствуют индексам вершин - носи-20 сированными ранее. Тем самым исключается потеря информации, полученной на предыдущих тактах.

Группы элементов И 11, 12 служат для предотвращения искажения резуль- 25 тирующей информации из-за наличия обратных связей в целях опроса мат- модели 10 дуг. При переходе тактового импульса в уровень О элементы И 11, 12 закрываются по второму

телям полученной компоненты сильной связности, на выходы 21 устройства через элементы ИЛИ 19 на входы регистра 20. Код пересечения также поступает к четвертой группе элементов И 18, в которых осуществляется его сравнение с кодами носителей компонент сильной связности, полученными на предьщущих тактах с целью исключения дублирования информации. Посколь- 30 входу, тем самым разрывая цепи рпро- ку ни одна вершина графа не может . са строк и столбцов матрицы моделей одновременно принадлежать двум различ- .10 дуг и исключая прохождение сигна- ным компонентам сильной связности, то при совпадении текущего кода с записанными в регистре 20 хотя бы в 35 одном разряде на выходе элемента ИЛИ 22 появляется 1, поступающая на вход второго элемента НЕ 23 и запрещающая прохождение тактового импульса на выход 27 синхронизации вывода 4р и к второму счетчику 26. Тем самым блокируется появление синхросигнала, являющегося признаком вывода информации с выходов 21, и изменение содержимого второго счетчика 26, учитываю- 45 работы, который поступает на выход 6 щего число компонент сильной связ- устройства и на элемент НЕ 4. Нулевой ности в исследуемом графе. В случае получения информации о компоненте сильной связности, не зафиксированной на предыдущих тактах, ни в одном из 50 разрядов сравниваемых кодов совпадения .не будет и на выходах всех элементов четвертой группы И 18 будут логические О. На выходе элемента ИЛИ 22 также будет О, который через 55 элементы НЕ 23 и 24 И разрешит прохождение тактового импульса с генератора 1 на выход синхронизации 27 и

лов уровня 1 по этим цепям с выходов элементов ИЛИ первой 8 и второй 9 групп на их же входы.

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

При достижении первым счетчиком 7 соответствующего состояния на последнем выходе дешифратора 5 появляется сигнал, служащий признаком окончания

сигнал с выхода элемента НЕ А блокирует прохождение тактовых импульсов с генератора 1 через элемент И 2. В счетчике 26 фиксируется общее число компонент сильной связности исследуемого графа. При этом работа устройства заканчивается.

После обнуления регистра 20, первого 7 и второго 26 счетчиков сигналом на входе 29 начальной установки и занесения исходной информации о .

чается потеря информации, полученной на предыдущих тактах.

Группы элементов И 11, 12 служат для предотвращения искажения резуль- 25 тирующей информации из-за наличия обратных связей в целях опроса мат- модели 10 дуг. При переходе тактового импульса в уровень О элементы И 11, 12 закрываются по второму

30 входу, тем самым разрывая цепи рпро- . са строк и столбцов матрицы моделей .10 дуг и исключая прохождение сигна- 35 4р 45 работы, который поступает на выход 6 устройства и на элемент НЕ 4. Нулевой 50 55

входу, тем самым разрывая цепи рпро- са строк и столбцов матрицы моделей .10 дуг и исключая прохождение сигна- работы, который поступает на выход 6 устройства и на элемент НЕ 4. Нулевой

лов уровня 1 по этим цепям с выходов элементов ИЛИ первой 8 и второй 9 групп на их же входы.

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

При достижении первым счетчиком 7 соответствующего состояния на последнем выходе дешифратора 5 появляется сигнал, служащий признаком окончания

входу, тем самым разрывая цепи рпро- са строк и столбцов матрицы моделей .10 дуг и исключая прохождение сигна- работы, который поступает на выход 6 устройства и на элемент НЕ 4. Нулевой

сигнал с выхода элемента НЕ А блокирует прохождение тактовых импульсов с генератора 1 через элемент И 2. В счетчике 26 фиксируется общее число компонент сильной связности исследуемого графа. При этом работа устройства заканчивается.

После обнуления регистра 20, первого 7 и второго 26 счетчиков сигналом на входе 29 начальной установки и занесения исходной информации о .

топологии исследуемого графа устройство готово к следующему циклу работы .

Формула изобретения Устройство для исследования связности графов, содержащее генератор тактовых импульсов, первый элемент И, первую и вторую группы элементов И, первый элемент НЕ, дешифратор, матрицу моделей дуг, первый счетчик, информационные выходы которого соединены с информационными входами дешифратора, а счетный вход соединен с выходом первого элемента И, первый вход которого является входом пуска устройства, второй вход соединен с. выходом генератора тактовых импульсов, а третий вход г с выходом пер- вого элемента НЕ, вход которого соединен с (К+1 )-м выходом дешифратора (где К - количества вершин в графе), отличающееся тем, что, с целью расширения функциональных воз- можностей за счет определения носителей компонент сильной связности, в устройство введены первая, вторая и третья группы элементов ИЛИ, третья и четвертая группы элементов И, регистр, второй элемент задержки, элемент ИЛИ, второй элемент НЕ, второй элемент И, второй счетчик, счет- цый вход которого соединен с выходом второго элемента И, первый вход которого соединен с выходом второго элемента НЕ, вход которого соединен с выходом элемента ИЛИ, входы которого соединены с выходами соответствующих элементов И четвертой группы, первые входы которых соединены с первыми входами соответствующих элементов ИЛИ -третьей группы, выходами соответствующих элементов И и являются первой группой информационных выхо- доз устройства, информационные выходы вто.рого счетчика являются вторыми информационными выходами устрой

0 5 0 5 О 0 5

5

ства, счетный вход второго счет; ика является тактовым выходом устройства, а вход сброса второго счетчика соединен с входами сброса первого счетчика и регистра и является входом сброса устройства, вход первого элемента НЕ соединен с выходом признака окончания цикла работы устройства, информационные выходы регистра соединены с вторыми входами соответствующих элементов И четвертой группы и элементов ИЛИ третьей группы, выходы элементов ИЛИ третьей группы соединены с соответствующими информа- ционньгми входами регистра, вход записи которого соединен с вторым входом второго элемента И и выходом второго элемента задержки, вход которого сое- сдинен с выходом первого элемента И, первые входы элементов И первой и второй групп объединены и соединены с выходом первого элемента И, М-й выход дешифратора (где М,,.,,К) соединен с первыми входами М-х .элементов ИЛИ первой и второй групп, входы с второго по К-й М-го элемента ИЛИ первой группы соединены с первыми выходами соответствующих им моделей дуг М-го столбца матрицы, вых,од М-го элемента ИЛИ первой группы соединен с вторыми входами соответствующих М-х.элементов И первой и третьей групп, вькод М-го элемента И первой группы соединен с первыми входами моделей дуг М-й строки матрицы, выход М-го элемента ИЛИ второй группы соединен с первым входом соответствую- Diero М-го элемента И третьей группы и вторым входом соответствующего М-го элемента И третьей группы, входы с второго по К-й М-го элемента ИЛИ второй группы соединены с вторыми выходами соответств- тощих моделей дуг М-й строки матрицы, выход М-го элемента И второй гр-уппы соединен с вторыми входами моделей дуг М-го столбца матрицы.

Фи$.1

Фиг. 2