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

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (51)4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н АBTOPCHQMV СВИДЕТЕЛЬСТВУ (21) 4111813/24-24 (22) 22,08.86 (46) 15.07.88. Бюл. В 26 (72) E.Ä.Áîáðàêoâ, П.П.Лебедев и С.В.Данилов (53) 681.333 (088.8) (56) Авторское свидетельство СССР ,Ф 1024930, кл. G 06 F 15/20, 1982, Авторское свидетельство СССР ,Ф 732898, кл. G 06 G 7/122, 1977.,Л0, 1410050 А 1 (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ

ГРАФОВ. (57) Изобретение относится к области вычислительной техники и может быть использовано при моделировании сетевых структур, отображаемых графами.

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

1410050 содержит модель исходнОГО графя вы

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

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

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

11умерации узлов графа.

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

Устройство содержит (фиг. 1) 15 модель исходного графа, выполненную в виде няддиягоняльной матрицы f из

ix j (i = 1, п-1, j = 2,n, n — число узлов графа) моделей 2 ребер, первую

3 и вторую 4 группы из п-1 моделей 20 узлов, модель искомого графа, выполненную в виде квадратной матрицы 6 из пхп .моделей 7 ребер, состоящих каждая из блока 8 элементов И, элемента ИЛИ 9 и регистра 10 для над- 25 диагональных элементов и из блока 8 элементов И для поддиагональных элементов матрицы 6, первый счетчик 11, первый 12, второй 13, третий 14 и четвертый 15 элементы ИЛИ, первый l6 30 и второй 17 распределители импульсов, генератор 18 импульсов, элемент И 19, первый 20 и второй 21 дешифраторы, второй счетчик 22.

Модель 2 (фиг. 2) содержит триггер >>

23, элемент И- IF. 24, коммутатор 25, блок 26 элементов И, первый 27, второй 28 и третий 29 элементы И, первый

30 и второй 31 элементы задержки, регистр 32, входные и выходнь|е полюса

33-43. второй 13, третий 14 и четвертый 15 элементы ИЛИ, первыи 16 и второй 17 распределители импульсов, генератор

18 импульсов, элемент И 19, первый

20 и второй 21 дешифряторь1, второй счетчик 22. Расширение функциональных возможностей достигнуто за счет присвоения узлам исходного графа новых условных номеров с одновременным формированием матрицы смежности искомого графа. 3 ил.

Модель 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" по третьему выходу. Цифрами в матрицах обозначены веса ребер.

1410050

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

После занесения исходной информации единичнымы потенциалами с выходов 5 распределителей 16, 17 открывается элемент И 27 и блок 26 в модели 2э и вес 3 ребра (3,4) с выхода регистра

32 через блок 26 и элемент ИЛИ 12 поступает на первые входы блоков 8.

Потенциал " 1" с выхода элемента И 27 проходит через элемент И 28, открытый потенциалом "1" с выхода элемента И-НЕ )

24, и элемент ИЛИ 13 на счетный вход счетчика 11, содержимое которого ста15 новится "1" и выставляется на информационные входы регистров 47. Сигнал с выхода элемента И 29, открытый потен циалом "1" на втором и третьем входах,. на вход элемента задержки 30. Сигнал с выхода элемента И 27 проходит так-: же через первый выход коммутатора 25 в модель 5, где через элементы

ИЛИ 44, И 46, ИЛИ 45 поступает на единичный вход триггера 49 и вход записи регистра 47, который запоминает число 1. Нулевой потенциал с инверсного выхода триггера 49 закрывает элемент И 46, исключая запись новой информации в регистр 47, а также за-, 30 крывает элементы И 29 в моделях 2 четвертого столбца матрицы 1. Потенциал "1" с прямого выхода триггера

49, поступает через полюса 34 моделей 2 четвертого столбца матрицы 1 З

1 на первые входы элементов И-НЕ 24, а через полюс 50 он проходит в модель

5, где через элемент ИЛИ 45 поступает на вход записи регистра 47, ко40 торый запоминает 1, и на единичный вход триггера 49, который переходит в состояние "1". Потенциал "0" с инверсного выхода этого триггера закрывает элемент И 46, а через полюса 37 моделей 2 четвертой строки матрицы

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

С выхода элемента задержки 30 модели 2> сигнал проходит через элемент

ИЛИ 13 на счетный вход счетчика t 1, содержимое которого становится равным

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

25, который подключает свой вход ко второму выходу, и потенциал " 1" с выхода элемента И 27 через полюс 55 поступает в модель 5 g, где проходит через элементы ИЛИ 44, И 46, ИЛИ 45 на вход записи регистра 47, который запоминает число 2, и на единичный вход триггера 49, который переходит в состояние " 1". Потенциал "0" с его инверсного выхода закрывает элемент

И 46, а через полюса 37 моделей 2 третьей строки матрицы 1 поступает на третьи входы элементов И 29.Потенциал "1" с прямого выхода этого триггера через полюса 35 моделей 2 третьей строки матрицы 1 подается на вторые входы элементов И-НЕ 24, а через полюс 50 модели 5< и элемент ИЛИ 45 поступает на вход записи регистра 47, который запоминает число 2, и на единичный вход тгиггера 49. который curiiy налами "со своего прямого и инверсного выходов производит те же действия, что и триггер 49, Задержавшись в элементах задержки

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

После подачи сигнала на вход запус" ка генератор 18 выдает импульсы, при поступлении первого из которых распределитель 16 выдает единичный потенциал по пятому выходу, открывая в модели 2 элемент И 27 и блок 26, через который записанный в регистре

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

