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

(19) (11 06 Г 15/20 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙОПИСАНИЕ ИЗОБРЕТЕ фф Ур/Фф гфс ЬСТВУ К АВТОРСКОМУ СЕИД(56) Авторское свидетельство СССР У 943738, кл. С 06 Р 15/20, 1980.Авторское свидетельство СССР В 1120341, кл. С 06 Р 15/20, 1983. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ НЕЧЕТКИХ ГРАФОВ(5) Изобретение относится к вычислительной технике, может быть использовано для исследования нечетких некратных графов и позволяет разбить множество вершин нечеткого графа на уровни по количеству смежных ребер, функция принадлежности которых не меньше заданного значения. С этой целью в матрице смежности графа заданы значения функций принадлежности всех ребер графа. В момент подачи сигнала начальной установки устройства, значения функций принадлежности сравниваются с заданным значением, в результате чего формируется новая матрица смежности, в которую входят только те ребра, функция принадлежности которых не меньше заданной. После пуска устройства подсчитывается количество смежных ребер для каждой вершины графа и во все вершины последовательно сравниваются по количеству смежных ребер с эталонами уровней: от высшего - все единицы в столбце матрицы смежности, до низшего - все ноли в столбце матрицы смежности. В слу- сф чае совпадения количества смежных ребер с эталоном номера соответствующих вершин записываются в регистры тех строк матрицы разбиений, которые С соответствуют уровню, заданному эталоном. 1 нл.1325503 50 Изобретение относится к вычислительной технике и может быть использовано для определения нечеткого порядкового отношения множества вершиннечеткого графа,Цель изобретения - расширение класса решаемых задач за счет разбиениямножества вершин нечеткого графа науровни о количеству смежных ребер с 10учетом значения их функций принадлежности.На чертеже представлена функциональная схема устройства.Устройство содержит генератор 1 15тактовых импульсов, дешифратор 2, дваэлемента 3 и 4 задержки, шесть элементов И 5-10, блок 11 элементов И,два элемента ИЛИ 12 и 13, блок 14 эле 1ментов ИЛИ, матрицу 15 узлов принадлежности, матрицу 16 регистров разбиений, два элемента НЕ 17 и 18, двараспределителя 19 и 20 импульсов, выполненные в виде кольцевых регистровсдвига, три регистра 21-23, группурегистров 24 сдвига, два счетчика 25и 26, группу счетчиков 27, два реверсивных счетчика 28 и 29, схему 30сравнения и два триггера 31 и 32.Каждый узел матрицы 15 принадлех- З 0ности содержит регистр 33 и схему 34сравнения,Матрица 16 регистров разбиений выполнена на регистрах 35, вход 36 является входом пуска устройства, входы З 537 и 38 являются входами начальной установки устройстваВ качестве распределителей импульсов могут быть использованы кольцевыерегистры сдвига. 40Устройство работает следующим образом.Под нечетким графом С понимаетсяграФ С = Ы,1,Я),где У - множество пар вершин графа;.1 - множество связывающих их дуг,с заданными Функциями принадлежности(11);рв 0,1 . Множество Я и ФункцииЯ), соответствующие его элементам, задаютсяматрицей 15 узлов принадлежности, т.е.матрицей смежности некратного графа,в узлах которой заданы функции принадлежности,иР),В исходном состоянии в регистре 22хранится число М, где М - максимальная размерность матрицы 15, а в регистре 23 - число М+1. Каждый регистр 24 соответствует одной строке матрицы смежности, а К-й разряд всех регистров 24 соответствует К-му столбцу матрицы 15.По сигналу, поступающему на вход 37, число М с регистра 22 переписывается в счетчик 28, а число М+1 с регистра 23 - в счетчик 29, низкий потенциал с выхода признака переполнения которого, пройдя через элемент НЕ 18 и элемент ИЛИ 13, открывает элемент И 7.На вход элемента 3 задержки по входу 38 подается импульс сброса, который сбрасывает регистры 24 сдвига, регистры 14 и счетчики 25-27 и устанавливает в ноль триггеры 32 и 31. Этим же сигналом заносится единица в младший разряд регистров 19 и 20,Задержанный элементом 3 задержки импульс сброса поступает на входы опроса схем 34 сравнения, при этом сравниваются элементы матрицы 15, хранящиеся в соответствующих регистрах 33 (значения функций принадлежности) с некоторым пороговым значением, хранящимся в регистре 21, Если значение содержимого регистра 33 больше или равно пороговому значению, в соответствующий разряд регистра 24 записывается единица, если меньше, записывается ноль. Устройство готово к работе.При подаче высокого потенциала на вход 36 устройства на выходе элемента И 5 появляются тактовые импульсы, так как он открыт высоким потенциалом с выхода элемента НЕ 17, который снимается лишь при переходе реверсивного счетчика 28 через ноль, т,е. после М-го тактового импульса.Тактовые импульсы проходят через элемент И 1 О, который открыт высоким потенциалом с инверсного выхода триггера 31, и поступают на входы сдвига регистров 24. Информация с выхода каждого регистра 24 подается на счетный вход соответствующего счетчика 27.После прихода М-го тактового импульса на вычитающий вход счетчика 28 он переходит в нулевое состояние,так как в исходном состоянии в него записано число М, соответствующее мак-, симальной размерности матрицы 15. На выходе переполнения реверсивного счетчика 28 появляется уровень логи 1325503ческой единицы, который устанавливаеттриггер 31 в единичное состояние ичерез элемент НЕ 17 запрещает дальнейшее прохождение тактовых импульсов через элемент И 2. За М тактов5информация в регистрах 24 переписывается полностью и соответствует исходной матрице смежности. При этом в соответствующих счетчиках 2 записаночисло единиц, содержащееся в соответствующей строке матрицы смежности.(М+1)-й импульс с генератора 1 тактовых импульсов проходит через элемент И 8, который откроет его высоким потенциалом с выхода признака переполнения реверсивного счетчика 28и, проходя через элемент ИЛИ 12, переписывает с регистра 22 на реверсивный счетчик 28 число М, соответствующее размеру исходной матрицы смежности. На выходе признака переполнения реверсивного счетчика 28 появля- .ется низкий потенциал, который закрывает элемент И 8 и, проходя через эле мент НЕ 7, разрешает прохождение тактовых импульсов через элемент И 5.Кроме того, (М+1)-й импульс устанавливает эталонное значение, соответствующее первому уровню вершин З 0(т.е. все единицы в строке), на счетчике 29, поступая на его вычитакщийвход, а так как в нем хранится число(М+1), то после этой операции оно становится. равным М. Это эталонное значение сравнивается поочередно с числами, находящимися в счетчиках 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 находится в единичном состоянии и разрешает прохождение (М+1)-го импульса через элемент И 9 на вход сдвига кольцевого сдвигового регистра 20 и на вход установки в ноль счетчика 26.Под действием этого импульса единица в регистре 20 перемещается на один разряд, и на следующем этапе работы информация записывается в следующую строку матрицы 16, что соответствует новому уровню. Тот же (М+1)-й импульс, задержанный во времени элементом 33 задержки на время,необходимое для перемещения единицы в регистре 20 и установки в ноль5 3 Л счетчика 26, установит в ноль триггер 32, и процесс работы устройства повторяется.После того как (М+1) - й импульс генератора 1 тактовых импульсов на очередном шаге работы устройства установит на реверсивном счетчике 29 значение ноль, т,е, значение функции принадлежности низшего уровня вершин, на его выходе признака перепол кения появляется высокий потенциал, который, пройдя через элемент НЕ 8, поступает на элемент ИЛИ 13, на выходе которого появляется высокий потенциал, так как он открыт высоким потенциалом с выхода элемента НЕ 17. После того как содержимое счетчика 28 достигнет ноля, на его выходе признака переполнения появляется высокий потенциал, который, проходя че рез элемент НЕ 17 и элемент ИЛИ 13, закрывает элемент И 7 и тем самым запрещает прохождение тактовых импульсов с генератора 1. Работа устройства завершена, 25Формула изобретенияУстройство для исследования нечетких графов, содержащее генератор так товых импульсов, шесть элементов И, группу регистров сдвига, группу счетчиков, элемент задержки, дешифратор, три реверсивных счетчика, два элемента ИЛИ, два элемента НЕ, два счетчика и матрицу узлов принадлежности, причем выход генератора тактовых импульсов подключен к первому входу первого элемента И, о т л и ч а ю щ ее с я тем, что, с целью расширения щ класса решаемых задач за счет разбиения множества вершин нечеткого графа на уровни по количеству смежных ребер с учетом значения их функций принадлежности, в него введены два распределителя импульсов, три регистра, группа блоков элементов И, блок элементов ИЛИ,схема сравнения, два триггера и матрица регистров разбиений, а каждый узел матрицы принадлежности содержит схему сравнения и регистр, информационный выход которого подключен к первому информационному входу схемы сравнения того же узла матрицы принадлежности выход первого элемен та И подключен к первому входу второго элемента И, и первому входу третьего элемента И, второй вход которого является входом пуска устройства,036выход третьего элемента И подключен к первым входам четвертого и пятого элементов И и вычитающему входу первого реверсивного счетчика, выхоц признака переполнения которого подключен к информационному входу первого триггера, входу первого элемента НЕ и второму входу второго элемента И, выход которого подключен к вычитающему входу второго реверсивного счетчика, первому входу шестого элемента И, входу элемента задержки и первому входу первого элемента ИЛИ, выход которого подключен к входу записи первого реверсивного счетчика и входу чтения первого регистра, выхоц которого подключен к информационному входу первого реверсивного счетчика, прямой выход первого триггера подключен к второму входу четвертого элемента И, выход которого подключен к тактовому входу первого распределителя импульсов и счетному входу первого счетчика, информационный выход которого подключен к информационным входам регистров матрицы разбиений, К-й выход К=1М, где М - максимальное число вершин графа) первого распределителя импульсов подключен к первому входу К-го блока элементов И группы, выход которого подключен к соответствующему входу блока элементов ИЛИ, выход которого подключен к первому входу схемы сравнения, выход второго регистра подключен к информационному входу второго реверсивного счетчика, информационный выход которого подключен к второму входу схемы сравнения, выход признака равенства которой подключен к счетному входу второго счетчика, входам разрешения записи регистров матрицы разбиений и информационному входу второго триггера, выход элемента задержки подключен к входу установки в 0" второго триггера, выход которого подключен к второму входу шестого элемента И, выход которого подключен к входу установки в "0" второго счетчика и тактовому входу второго распределителя импульсов, К-й выход которого подключен к тактовым входам всех регистров К-й строки матрицы разбиений, информационный выход второго счетчика подключен к входу дешифратора, К-й выход которого подключен к входам записи всех регистров К-го столбца матрицы разбиений, инверсный выход первого триггера подключен к1325503 Составитель А.Мишиактор Н.Рогулич Техред И.Попович ректор Л Пилипенко аз 3112/46ВНИИПИ Госпо делам113035, Мо Подписное СССР й Тираждарствизо комите и откры бретени Ж,ашуская наб., д Производственно-попиграфическое предприятие,г.ужгор.Проектная,второму входу пятого элемента И, выход которого подключен к входу сдвига всех регистров сдвига группы, выход третьего регистра подключен квторым информационным входам схемсравнения всех узлов матрицы принадлежности, первый вход начальной установки устройства подключен к входам опроса схем сравнения всех узловматрицы принадлежности, выход признака неотрицательного результата схемы сравнения узла Р-й строки К-го столбца матрицы принадлежности подключен к входу установки в "1" Р-го разряда К-го регистра сдвига группы, последовательный информационный выход которого подключен к своему последовательному информационному входу и счетному входу К-го счетчика группы, информационный выход которого подключен к второму входу К-го блока элементов Игруппы,второй входпервого элемента ИЛИ группы является вторым вхо. дом начальной установки устройства.