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

СЛ

0ufff

Содержит модель исходного графа, вы- лолненную в виде наддиагональной матрицы 1 моделей 2 ребер, 3 и вторую 4 группы моделей 5 узлов, модель искомого графа, выполненную в виде матрицы 6 из моделей 7 ребер, :остоящих каждая из блока 8 элементов И, элемента ИЛИ 9 и регистра 10 для наддиагональных элементов матрицы 6 и блока 8 элементов И - для поддиагональных элементов матрицы 6, первый счетчик 11, первый 12,

50

второй 13, третий 1ч и четвертый 15 элементы ИЛ1-1, первый 16 и второй 17 распределители импульсов, г енератор 18 импульсов, элемент И 19, первь й 20 и второй 21 дешифраторы5 второй счетчик 22, Расширение функциональных возможностей достигнуто за счет присвоения узлам исходного графа новых условных номеров с одновременным формированием матрицы смежности -искомого графа. 3 ил.

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

1

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

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

На фиг. 1 представлен пример функциональной схемы устройства; на фиг.2 кодель ребра; на фиг„ 3 - модель узла

Устройство содержит (фиг, 1) модель исходного графа, выполненную я виде наддиагональной матрицы 1 из ix j (i 1, n-lj j 2,П5 п - число узлов графд) моделей 2 ребер, первую 3 и вторую 4 группы из п-1 моделей узлов, модель искомого графа, вьтол- неннуго в виде квадратной матрицы 6 из пхп моделей 7 ребер, состоящих каждая из блока 8 элементов И, элемента ИЛИ 9 и регистра 10 для над-- д.иагойальных элементов и из блока 8 элементов И для поддиагональных элементов матрицы 6, первый счетчик 11, первый 12, второй 13, третий 14 и четвертый 1.5 элементы ИЛИ, первый 16 и второй 17 распределители импульсов, генератор 18 импульсов, элемент И 19, первый 20 и второй 21 дешифраторы, второй счетчик 22.

Модель 2 (фиг. 2) содержит триггер 23, элемент И-НЕ 24, коммутатор 25, блок 26 элементов И, первый 27, второй 28 и третий 29 элементы И, первый 30 и второй 31 элементы задержки, регистр 32, входные и выходные полюса 33-43.

Модель 5 (фиг. 3) содержит первый 44 и второй 45 элементы ИЛИ, элемент - И 46, регистр 47, элемент 48 задержки, триггер 49, входные и выходные полюса 50-55.

В исходном статическом состоянии счетчик 11, дешифраторы 20, 21 регистры 10, триггеры 49 и регистры 47 обну- лены, триггеры 23 в моделях 2, соответствующих ребрам исходного графа, устанавливаются в единичное состояние, а в регистры 32 заносятся веса ребер, в счетчик 22 заносится число, дополняющее число п-1 до полной емкости счетчика. Исходное состояние распределителя 17 - произвольное,, исходное состояние распределителя 16 устанавливают таким, чтобы он выдавал единичный потенциал на выход с номером, соответствующий которому узел исходного графа выбирается в качестве первого узла искомого графа. Работу устройства рассмотрим на примере преобразования исходного графа с матрицей смежности А в искомый граф с матрицей смежности А|, причем исходное положение распределителя 16 - выдача потенциала 1 по четвертому выходу, т.е за начальный узел в искомом графе выбран чет- . вертьЕЙ узел исходного графа, а исходное положение распределителя 17 - выдача 1 по третьему выходу. Цифрами в матрицах обозначены веса ребер.

Устройство работает следующим

образом.

