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

 

Изобретение относится к вычислительной технике, может быть использовано для исследования нечетких некратных графов и позволяет разбить множество вершин нечеткого графа на уровни по количеству смежных ребер, функция принадлежности которых не меньше заданного значения. С этой целью в матрице смежности графа заданы значения функций принадлежности всех ребер графа. В момент подачи сигнала начальной установки устройства , значения функций принадлежности сравниваются с заданным значением, в результате чего формируется новая матрица смежности, в которую входят только те ребра, функция принадлежности которых не меньше заданной. После пуска устройства подсчитьшается количество смежньк ребер дпя каждой вершины графа и во все вершины последовательно сравниваются по количеству смежных ребер с эталонами уровней: от высшего - все единицы в столбце матрицы смежности, до низшего - все ноли в столбце матрицы смежности. Белуа чае совпадения количества смежных ребер с эталоном номера соответствую- mjrx вершин записьшаются в регистры тех строю матрицы разбиений, которые соответствуют уровню, заданному эталоном ... 1 ил. S (Л со ю ел СП

CCNO3 СОВЕТСНИХ

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

РЕСПУБЛИК,.SU„„1325503

А1 (5g 4 С 06 F 15/20

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (Я р °, 3

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

t (21) 4041970/24-.24 (22) 24.03.86 (46) 23.07.87. Бюл. ¹ 27 (72) Б.M.Ãåðàñèìoâ, С.Ч.Колесник, С.Ю.Переваров и И.А.Ветров (53) 681.333(088 ° 8) (56) Авторское свидетельство СССР № 943738, кл. G 06 F 15 20, 1980.

Авторское свидетельство СССР № 1120341, кл. G 06 F 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ НЕЧЕТКИХ ГРАФОВ (5?) Изобретение относится к вычислительной технике, может быть использовано для исследования нечетких не-: кратных графов и позволяет разбить множество вершин нечеткого графа на уровни по количеству смежных ребер, функция принадлежности которых не меньше заданного значения. С этой целью в матрице смежности графа заданы значения функций принадлежности всех ребер графа. В момент подачи сигнала начальной установки устройства, значения функций принадлежности сравниваются с заданным значением, в результате чего формируется новая матрица смежности, в которую входят только те ребра, функция принадлежности которых не меньше заданной. После пуска устройства подсчитывается количество смежных ребер для каждой вершины графа и во все вершины последовательно сравниваются по количеству смежных ребер с эталонами уровней: от высшего — все единицы в столбце матрицы смежности, до низшего — все ноли в столбце матрицы смежности. В случае совпадения количества смежных ребер с эталоном номера соответствующих вершин записываются в регистры тех строк матрицы разбиений, которые соответствуют уровню, заданному эта лоном., 1 нл.

1325503

С = (W, 1.,(W}1,, где У вЂ” множество пар вершин графа; .1 — множество связывающих их дуг, с заданными функциями принад— лежности р, (W); рв(0,1) .

Множество W и функции y<(M), соответствующие его элементам, задаются матрицей 15 узлов принадлежности, т.е. матрицей смежности некратного графа, в узлах которой заданы функции принадлежности,и (W).

В исходном состоянии в регистре 22 хранится число М, где М вЂ” максималь45

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

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

На чертеже представлена функциональная схема устройства.

Устройство содержит генератор 1 15 тактовых импульсов, дешифратор 2, два элемента 3 и 4 задержки, шесть элементов И 5-10, блок 11 элементов И, два элемента ИЛИ 12 и 13, блок 14 эле—

1 ментов ИЛИ, матрицу 15 узлов принад- 20 лежности, матрицу 16 регистров разбиений, два элемента НЕ 17 и 18, два распределителя 19 и 20 импульсов, выполненные в виде кольцевых регистров сдвига, три регистра 21-23, группу регистров 24 сдвига, два счетчика 25 и 26, группу счетчиков 27, два реверсивных счетчика 28 и 29, схему 30 сравнения и два триггера 31 и 32.

Каждый узел матрицы 15 принадлежности содержит регистр 33 и схему 34 сравнения.

Матрица 16 регистров разбиений выполнена на регистрах 35, вход 36 является входом пуска устройства, входы З5

37 и 38 являются входами начальной установки устройства °

В качестве распределителей импульсов могут быть использованы кольцевые регистры сдвига. 40

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

Под нечетким графом G понимается граф ная размерность матрицы 15, а в регистре 23 — число М+1. Каждый регистр

24 соответствует одной строке матрицы смежности, а К-й разряд всех регистров 24 соответствует К-му столбцу матрицы 15.

По сигналу, поступающему на вход

37, число М с регистра 22 переписывается в счетчик 28, а число М+! с регистра 23 — в счетчик 29, низкий потенциал с выхода признака переполнения которого, пройдя через элемент

HE 18 и элемент ИЛИ 13, открывает элемент И 7.

На вход элемента 3 задержки по входу 38 подается импульс сброса, который сбрасывает регистры 24 сдвига, регистры 14 и счетчики 25-27 и устанавливает в ноль триггеры 32 и 31.

Этим же сигналом заносится единица в младший разряд регистров 19 и 20.

Задержанный элементом 3 задержки импульс сброса поступает на входы опроса схем 34 сравнения, при этом сравниваются элементы матрицы 15, хранящиеся в соответствующих регистрах

33 (значения функций принадлежности) с некоторым пороговым значением, хранящимся в регистре 21. Если значение содержимого регистра 33 больше или равно пороговому значению, в соответствующий разряд регистра 24 записывается единица, если меньше, записывается ноль. Устройство готово к ра— боте.

При подаче высокого потенциала на вход 36 устройства на выходе элемента И 5 появляются тактовые импульсы, так как он открыт высоким потенциалом с выхода элемента HE 17, который снимается лишь при переходе реверсивного счетчика 28 через ноль, т.е. после М-ro тактового импульса.

Тактовые импульсы проходят через элемент И 10 который открыт высоким потенциалом с инверсного выхода триггера 31, и поступают на входы сдвига регистров 24. Информация с выхода каждого регистра 24 подается на счетный вход соответствующего счетчика 27.

После прихода М-го тактового импульса на вычитающий вход счетчика 28 он переходит в нулевое состояние,так как в исходном состоянии в него записано число М, соответствующее мак-, симальной размерности матрицы 15. На выходе переполнения реверсивного счетчика 28 появляется уровень логи1325503 ческой единицы, который устанавливает триггер 31 в единичное состояние и через элемент НЕ 17 запрещает дальнейшее прохождение тактовых импульсов через элемент И 2. За М тактов

5 информация в регистрах 24 переписывается полностью и соответствует исходной матрице смежности. При этом в соответствующих счетчиках 2 записано число единиц, содержащееся в соответствующей строке матрицы смежности. (М+1)-й импульс с генератора 1 тактовых импульсов проходит через элемент И 8, который откроет его высоким потенциалом с выхода признака переполнения реверсивного счетчика 28 и, проходя через элемент ИЛИ 12, переписывает с регистра 22 на реверсивный счетчик 28 число М, соответствующее размеру исходной матрицы смежности. На выходе признака переполнения реверсивного счетчика 28 появля-ется низкий потенциал, который закрывает элемент И 8 и, проходя через эле-2 мент НЕ 7, разрешает прохождение тактовых импульсов через элемент И 5.

Кроме того, (М+1)-й импульс устанавливает эталонное значение, соответствующее первому уровню вершин (т.е. все единицы в строке), на счетчике 29, поступая на его вычитак!щий вход, а так как в нем хранится число (М+1), то после этой операции оно становится. равным M. Это эталонное значение сравнивается поочередно с числами, находящимися в счетчиках 2. Информация со всех счетчиков 2 через блок 14 элементов ИЛИ подается на схему 30 сравнения.

Запись информации в матрицу 16 происходит следующим образом.

За такт (М+1)-го импульса проходит сравнение с эталоном числа, находя- щегося в первом счетчике 27. Если сравнение произошло, схема 30 сравнения вырабатывает сигнал, который устанавливает триггер 32 в единичное состояние, записывает в первый ре-" гистр 38 строки, отведенндй под наивысший класс, содержимое счетчика 25, которое соответствует номеру первого счетчика 27. Этот же импульс увеличивает содержимое счетчика 26 позиций на единицу в случае, если при дальнейшей проверке найдены еще строки, входящие в данный уровень. Если же сравнения не произошло, все схемы остаются в первоначальном состоянии.

Следующий тактовый импульс через элемент И 5 поступает на вычитающий вход счетчика 28, проходит через элемент И 6, открытый высоким потенциалом с выхода триггера 31, и поступает на регистр 19 и счетчик 25 номера строк матрицы смежности . Под действием тактового импульса единица в регистре 19 сдвигается на один разряд, разрешая прохождение через блок 11 элементов И на схему 30 сравнения информации с второго счетчика 27, и увеличивает содержимое счетчика 25 на единицу, что соответствует второй строке.

Таким образом, по приходу тактовых импульсов содержимое всех счетчиков 27 поочередно подается на схему 30 сравнения и при совпадении с эталонным значением в соответствующий регистр 14 записывается номер строки матрицы смежности. При этом изменяется состояние регистра 19, счетчика 25 и счетчика 26 при условии, что сравнение является неоднократным.

После того как проверено содержимое всех счетчиков 27 по данному уровню, содержимое счетчика 28 становится равным нулю, íà его выходе признака переполнения появляется высокий потенциал, который, проходя через элемент НЕ 17, запрещает прохождение тактовых импульсов с выхода генератора 1 через элемент И 5. В исходном состоянии на регистре 20 единица находится в младшем разряде, (М+1)-й импульс, пройдя через элемент 8 И, установит в счетчик 28 чисчисло М, поступит на вычитающий вход счетчика 29 и установит число минус один. Если в предыдущем шаге были сравнения, триггер 20 находится в единичном состоянии и разрешает прохождение (M+1)-ro импульса через элемент И 9 на вход сдвига кольцевого сдвигового регистра 20 и на вход установки в ноль счетчика 26.

Под действием этого импульса единица в регистре 20 перемещается на один разряд, и на следующем этапе работы информация записывается в следующую строку матрицы 16, что соответствует новому уровню. Тот же (М+1)-й импульс, задержанный во вре-! ! мени элементом 33 задержки на время, ! необходимое для перемещения единицы в регистре 20 и установки в ноль

5 13255 счетчика 26, установит в ноль триггер 32, и процесс работы устройства повторяется.

После того как (М+1) — и импульс генератора 1 тактовых импульсов на очередном шаге работы устройства установит на реверсивном счетчике 29 значение ноль, т.е. значение функции принадлежности низшего уровня вершин, на его выходе признака перепол- 10 кения появляется высокий потенциал, который, пройдя через элемент НЕ 18, поступает на элемент ИЛИ 13, на выходе которого появляется высокий потенциал, так как он открыт высоким потенциалом с выхода элемента НЕ 17.

После того как содержимое счетчика

28 достигнет ноля, на его выходе признака переполнения появляется высокий потенциал, который, проходя че- 20 рез элемент НЕ 17 и элемент ИЛИ 13, закрывает элемент И 7 и тем самым запрещает прохождение тактовых импульсов с генератора 1. Работа устройства завершена. 25

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

Устройство для исследования нечетких графов, содержащее генератор так- 30 товых импульсов, шесть элементов И, группу регистров сдвига, группу счетчиков, элемент задержки, дешифратор, три реверсивных счетчика, два элемента ИЛИ, два элемента НЕ, два счетчика и матрицу узлов принадлежности, причем выход генератора тактовых импульсов подключен к первому входу первого элемента И, о т л и ч а ю щ е— е с я тем, что, с целью расширения !0 класса решаемых задач за счет разбиения множества вершин нечеткого графа на уровни по количеству смежных ребер с учетом значения их функций принадлежности, в него введены два распределителя импульсов, три регистра, группа блоков элементов И, блок элементов ИЛИ,схема сравнения, два триггера и матрица регистров разбиений, а каждый узел матрицы принадлежности содержит схему сравнения и регистр, информационный выход которого подключен к первому информационному входу схемы сравнения того же узла матрицы принадлежности„ выход первого элемен- <5 та И подключен к первому входу второго элемента И, и первому входу третьего элемента И, второй вход которого является входом пуска устройства, 03

6 выход третьего элемента И подключен к первым входам четвертого и пятого элементов И и вычитающему входу первого реверсивного счетчика, выхоц признака переполнения которого подключен к информационному входу первого триггера, входу первого элемента НЕ и второму входу второго элемента И, выход которого подключен к вычитающему входу второго реверсивного счетчика, первому входу шестого элемента И, входу элемента задержки и первому входу первого элемента ИЛИ, выход которого подключен к входу записи первого реверсивного счетчика и входу чтения первого регистра, выхоц которого подключен к информационному входу первого реверсивного счетчика, прямой выход первого триггера подключен к второму входу четвертого элемента И, выход которого подключен к тактовому входу первого распределителя импульсов и счетному входу первого счетчика, информационный выход которого подключен к информационным входам регистров матрицы разбиений, К-й выход (K-=1,...,М, где М вЂ” максимальное число вершин графа) первого распределителя импульсов подключен к первому входу К-го блока элементов И группы, выход которого подключен к соответствующему входу блока элементов ИЛИ, выход которого подключен к первому входу схемы сравнения, выход второго регистра подключен к информационному входу второго реверсивного счетчика, информационный выход которого подключен к второму входу схемы сравнения, выход признака равенства которой подключен к счетному входу второго счетчика, входам разрешения записи регистров матрицы разбиений и информационному входу второго триггера, выход элемента задержки подключен к входу установки в "0" второго триггера, выход которого подключен к второму входу шестого элемента И, выход которого подключен к входу установки в "0" второго счетчика и тактовому входу второго распределителя импульсов, К-й выход которого подключен к тактовым входам всех регистров К-й строки матрицы разбиений, информационный выход второго счетчика подключен к входу дешифратора, К-й выход которого подключен к входам записи всех регистров К-го столбца матрицы разбиений, инверсный выход первого триггера подключен к

1325503

Составитель А.Мишин

Редактор H.Ðoãóëè÷ Техред И.Попович Корректор Л.Пилипенко

Заказ 3112/46 Тираж 672 Подписное

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

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

Производственно-попиграфическое предприятие,г.ужгород,ул.Проектная,4 второму входу пятого элемента И, выход которого подключен к входу сдвига всех регистров сдвига группы, выход третьего регистра подключен к вторым информационным входам схем сравнения всех узлов матрицы принадлежности, первый вход начальной установки устройства подключен к входам опроса схем сравнения всех узлов матрицы принадлежности, выход признака неотрицательного результата схемы сравнения узла P-й строки К-го столбца матрицы принадлежности подключен к входу установки в "1" Р-го разряда К-ro регистра сдвига группы, последовательный информационный выход которого подключен к своему последовательному информационному входу и счетному входу К-ro счетчика группы, информационный выход которого подключен к второму входу К-го блока элементов Игруппы,второй входпервого элемента ИЛИ группы является вторым входом начальной установки устройства.