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

СОЮЗ СОВЕТСКИСОЦИАЛИСТИЧЕСНРЕСПУБЛИН 14100 1)4 С 06 Г 15 20 фе .,с ТЕТ ССС И ОТКРЫТ ГОСУДАРСТВЕННЫЙ Н ПО ДЕЛАМ ИЗОБРЕТЕН 21)(54) ГРАФ (57) вычи СТРОИСТВО ОДЕЛИРОВА 26,Лебедев испо овано приуктур, отообретения соскциональных втва за счет п ировании сет мод бра выхЦель жаемых графами, тоит в расшире озможностейроизвольнои ну тельство ССС Р 15/20,.198 льство СССР 7/122, 197 нии Фун устройс мерации,В 7 7. узлов граФа троиство ПИСАНИЕ ИЭОБРЕТВТОРСНОМ,К СВИДЕТЕЛЬСТВУ 111813/24-24 2,08.86 5.07.88. Бюл, .Д.Бобраков, Данилов 81.333 (088.8Авторское свид 930, кл, С 06 орское свидет 98, кл. С 061410050 содержит модель исходного графя, выполненную в виде няддиагональнойматрицы 1 моделей 2 ребер, первую 3и вторую 4 группы моделей 5 узлов,модель искомого графа, выполненнуюв виде матрицы 6 из моделей 7 ребер,состоящих каждая из блока Я элементов И, элемента ИЛИ 9 и регистра 10для наддиагональных элементов матрицы 6 и блока Я элементов И - дляподдиагональных элементов матрицы6, первый счетчик 11, первый 12,Изобретение относится к областивычислительной техники и может быть использогно при моделировании сетевых структур, отображаемых графами,для решения задачи переадресации узлов сети.Цель изобретения состоит в расширении функциональных воэможностейустройства за счет произвольной 10нумерации узлов графа,Ня Фиг, 1 представлен пример функциональной схемы устройства; на фиг.2 -модель ребра; на фиг, 3 - модель узла,Устройство содержит (фиг, 1) 15модель исходного графа, выполненнуюв виде няддиягоняльной матрицы 1 из1 х) (1 = 1, п, 1 = 2,п, п - числоузлов графа) моделей 2 ребер, первую3 и вторую 4 группы из пмоделей 20узлов, модель искомого графа, выполненную в виде квадратной матрицы 6из пхп,моделей 7 ребер, состоящихкаждая из блока 8 элементов И, элемента ИЛИ 9 и регистра 10 для наддиагональных элементов и из блока 8элементов И для поддиагональных элементов матрицы 6, первый счетчик 11,первый 12, второй 13, третий 14 ичетвертый 15 элементы ИЛИ, первый 16 30и второй 17 распределители импульсов,генератор 18 импульсов, элемент И 19,первый 20 и второй 21 дешифраторы,второй счетчик 22,Модель 2 (фиг. 2) содержит триггер 3523, элемент И-НЕ 24, коммутатор 25,блок 26 элементов И, первый 27, второй 28 и третий 29 элементы И, первый30 и второй 31 элементы задержки, регистр 32, входные и выходные полюса33-43. второй 13, третий 14 и четвертьй 15элементы ИЛИ, первыи 16 и второй 17распределители импульсов, генератор18 импульсов, элемент И 19, первый20 и второй 21 дешифряторы, второйсчетчик 22, Расширение Функциональных возможностей достигнуто за счетприсвоения узлам исходного графановых условных номеров с одновременным формированием матрицы смежностиискомого граФа, 3 ил. 2Модель 5 (Фиг. 3) содержит первый 44 и второй 45 элементы ИЛИ, элемент И 46, регистр 47, элемент 48 задержки, триггер 49, входные и выходные полюса 50-55.В исходном статическом состоянии счетчик 11, дешифряторы 20, 21 регистры 10, триггеры 49 и регистры 47 обнулены, триггеры 23 в моделях 2, соответствующих ребрам исходного графа, устанавливаются в единичное состояние, а и регистры 32 заносятся веса ребер, в счетчик 22 заносится число, дополняющее число пдо полной емкости счетчика. Исходное состояние распределителя 17 - произвольное, исходное состояние распределителя 16 устанавливают таким, чтобы он выдавал единичный потенциал на выход с номером, соответствующий которому узел исходного графа выбирается в качестве первого узла искомого графа. Работу устройства рассмотрим на примере преобразования исходного графа с матрицей смежности А в искомый граф с матрицей смежности А, причем исходное положение распределителя 16 - выдача потенциала "1" по четвертому выходу, т.е за начальный узел в искомом графе выбран четвертый узел исходного графа, а исходное положение распределителя 17 - выдача "1" по третьему выходу. Цифрами в матрицах обозначены веса ребер.Устройство работает следующимобразом.1После занесения исходной информации единичнымы потенциалами с выходов 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 и вход записи регистра 471, который запоминает число 1. Нулевой потенциал с инверсного выхода триггера 49 закрываетэлемент И 46, исключая запись новойинформации в регистр 47, а также за-,30крывает элементы И 29 в моделях 2четвертого столбца матрицы 1. Потенциал "1" с прямого выхода триггера49 поступает через полюса 34 моделей 2 четвертого столбца матрицы 1 З 51на первые входы элементов И-НЕ 24, ачерез полюс 50 он проходит в модель5 , где через элемент ИЛИ 45 поступает на вход записи регистра 47, ко 40торый запоминает 1, и на единичныйвход триггера 49, который переходитв состояние "1". Потенциал "0" с инверсного выхода этого триггера закрывает элемент И 46, а через полюса 37моделей 2 четвертой строки матрицы451 поступает на третьи входы элементов И 29, закрывая их. Потенциал "1"с прямого выхода указанного триггерачерез полюса 35 моделей 2 четвертойстроки матрицы 1 поступает на вторыевходы элементов И-НЕ 24,С выхода элемента задержки 30 модели 2 э сигнал проходит через элементИЛИ 13 на счетный вход счетчика 11,содержимое которого становится равным2 и выставляется на информационныевходы регистров 47. С выхода элемента задержки 31 потенциал "1" поступает на управляющий вход коммутатора25, который подключает свой вход ковторому выходу, и потенциал " 1" с выхода элемента И 27 через полюс 55 поступает в модель 5, где проходитчерез элементы ИЛИ 44, И 46, ИЛИ 45на вход записи регистра 47, которыйзапоминает число 2, и на единичныйвход триггера 49, который переходитв состояние " 1". Потенциал "0" с егоинверсного выхода закрывает элементИ 46, а через полюса 37 моделей 2третьей строки матрицы 1 поступаетна третьи входы элементов И 29.Потенциал "1" с прямого выхода этого триггера через полюса 35 моделей 2 третьей строки матрицы 1 подается на вторые входы элементов И-НЕ 24, а черезполюс 50 модели 5 и элемент ИЛИ 45поступает на вход записи регистра 47,который запоминает число 2, и на единичный вход триггера 49. который сигУналами "со своего прямого и инверсноговыходов производит те же действия,что и триггер 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,з 1 поэтому единичный сигнал с выхода элемента И 27 проходит только на вход элемента задержки 31 и на первый выход коммута тора 25, откуда поступает на полюс 55 модели 5, , где через элемент ИЛИ 44 проходит на вход элемента задержки 48, а через элементы И 46, ИЛИ 45 - на вход записи регистра 47, который запоминает число 3, и на единичный вход триггера 49, который переходит в единичное состояние, Потенциал "0" с инверсного выхода триг гера 49, закрывает элемент И 46 а через полюса 36 моделей 2 пятого столбца матрицы 1 поступает на вторые входы элементов И 29 и закрывает их, Потенциал " 1" с прямого выхода триггера 49, через полюс 50 модели 5.1- и далее через элемент ИЛИ 45 проходит на вход записи регистра 47 1, который запоминает число 3, и на единичный вход триггера 49, который переходит в состоя 11 1ние 1 и сигналами с прямого и инверсного выходов производит такие же действия, как и триггер 49. Единичный сигнал с прямого выхода триггера 49 через полюса 34 моделей 2 пятого столбца матрицы 1 поступает на первые входы элементов И-НЕ 24 . При выдаче элементом 31 задержки сигнала на управляющий вход коммутатора 25 он под-,1 35 ключает свои вход ко второму выходу, Тогда в модели 2 единичный сигнал с выхода элемента И 27 поступает через второй выход коммутатора 25 на полюс 55 модели 5, где проходит через элемент ИЛИ 44 на вход элемента 48 задержки, в то время, как элемент И 46 закрыт. По истечении времени задержки элементы 48 , 48 задержки вьдают импульсы на входы считыва ния регистров 47 , 47 э, с выходов которых числа 3 й 2 через элементы ИЛИ 14, 15 поступают на входы дешйфраторов 20, 21, Они вьдают единичные сигналы соответственно по третьему и второму выходам, открывая блок 89 для прохождения выставленного на его первом входе числа 7 через элемент ИЛИ 9 модели 7 В регистр 10 з.Следующий импульс генератора 18 проходит, во-первых, на вход распределителя 16, во-вторых, через открытый элемент И 19 на вход распределителя 17. Распределитель 16 выдает едиО 6ничный сигнал по второму выходу (выходы распределителя пронумерованы с второго по п-й), а распределитель 17 - по первому выходу, При :этом в модели 211 открывается элемент И 27 и и далее происходят аналогичные процессы, в результате которых в регистрах 47 моделей 511 , 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 увеличивается на 1 и при его переполнении на соответствующий выход устройства вьдается сигнал окончания его работы. При этом в регистрах 47 записаны номера узлов искомого графа, а в регистрах 10 - веса его ребер (в наддиагональных элементах), Квадратная матрица 6 представля- ет собой матрицу смежности искомого графа.Формула изобретенияУстройство для моделирования граФов, содержащее наддиагональную матрицу ( = 1, п,=: 2,п, ив число узлов моделей ребер) моделей ребер, генератор импульсов, первый и второй счетчики, элемент И, каждая модель ребра содержит триггер, первьй 1 второй и третий элементы И, причем прямой выход триггера соединен с первым входом первого элемента И, выход которого подключен к первому входу второго элемента И, о т л и ч а ю - щ е е с я тем, что, с целью расширения функциональных возможностей устройства за счет произвольной нумерации узлов графа, в него введены141005 первый, второй, третий и четвертый элементы ИЛИ, первый и второй распределители импульсов, первый и второй дешифраторы, первая и вторая группы из имоделей узло квадратная пхд матрица моделей ребер, поддиагональная модель ребра которой содержит блок элементов И, а наддиагональная модель ребра квадратной матрицы моделей ребер содержит блок элементов И, элемент. ИЛИ и регистр, каждая модель узла содержит первый элемент ИЛИ, элемент И, второй элемент ИЛИ, триггер, элемент задержки и регистр, в каждую модель ребра наддиагональной матрицы введены блок элементов И, элемент И-НЕ, коммутатор, первый ивторой элементы задержки и регистр, выход которого соединен с первым вхопом блока элементов И, выход первого элемента И модели ребра наддиагональной матрицы подключен к информационному входу коммутатора, к входу первого элемента задержки и к первому 2 б входу третьего элемента И, выход кото.1 ого соединен с входом второго элемента задержки, выход первого элемента задержки подключен к управляющему входу коммутатора модели ребра наддиагональной матрицы, выход первого элемента ИЛИ модели узла соединен с первым входом элемента И и входом элемента задержки, выход которого соединен с входом разрешения считывания35 регистра модели узла, выход элемента И модели узла соединен с первым входом второго элемента ИЛИ, выход которого соединен с входом разрешения записи регистра и с входом установки в "1" триггера, инверсный выход кото- . рого соединен с вторым входом элемента И модели узла, выход блока элементрв И наддиагональной модели ребра квадратной матрицы соединен с первым 4 входом элемента ИЛИ, выход которого соединен с входом регистра наддиагональной модели ребра квадратной матрицы, выходы блоков элементов И поддиагональных моделей ребра 1 - го столб- О ца квадратной матрицы соединены с вторыми входами элементов ИЛИ наддиагональных моделей ребер- й строки квадратной матрицы, первые выходы коммутаторов моделей ребер 1 - го столб Ьб ца наддиагональной матрицы подключены к группе входов первого элемента ИЛИ- й модели узла первой группы ( - 2п) вторые выходы коммутаторов моделей ребер д в ,й строки надциагональной матрицы подключены к группе входов первого элемента ИЛИ- й модели узла второй группы ( = 1 и) выходы регистров моделей узлов первой группы соединены с группой входов первого элемента ИЛИ устройства, выходы регистров моделей узлов второй группы соединены с группой входов второго элемента ИЛИ устройства, выход первого элемента ИЛИ устройства соединен с входом первого дешифратора устройства, выход второго элемента ИЛИ соединен с входом второго дешифратора устройства,- й выход группы выходов первого дешифратора соединен с первыми входами блока элементов И моделей ребра х - й строки квадратной матрицы,- й выход группы выходов второго дешифратора соединен с вторыми входами блоков элемен" тов И моделей ребра- го столбца квадратной матрицы, третьи входы блоков элементов И моделей ребер квадратной матрицы соединены с выходомтретьего элемента ИЛИ устройства, группа входов которого соединена с соответствующими выходами блоков элементов И моделей ребер наддиагональной матрицы, выходы вторых элементов И и вторых элементов задержки моделей ребер наддиагональной матрицы соединены с соответствующими входами четвертого элемента ИЛИ, выход которого соединен со, счетным входом первого счетчика, выход которого соединен с информационными входами регистров моделей узлов первой и второй групп, прямые выходы триггеров моделей узлов первой группы соединены с первыми входами элементов И-НЕ моделей ребер соответствующих столбцов наддиагональной матрицы и с вторым входом второго элемента ИЛИ соответствующих моделей узла второй группы, прямые выходы триггеров моделей узлов второй группы соединены с вторыми входами элементов И-НЕ моделей ребра соответствующих строк наддиагональной матрицы и с вторым входом второго элемента ИЛИ соответствуюцей модели узла первой группы, инверсные выходы триггеров моделей узлов первой группы соединены с вторыми входами третьих элементов И моделей ребер соответствующих столбцов наддиагональной матрицы, инверсные выходы триггеров моделей узлов второй группы соединены с9 1410050 0третьими входами третьих элементов ми входами блоков элементов И моде- И моделей ребер соответствуницих строк лей РебеР 1 - й строки наддиагональной наддиагональной матрицы, выход гене- матрицы - й выход первого распрератора импульсов .соединен с входом; делителя им 11 ульсов соединен с третьи- первого распределителя импульсов и с ми входами первых элементов И и тре 5первым входом элемента И устройства, тьими входами блоков элементов И выход которого соединен с входом вто- моделей ребер- го столбца наддиарого счетчика устройства и с входом гональной матрицы, и в . й выход перво- второго распределителя импульсов, 1 - 1 О го распределителя импульсов соединен й выход которого соединен с вторыми с вторым входом элемента И устройствходами первых элементов И и с вторы- ва.1410050 Составитель С.КошелевРедактор О.Спесивых Техред Л, Олийнык Корректор О, Кравцова Заказ 4352ПодписноеТираж 704 ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4/5Производственно-полиграфическое предприятие, г, Ужгород, ул, Проектная, 4