5, 141005

2 закрыт потенциалом "0" с инверсного выхода. триггера 49,, поэтому единичный сигнал с выхода элемента

И 27 проходит только на вход элемента задержки 31 и на первый выход коммута. тора 25, откуда поступает на полюс

+5 модели 5,, где через элемент

ИЛИ 44 проходит на вход элемента задержки 48, а через элементы И 46, ИЛИ 45 — на вход записи регистра 47, который запоминает число 3, и на еди( ничный вход триггера 49, который ( переходит в единичное состояние. Потенциал "0" с инверсного выхода триг- 1 гер 49„ закрывает элемент И 461,, а через полюса 36 моделей 2 пятого столбца матрицы 1 поступает на вторые входы элементов И 29 и закрывает их, Потенциал " 1" с прямого выхода триггера 49, через полюс 50 модели 5 - и далее через элемент

ИЛИ 45 проходит на вход записи регистра 47, который запоминает число 3, и на единичный вход триггера 49<, который переходит в состоян 1! ние 1 и сигналами с прямого и инверсного выходов производит такие же действия, как и триггер 49 . Единичный сигнал с прямого выхода триггера (49 через полюса 34 моделей 2 пятого столбца матрицы 1 поступает на первые

1 входы элементов И-НЕ 24. При выдаче элементом 31 задержки сигнала на управляющий вход коммутатора 25 он под- . ( с 35 ключает свои вход ко второму выходу, Тогда в модели 2 единичный сигнал с выхода элемента И 27 поступает через второй выход коммутатора 25 на полюс

55 модели 5, где проходит через элемент ИЛИ 44 на вход элемента 48>> задержки, в то время, как элемент

И 46 закрыт. По истечении времени задержки элементы 481, 48 задержки выдают импульсы на входы считыва- 4> ния регистров 47„, 47,, с выходов которых числа 3 и 2 через элементы

ИЛИ 14, 15 поступают на входы дешйфраторов 20, 21. Они выдают единичные сигналы соответственно по третьему и второму выходам, открывая блок 89 для прохождения выставленного на его первом входе числа 7 через элемент

ИЛИ 9 модели 7 в регистр 10>з

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

17 — по первому выходу. При этом в модели 21 открывается элемент И 27 и и далее происходят аналогичные процессы, в результате которых в регистрах

47 моделей 517, 5<< записывается число 4, а в регистре 47 модели 5, число 5. Вес 6 ребра (1,2) исходного графа записывается в регистр 10 модели 7д квадратной матрицы 6.

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

18 приводит к выдаче распределителем

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

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

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

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

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

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

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

35 регистра модели узла, выход элемента

И модели узла соединен с первым входом второго элемента ИЛИ, выход которого соединен с входом разрешения записи регистра и с входом установки 4О в "1" триггера, инверсный выход кото-рого соединен с вторым входом элемента И модели узла, выход блока элементрв И наддиагональной модели ребра квадратной матрицы соединен с первым 4> входом элемента ИЛИ, выход которого соединен с входом регистра наддиагональной модели ребра квадратной матрицы, выходы блоков элементов И поддиагональных моделей ребра j — го столб- О ца квадратной матрицы соединены с вторыми входами элементов ИЛИ наддиагональных моделей ребер — и строки квадратной матрицы, первые выходы коммутаторов моделей ребер j — го столб-Ь5 ца наддиагональной матрицы подключены к группе входов первого элемента ИЛИ

) — и модели узла первой группы (3 — 2,...,n) вторые выходы коммутаторов моделей ребер i —,й строки наддиагональной матрицы подключены к группе входов первого элемента ИЛИ i — и модели узла второй группы (i = 1,..., и-1) выходы регистров моделей узлов первой группы соединены с группой входов первого элемента ИЛИ устройства, выходы регистров моделей узлов второй группы соединены с группой входов второго элемента ИЛИ устройства, выход первого элемента ИЛИ устройства соединен с входом первого дешифратора устройства, выход второго элемента ИЛИ соединен с входом второго дешифратора устройства, — и выход группы выходов первого дешифратора соединен с первыми входами блока элементов И моделей ребра i — и строки квадратной матрицы, j — и выход группы выходов второго дешифратора соединен с вторыми входами блоков элемен" тов И моделей ребра j — го столбца квадратной матрицы, третьи входы блоков элементов И моделей ребер квадратной матрицы соединены с выходом третьего элемента ИЛИ устройства, группа входов которого соединена с соответствующими выходами блоков элементов И моделей ребер наддиагональной матрицы, выходы вторых элементов

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

9 14I 0050 to третьими входами третьих элементов ми входами блоков элементов И модеИ моделей ребер соответствуняцих строк леи P«eP i — и строки наддиагональной наддиагональной матрицы, выход гене- матрицы, j — и выход первого распрератора импульсов .соединен с входом -; делителя им11ульсов соединен с третьипервого распределителя импульсов и с ми входами пеРвых элементов И и тре5 первым входом элемента И устройства, тьими входами блоков элементов И выход которого соединен с входом вто- моделей Ребер — го столбца наддиарого счетчика устройства и с входом гональной матрицы, и †. и выход первовторого распределителя импульсов, i — O го РаспреДелителЯ импУльсов соединен и выход которого соединен с вторыми с втоРым входом элемента И устройст входами первых элементов И и с вторы- ва.

Фиг.2 1410050

Заказ 4352.

Тираж 704

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Составитель С.Кошелев

Редактор О.Спесивых Техред Л.Олийнык Корректор О.Кравцова