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

СООЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 19) 111 51)4 С 06 Р 15 2 СССРНРЫТИЙ РЕТЕИИ д 4;,ГОСУДАРСТВЕННЫЙ НОМИТ ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОПИСАНИЕ ИЗ(54) УСТРОЙСТВО ДЛЯ ИСП 1 ЕДОВЛНИЯПАРАИКТРОВ 1 РАФОВ(57) Изобретение относится к обЛастивычислигельной техники и может бытьиспользовано для определения связности графов, в том числе ориентированных графов, являшщихся математическими моделями сетей связи, нычислительных сетей, Цель изобретениярасширение Функшюнальных возможно -стей за счет оценки связности сильнои слабо связньгх ориентированных графов - достига,:тся тем, что в устройство, содержащее матрипь триггерови элементов И, группу элементов ИЛИи элемент И, дополнительно вгеденыматрица элементов ИЛИ, с второй почетвертуп группы элементов ИЛИ,груп-"па элементов И, первый и второй эле -менты задержки, с первого по третийэлементы ИЕ с второго по шестой элементы И. 2 ил.Изобретение относится к вычислительной технике и может быть использовано для определения связностиграфов, в том числе ориентированных графов, являющихся математическими моделями сетей связи, вычислительных сетей и т.д.Цель изобретения - расширениефункциональных возможностей устрой Оства за счет оценки связности сильно и слабо связных ориентированныхграфов.Функциональная схема устройствапоказана на Фиг. 1 и 2. 5Устройство содержит матрицы триггеров 1, матрицу элементов И 2, матрицу элементов ИЛИ 3, первую группу элементов ИЛИ 4, вторую группуэлементов ИЛИ 5, третью группу элементов ИЛИ 6, группу элементов И 7,ирвый элемент И 8, первый 9 и второй 10 элементы задержки, первый 11и второй 12,третий 13 элементы НЕ,второй 14, третий 15, четвертый 16пятый 17 элементы И, блок 18 индикации, четвертую группу элементов И 19,шестой элемент И 20, вход 21 начальной установки устройства, установочные входы 22 триггеровматрицы, 30вход 23 пуска устройства,Блок 7 содержит три индикатора,соответствующие трем входам: первыйсигнализует о сильной связности графа второй - о слабой связности графа, третий - граф не связен. Устройство работает следующим образом.Предварительно происходит устанавка в нулевое состояние всех триггеров 1 матрицы подачей сигнала на вход 21 начальной установки устройства. Затем на установочные входы 22 триггеров 1 матрицы передаются двоичные сигналы (нуль или единица), определяемые значениями соответствующих элементов матрицы смежности исследуемого графа. После этого подается потенциал на вход 23 пуска устройства, который попадает на вход первого элемента ИЛИ50 5 второй группы и вход первого элемента 9 задержки. На выходе первого элемента ИЛИ 5 первой группы появляется сигнал, который попадает на первые входы элементов ИЛИ 3 первой55 строки матрицы элементов ИЛИ и далее на вторые входы элементов И 2 первой строки матрицы элементов И.Если первая вершина сильно связана хотя бы с одной вершиной, то соответствующий триггер 1 первой строки находится в единичном состоянии. В противном случае все триггерыпервой строки находятся в нулевом состоянии, граф не является сильно связным и на всех входах первого элемента ИЛИ 6 третьей группы будут нули.Если К-й триггер 1 первой строки находится в единичном состоянии, то сигнал с его выхода поступает через соответствующий элемент И 2 на первый вход К-го элемента ИЛИ 4 первой группы и на К-й вход первого элемента ИЛИ 6 третьей группы, сигнал с выхода К-го элемента ИЛИ 4 попадает на вход первого элемента И 8 и через К-й элемент ИЛИ 5 - на первь;е входы элементов ИЛИ 3 К-й строки матрицы элементов ИЛИ и далее на вторые входы элементов И 2 К-й строки матрицы элементов И, сигнал с выхода первого элемента ИЛИ 6 попадает на вход первого элемента И 8.Если граявляется сильно связным, то в результате таких переключений на всех входах первого элемента И 8 имеется сигнал "1", в противном случае на всех входах хотя бы одного элемента ИЛИ 4 первой группы или элемента ИЛИ 6 третьей группы отсутствуют сигналы и элемент И 8 не срабатываетСигнал с элемента И 8 поступает на первый вход элемента И 15.Время задержки первого элемента 9 задержки подобрано с учетом всех переключений для определения сильной связности графа, Поэтому сигнал выхода элемента И 8 поступае: до появления сигнала с выхода элемента 9 задержки, значит, на выходе элемента НЕ 12 сигнал есть и срабатываетэлемент И 15, выход которого подключен к первому входу блока 18, сигнализирую,гего о сильной связности граФа. Если граф не сильно связен и на выходе элемента И 8 нет сигнала, то на выходе первого элемента НЕ 11 сигнал есть, поэтому при появлении сигнала на выходе первого элемента 9 задержки срабатывает второй элемент И 14, сигнал с которого попадает на управляющие входы группы элементов И 7, Сигнал с выхода элемента И 14 попадает на вход первого элемента1 ч 4141" ИЛИ э и с его выхода попадает на первые входы элементов ИЛИ 3 первой строки матрицы и через первый элеме г И 7 группы - на вторые входы элементов ИЛИ 3 первого столбца матрицы элементов ИЛИ и далее на вторые ,входы элементов И 2 первой строки и первого столбца матрицы элементов И. Если первая вершина слабо связана хотя бы с одной вершиной, то соответственно триггер 1, первой строки или гервого столбца находится в единччном состоянии, В противном случае все триггеры 1 первой строки и 15 первого столбца находятся в нулевом состоянии, граф является не связнью. на всех входах первого элемента ИЛИ 4 первой группы и первого элемента 1,11 И 6 третьей группы - нули, на 20 в:",одах первого элемента ИЛИ 19 четвертой группы - нули.Если К-й триггер 1 первой строки находится в единичном состнии, сигнал с его выхода поступает через 25 соответствующий элемент И 2 на первый вход К-го элемента ИЛИ 4 первой группы, на К-й вход первого элемента ИГ.И э третьей группы, сигнал с выхода К-гс элемента ИЛ 11 4 попадает на пер вый вход К-го элемента ИЛИ 19 и через К -й элемент ИЛИ э - на первые входы эле.:ентов ИЛИ 3 К-й строки, а через К-й элемент И 7 - на вторые входы элементов ИЛИ 3 К-го столбца ма-рицы и далее на вторые входы элементов И 2 К-й строки и К-го столбца матрицы элементов И, сигнал с выхода первого элемента ИЛИ 6 попадает на второй вход первого элемента ИЛИ 19. 40 переключений для определения слабойсвязности графа, Поэтому при появлении сигнала на выходе элемента 10задержки и отсутствии сигнала навыходе элемента И 20 на выходе элемент ИЕ 13 сигнал есть, срабатываетэлемент И 17, выход которого подключен к третьему входу блока 18.10Формула изобретения ется сигнал, в противном случае на 45 выходе хотя бы одного элемента ИЛИ 19 четвертой группы отсутствует сигнал и элемент И 20 не срабатывает.Сигнал с элемента И 20 поступает на второй вход элемента И 16 и вход эле. элемента НЕ 13.При наличии с ягнала на выходе элемента И 1 ц и эл:мента И 20 срабатывает элемент И 16, выход которого под. ключен к второму входу блока 18 сигф 55 нализирующему о слабой связности граяа Если граф является слабо связньм, то ь результате таких переключений нг всех входах шестого элемента И 8 имеВремя задержки второго элемента1 О задержки подобрано с учетом всех устройство для исследования параметров графов, содержащее матрицу триггеров матрицу элементов И (размерность матриц равна РхР, где Р количество узлов в исследуемом графе), первый элемент И к первую группу элементов ИЛИ, выходы которых соединены с соответствующими входами с первого по Р - й первого элемента И, выход элемента И К-й строки и М-го столбца матрицы соединены с К-м входом И-го элемента ИЛИ первой группы (где К,М=1Р), прямой выход триггера К-й строки и М-го столбца мат" рицы соединен с первым входом элемента И К-й строки и И-го столбца матрицы, установочные входы триггеров матрицы являются установочными входами устройства, входы сброса триггеров матрицы соединены между собой и являются входом начальной установки устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения Функциональных возможностей устройства за счет оценки связности сильно и слабо связных ориентированных графов, в него введены матрицы элементов ИПИ, вторая, третья и четвертая группы элементов ИЛИ, группы элементов И, первый и второй элементы задержки, первый, второй и третий элементы НЕ, с второго по шестой элементы И, выход второго элемента И соединен с первым входом четвертого элемента И и первыми входами элементов И группы, вторые входы которых соединены с выходами соответствующих элементов ИЛИ второй группы и с первыми входами всех элементов ИЛИ соответствующей строки матрицы, выход элемента ИЛИ К-й строки и М-го столбца матрицы соединен с вторым входом элемента М К-й строки М-го столбца матрицы, вторые входы элементов ИЛИ М-го столбца матрицы соединены с выходом И-го элемента И группы, К-й вход И-го элемента ИПИ третьей группы соединен с М-м входом К-го элементаИЛИ первой группы, выход К-го элемента ИЛИ третьей группы соединен с первым входом К-го элемента ИЛИ второйгруппы, с первьм входом К-го элемента ИЛИ четвертой группы, (Р+К)-мвходом первого элемента И, выход которого соединен с первым входом третьего элемента И, и входом первого элемента НЕ, выход которого соединен с 10первым входом второго элемента И,второй вход которого соединен с выходом первого элемента задержки,входом второго элемента задержки ивходом второго элемента НЕ, выход ко торого соединен с первым входом пятого элемента И, второй вход которогосоединен с выходом третьего элемента НЕ, вход которого соединен с вторым входом четвертого элемента И и 20 с выходом шестого элемента И, К-йвход которого соединен с выходом К-гоэлемента ИЛИ четвертой группы, второй вход которого соединен с вторымвходом К-го элемента ИЛИ второй группы и выходом К-го элемента ИЛИ первой группы, третий вход первого элемента ИЛИ второй группы соединен свыходом второго элемента И, выход второго элемента НЕ соединен с вторымвходом третьего элемента И, четвертый вход первого элемента ИЛИ второйгруппы и вход первого элемента задержки объединены и являются входом пуска устройства, выходы третьего, четвертого н пятого элементовИ являются соответственно, первым,вторым и третьим выходами уСтройства,441415 Составитель О. Гречухина Техред М.Дидык Корректор Э. Лончакова Редактор И, Рыб енко Тираж 704 Подписное В 1 ИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5Заказ б 290/53 Производственно-полиграфическое предприятие, г.р д, уг Ужго од ул, Проектная, 4