После занесения исходной информа- лии единичными потенциалами с выходов распределителей 16, 17 открывается элемент И 27 и блок 26 в модели 234 и вес 3 ребра (3,4) с выхода регистра 32j через блок 26j и элемент ИЛИ 12 поступает на первые входы блоков 8. Потенциал 1 с выхода элемента И 27 проходит через элемент И 28, открытый потенциалом 1 с выхода элемента И-НЕ 24, и элемент ИЛИ 13 на счетный вход счетчика 11, содержимое которого становится 1 и выставляется на информационные входы регистров 47. Сигнал с выхода элемента И 29, открытый потенциалом 1 на втором и третьем входах,- на вход элемента задержки 30. Сигнал с выхода элемента И 27 проходит также через первый выход коммутатора 25 в модель 514- , где через элементы ИЖ 44, И 46, ИЛИ 45 поступает на единичный вход триггера 49 и вход за- регистра которьй запоминает число 1. Нулевой потенциал с ир- версного выхода триггера 49 закрывает элемент И 46, исключая запись новой информации в регистр 47, а также за- крывает элементы И 29 в моделях 2 четвертого столбца матрицы 1. Потенциал 1 с прямого выхода триггера 49 поступает через полюса 34 моделей 2 четвертого столбца матрицы 1 на первые входы элементов И-НЕ 24, а через полюс 50 он проходит в модель , где через элемент ИЛИ 45 поступает на вход записи регистра 47, ко- торьй запоминает 1, и на единичный вход триггера 49, который переходит в состояние 1. Потенциал О с инверсного выхода этого триггера закрывает элемент И 46, а через полюса 37 моделей 2 четвертой строки матрицы

1поступает на третьи входы элементов И 29, закрьшая их. Потенциал 1 с прямого выхода указанного триггера через полюса 35 моделей 2 четвертой строки матрицы 1 поступает на вторые входы элементов И-НЕ 24.

С выхода элемента задержки 30 модели 2з сигнал проходит через элемент ИЛИ 13 на счетньй вход счетчика 11, содержимое которого становится равным

2и выставляется на информационные входы регистров 47. С выхода элемента задержки 31 потенциал 1 поступа0

5

0

5

0

5

0

5

0

5

ет на управляющий вход коммутатора 25, который подключает свой вход ко второму выходу, и потенциал 1 с выхода элемента И 27 через полюс 55 поступает в модель , где проходит через элементы ИЛИ 44, И 46, ИЛИ 45 на вход записи регистра 47, который запоминает число 2, и на единичный вход триггера 49, который переходит в состояние 1. Потенциал О с его инверсного выхода закрывает элемент И 46, а через полюса 37 моделей 2 третьей строки матрицы 1 поступает на третьи входы элементов И 29.Потенциал 1 с прямого выхода этого триггера через полюса 35 моделей 2 третьей строки матрицы 1 подается на вторые входы элементов И-НЕ 24, а через полюс 50 модели , и элемент ИЛИ 45 поступает на вход записи регистра 47, который запоминает число 2, и на единичный вход триггера 49.который сигналами со своего прямого и инверсного выходов производит те же действия, что и триггер 49 , .

Задержавшись в элементах задержки 48 моделей 5, 5 на время записи информации в регистры 47, импульсы с выходов этих элементов поступают на входы считывания регистров 47 с выходов которых числа 1, 2 через элементы ИЛИ 14, 15 поступают на входы дешифраторов 20, 21 которые вьщают единичные импульсы соответственно по первому и второму выходам, открывая в модели 7 блок 8. Тогда поданное на его первый вход число 3 проходит через элемент ИЛИ 9 и записывается в регистр 10.

После подачи сигнала на вход запуска генератор 18 вьщает импульсы, при поступлении первого из которых распределитель 16 выдает единичный потенциал по пятому выходу, открывая в модели 2 jj элемент И 27 и блок 26, через который записанный в регистре 32 вес 7 ребра (3,5) исходного графа проходит через элемент ИЛИ 12 на первые входы блоков 8. В модели 2 на входах элемента И-НЕ 24 присутствуют потенциалы О и 1, на его выходе - потенциал 1, поэтому единичный сигнал с выхода элемента И 27 проходит через элемент И 28 и элемент ИЛИ 13 на счетный вход счетчика 11, содержимое которого становится равным 3 и выставляется на информационные входы регистров 47. Элемент И 29 модели

2-j закрыт потенциалом О с инверсного выхода триггера з s поэтому единичный сигнал с выхода элемента И 27 проходит только на вход элемента задержки 31 и на первый выход коммута тора 25, откуда поступает на полюс 5 модели 5 , где через элемент ИЛИ 44 проходит на вход элемента задержки 48, а через элементы И 46, ИЛИ 45 - на вход записи регистра 47, который запоминает число 3, и на единичный вход триггера 49, который переходит в единичное состояние. Потенциал О с инверсного выхода триггера 49-с закрывает элемент И 46

