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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 0 137609 06 Р 15/ 7Скорик, А.Ю.Пеи А,А.Прилуцкий тельство ССС Р 15/20, 198 ОДЕЛИРОВАН к вычисТь испол етение относится технике, может б исследования се оляет определять транзитивное и ое замыкание для Целью изобретен евых гравершины,блатноевсех веря являетГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРГ 10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТ(54) УСТРОЙСТВО ДЛЯ ГРАФОВ,зовано дляфов и позвобразующиетранзитивншин графа. ся расширение функциональных возможностей устройства за счет обеспечения возможности разбиения графа насильно связные подграфы. Устройствосодержит матричную модель 1 графа,триггеры 2, элементы И 4 и 3, двегруппы элементов ИЛИ 5 и 6, две группы 7 и 8 триггеров, дешифратор 9счетчик 10, элементы 11 задержки,элемент И 12, генератор 13 тактовых импульсов, вход 14 пуска,. две группы информационных выходов 15 и 16, выход 17признака окончания работы, группу элементов И 18 и группу регистров 19. Группа элементов И 18 введена для определения вершин, образующих одновременнотранзитивное и обратное транзитивноезамыкания для заданной вершины, чторавносильно определению вершин, вхо1376098 51 О15 20 25 30 40 дящих в состав сильно связного под, графа. Информация о составе сильносвяэньм подграфов, полученных в реИзобретение относится к вычислительной технике, может быть использовано для исследования сетевых графов и позволяет определять вершины, образующие транзитивное и обратное транзитивное замыкание для всех вершин графа и является усовершенствованием устройства по авт. св, У 1075268,Цель изобретения - расширение функциональных возможностей устройства за счет обеспечения возможности разбиения графа на сильно связные подграфы.На чертеже представлена функциональная схема устройства.Устройство содержит матричную модель 1 графа, триггеры 2, элементы И 3 и 4, две группы элементов ИЛИ 5 и 6, две группы 7 и 8 триггеров, дешифратор 9, счетчик 10, элемент 11 задержки, элемент И 12, генератор 13 тактовых импульсов, вход 14 пуска, две группы информационных выходов 15 и 16, выход 17 признака окончания работы, группу элементов И 18 и группу регистров 19 сдвига.Устройство работает следующим образом.Первоначально в нулевое состояние устанавливаются все триггеры 7,8 и счетчик 10. Информация о топологии моделируемого графа заносится путем установки соответствующих триггеров 2 в единичное состояние согласно матрицы смежности графаПосле подачи управляющего сигнала на выход 14 импульсы с генератора 13 начинают поступать через элемент . И 12 на вход счетчика 10,и вход элемента 11 задержки, одновременно происходит сдвиг в сторону младших разрядов содержимого регистров 19. С выхода счетчика 10 код номера импульса поступает на вход дешифратора 9; в результате чего последовательно возбуждаются его выходы, и единичный сигнал через элементы ИЛИ 5 и 6 перезультате разбиения исходного графа,запоминается на регистрах 19 сдвига.1 ил. водит в единичное состояние соответствующие триггеры 7,8.Единичный сигнал с выхода К-го триггера 7 (К=1 Р) проходит через открытые элементы 3 И М-ной строки матричной модели (М=1 Р) и устанавливает в единичное состояние соответствующие триггеры 7,Так определяются все вершины, образующие транэитивное замыкание для М-й вершины, Таким вершинам соответствует единичное состояние триггеров 7, При этом единица на К-ом выходе 15 соответствует номеру вершины,входящей в транзитивное замыкание для М-ой вершины моделируемого графа. Одновременно единичный сигнал с выхода М-го триггера 8 проходит через открытые элементы И 4 М-го столбца матричной модели 1 и устанавливает в единичное состояние соответствующий триггер 8, Так определяются все вершины, образующие транзитивноезамыкание для М-й вершины. Таким вершинам соответствует единица наК-м выходе 16 устройства.Одноименные триггеры 7 и 8, одновременно находящиеся в единичном состоянии, свидетельствуют о том,что соответствующие им вершины моделируемого графа являются достижимыми из заданной дешифратором 9 вершины и в то же время из этих вершиндостигается заданная вершина, а сле 35 довательно, соответствующие вершины принадлежат сильно связному подграфу, из вершин которого является заданная вершина.Определение вершин, входящих в сильно связный подграф осуществляется путем отыскания с помощью элементов И 18 триггеров одноименных 7 и 8, одновременно находящихся в единичном состоянии, При нахождении такой пары производится запись единицы в соответствующий разряд регистра 19 сдвига.1376098 Составитель А.ИипщнТехред А. Кравчук Корректор С. Черни Редактор С.Патрушева Заказ 789/48 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5етеае а ЮаПроизводственно-полиграфическое предприятие, г.Ужгород, ул.Проектная,4 3После завершения определения транзитивного и обратного транзитивного замыканий единичный сигнал с выхода элемента 11 задержки устанавливает все триггеры 7 и 8 в нулевое состояние. При поступлении на вход счетчика 10 очередного импульса транзитивное, обратное транзитивное замыкания и сильносвязный подграф определяются для второй вершины моделируемого графа и так далее до тех пор, пока на счетчик не достигнет числа Р, после чего с приходом очередного импульса происходит переполнение счетчика 10 и на выходе 17 устройства появляется единичный сигнал признака окончания работы.В этот момент времени в первых разрядах регистров 19 будет зафиксирован состав максимального сильно- связного подграфа, включающего первую вершину, во вторых разрядах подграф со второй вершиной и т,д.,Ф о р м у л .а и э о б р е т е н и я 5 Устройство для моделирования графов по авт. св. У 1075268, о т л ич а ю щ е е с я тем, что, с цельюрасширения функциональных возможностей устройства за счет обеспечения 10 возможности разбиения графа на сильно связные подграфы, в неЬо введеныгруппа из Р элементов И, где Р - количество вершин в графе и группа изР регистров сдвига, причем выход 15 К-го триггера первой группы (К=1,Р) подключен к первому входу К-гоэлемента И группы, выход К-го триггера второй группы подключен к второмувходу К-го элемента И группы, выход 20 которого подключен к информационномувходу К-го регистра сдвига группы,выход элемента И подключен к входампризнака сдвига всех регистров сдвига группы.