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

(С - г (С КЕХ,К) = к К) - число св- 1, , М, КЕХности К-й вер ины,где М - колич ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ К АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР В 716043, кл. С 06 Р 15/20, 1980.Авторское свидетельство СССР 9 1075268, кл. С 06 Е 15 /20, 1982. (54) УСТРОЙСТВО ДЛЯ МОДЕЛИРОВАНИЯ ГРАФОВ(57) Изобретение относится к вычислительной технике, может быть использовано для разбиения графа произвольной структуры на два максимально независимых подграфа и позволяет определятьчисла связности вершин двух подграфов. Устройство содержит матричнуюмодель 1 графа, триггеры 2, элементыИ 3 и 4, схемы 5 сравнения,.элементы НЕ 6, триггеры 7, арифметическиеустройства 8, вход 9 пуска. Устройство позволяет определить значениявеличин13 ство вершин в графе, г (С ) - количество ребер, соединяющих К-ю вершину с вершинами подграфа С, ( = 1,2); Х, - множество вершин -го подграфа. Перед началом работы в соответствующие триггеры 2 установкой в "1" заносится информация о топологии моделируемого графа, а в триггеры 7 - информация о вершинах, включаемых в первый подграф, Импульсный сигнал пуска, подаваемый на вход 9 устройства, обнуляет арифметические устрой 48849ства 8. Палее процесс.формирования чисел связности протекает параллельно и асинхронно. Если сигналы на обоих информационных входах схем 5 сравнения одинаковы, что соответствует принадлежности вершин К и Р к одному подграфу (Р = 1, , М), то сигналы с выхода элементов И 3 соответствующих узлов модели 1 поступают на вход Р-го вычитаемого К-го арифметического устройства, а в противном случае на вход его Р-го слагаемого. 1 ил, Изобретение относится к вычислительной технике и может быть исполь. -зовано при исследовании параметровграфов произвольной структуры дляопределения чисел связности вершинмоделируемого графа,Целью изобретения является .расширение класса задач, решаемых устройством эа счет определения чисел свяэ 10ности вершин двух подграфов.На чертеже изображена функциональная схема устройства.Устройство содержит матричную модель 1 графа, триггеры 2, элементы И153 и 4, схемы 5 сравнения, элементы НЕ6, триггеры 7, арифметические устройства 8, вход 9 пуска устройства.Устройство работает следующим образом,20При решении ряда практических задач, в частности, при нахождении разбиения графа произвольной структурына два максимально независимых подграфа, требуется определять для всехвершин графа значения величиныг(С,) - г(С,), КХИК) =гк(С) - г, (С, ), К Е Хгде 1. - число связности К-й вершины,(К = 1, , М, где М - коли 30чество вершин в графе),г (С ) - количество ребер, соединяюК 1щих К-ю вершину с вершинамиподграфа С ( = 1, 2);Х - множество вершин д-го под1графа (эта величина называется числом связности К-й вершины),В исходном состоянии в триггеры 2 матричной модели 1 графа заносится информация о топологии графа путем установки соответствующих триггеров 2 в единичное состояние, В единичное состояние устанавливаются триггеры 2 только тех узлов матричной модели 1, которым соответствует наличие в графе дуги. Триггеры 7, соответствующие вершинам, включаемым в первый подграф, устанавливаются в единичное состояние. Пуск устройства осуществляется путем подачи импульсного сигнала на вход 9. Этот сигнал устанавливает в нулевое состояние все арифметические устройства 8.Формирование значения числа связности для произвольной К-й вершины происходит путем параллельной передачи из узлов К-й строки матричной модели на К-й сумматор признаков наличия связей.этой вершины с другими вершинами с учетом знака, отражающего принадлежность К-й и связанной с ней вершин к одному и тому же подграфу. В этом случае К,Р-й узел (Р = 1, М) производит сравнение сигналов на входах схемы 5. Если сигналы одинаковы, что соответствует случаю принадлежности вершин К и Р к одному подграфу, то сигнал с выхода триггера 2 проходит через элемент И 3 на Р-й вычитающий вход К-го арифметического устройства. Если же сигналы на входах схемы 5 не совпадают, что соответствует случаю принадлежности вершин К и Р к разным подграфам, элемент НЕ 6 обеспечивает прохождениеСоставитель А,МишинТехред А.Кравчук Корректор В.Бутяга Редактор Е,Копча Заказ 4803/49 Тираж 670 ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д. 4/5Подписное Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 3 134 сигнала с выхода триггера 2 через элемент И 4 и на Р-й суммирующий вход К-го арифметического устройства 8. В результате объединения всех входных сигналов на К-м арифметическом устройстве 8 будет сформировано значение числа связности для К-й вершины. Формирование значений чисел связности для всех вершин графа происходит параллельно и практически мгновенно. Формула изобретенияУстройство для моделирования графов, содержащее М триггеров, где М - количество вершин в графе, и матричную модель графа, каждый узел которой содержит два элемента И, триггер, выход которого подключен к первым входам первого и второго элементов И того же узла матричной модели графа, о т л и ч а ю щ е е с я тем, что, с целью расширения класса решаемых задач эа счет определения чисел связности вершин двух подграфов, в него введены М арифметических устройств, а в каждый узел матричной модели гра. фа введена схема сравнения и элемент 1 88494НЕ, причем выход К-го триггера (К =1, , М) подключен к первым информационным входам схем сравнениявсех узлов К-й строки матричной модели графа и к вторым информационнымвходам схем сравнения всех узлов К-гостолбца матричной модели графа, выходпризнака равенства схемы сравненияР-го узла (Р = 1.М) К-й строкиматричной модели графа подключен квторому входу элемента И того же узламатричной модели графа и к входу элемента НЕ того же узла матричной модели графа, выход элемента НЕ Р-го узлаК-й строки матричной модели графаподключен к второму входу второго элемента И того же узла матричной моделиграфа, выход первого элемента И Р-гоузла К-й строки матричной модели графа подключен к входу Р-го вычитаемогоК-го арифметического устройства, выход второго элемента И Р-го узла К-йстроки матричной модели графа подклю В чен к входу Р-го слагаемого К-го арифметического устройства, вход пускаустройства подключен к входам установки в "0" всех арифметических устройств.