lf

а через полюса 36 моделей 2 пятого столбца матрицы 1 поступает на вторые входы элементов И 29 и закрывает их. Потенциал 1 с прямого выхода триггера 49, через полюс 50 модели 5j; и далее через элемент ИЛИ проходит на вход записи регистра 7 , который запоминает число 3, и на единичный вход тригге- ра 49(5 который переходит в состояние 1 и сигналами с прямого и инверсного выходов производит такие же действия, как и триггер 49. Единич шй сигнал с прямого выхода триггера 49 через полюса 34 моделей 2 пятог столбца матрицы 1 поступает на первы входы элементов И-НЕ 24. При вьщаче элементом 31 задержки сигнала на управляющий вхо;; коммутатрр а 25 он под ключает свой вход ко второму выходу. Тогда в модели 2, единичный сигнал с выхода элемента И 27 поступает чер второй выход коммутатора 25 на полюс 55 модели 5,}, где проходит через элемент ИЛИ 44 на вход элемента 8 задержки, в то время, как элемент И 4623 закрыт. По истечении времени задержки элементы 48 , задержки выдают импульсы на входы считыва- ния регистров 7, 7, с выходов которых числа 3 и 2 через элементы ИЛИ 14, 15 поступают на входы дешифрторов 20, 21. Они выдают единичные сигналы соответственно по третьему и второму выходам, открывая блок Sj для прохождения выставленного на его первом входе числа 7 через элемент ИЛИ 9 модели 7 в регистр 10,з

Следующий импульс генератора 18 проходит, во-первых, на вход распределителя 16, во-вторых, через открытый элемент И 19 на вход распределитля 17. Распределитель 16 вьщает еди

5

0

5 Q 0 Q

5

ничный сигнал по второму выходу (выходы распределителя пронумерованы с второго по п-й), а распределитель

17- по первому выходу. При этом в - модели 2 открывается элемент И 27 и и далее происходят аналогичные процессы, в результате которых в регистрах 47 моделей 5 , 5,j записывается число 4, а в регистре 47 модели 52, - число 5. Вес 6 ребра (1,2) исходного графа записывается в регистр 10 модели 7 квадратной матри1да 6.

Далее очередной импульс генератора

18приводит к выдаче распределителем 16 единичного потенциала по третьему выходу, в модели 2 открывается элемент И 27, вес 5 ребра (1,3) исходного графа записывается в регистр 10 модели 7j квадратной матрицы 6. После вьщачи очередных импульсов генератором 18 распределитель 16 выдает единичный потенциал по четвертому, а распределитель 17 - по второму выходам, в моде ли 2 , открывается элемент, И 27, после чего в регистр 10 модели 7 записывается вес 2 ребра (2,4) исходного графа.

Каждый раз при появлении импульса на выходе элемента И 19 содержимое счетчика 22 увеличивается на 1 и при его переполнении на соответствующий выход устройства вьщается сигнал окончания его работы. При этом в регистрах 47 записаны номера узлов искомого графа, а в регистрах 10 - веса его ребер (в наддиагональных элементах) , Квадратная матрица 6 представля- ет собой матрицу смежности искомого графа.

Формула изобретения

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

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

0

5

0

5

0

5

0

5

5

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

9 - 141 третьими входами третьих элементов И моделей ребер соответствуняцих строк иаддиагональной матрицы, выход генератора импульсов соединен с входом -г первого распределителя импульсов и с первым входом элемента И устройства, выход которого соединен с входом второго счетчика устройства и с входом второго распределителя импульсов, i - и выход которого соединен с вторыми входами первых элементов И и с вторы005010

ми входами блоков элементов И моделей ребер - и строки наддиагональной матрицы, j - и выход первого распределителя импульсов соединен с третьи ми входами первых элементов И и третьими входами блоков элементов И моделей ребер j - го столбца наддиагональной матрицы, п т и выход первого распределителя импульсов соединен с вторым входом элемента И устройств- ва.

10

8)

Фиг. 2

Фиг.