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

(71) Ленинградскийкий институт им. Внина) ат, Устентов ИЛИ2 две 6 электротехничес- И.Ульянова (Лечисли споль 1 ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ АВТОРСКОМУ СВИДЕТЕЛЬСТ(56) Авторское свидетельство СССР У 656073, кл, С 06 Р 15/36, 1976.Авторское свидетельство СССР Иф 1101834, кл. С 06 Р 15/20, 1982, (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ЧИСЛА ВЕРШИН ПОДГРАФОВ ГРАФА(57) Изобретение относится к вь тельной технике и может быть и зовано для решения комбинаторных задач, таких как выделение связанных подмножеств, при этом достигается сокращение аппаратурных затрройство содержит группу элем1,.1 группу триггеров 2группы элементов И 3, ,3, 17 17 , блок 4 задания топологии, диффек 1ренцирующие элементы 5 5, элементы ИЛИ 6 и 10, регистр 7 сдвига, две группы регистров 8 8, 18 18 триггер 9, вход 11 установки в ноль, генератор 13 тактовых импульсов, два элемента И 12 и 14, распределитель 15 импульсов, элемент 16 задержки, узлы 19 19 индикации числа вер 1шин, узлы 20 20 индикации номеров вершин, счетчик 21, где и - число вершин исследуемого графа, а 1 - число подграфов исследуемого графа.1 134164Изобретение относится к вычислительной технике и может быть использовано при построении специализированных устройств, предназначенныхсдля автоматизированного конструирования радиоэлектронной и электронновычислительной аппаратуры, а такжепри решении задач оптимизации сетейсвязи, 10Цель изобретения - снижение аппаратурных затрат путем сокращениягруппы счетчиков.На фиг. 1 приведена структурнаясхема предлагаемого устройства; нафиг. 2 - реализация блока заданиятопологии графа,Устройство содержит группу 1,; -1элементов ИЛИ, группу триггеров 2, -2,. первую группу 3 -3 элементов И,блок 4 задания топологии графа, дифференцирующие элементы 5,-5, первыйэлемент ИЛИ 6, регистр 7 сдвига,первую группу регистров 8 -8, триггер9, второй элемент ИЛИ 10, вход 11 25установки в "0" устройства, первыйэлемент И 12, генератор 13 тактовыхимпульсов, второй элемейт И 14, распределитель 15 импульсов,. элемент 16задержки, вторую группу 17 -17 элементов И, вторую группу регистров18,-18, узлы индикации 19, -19 числавершин, узлы индикации 20,-20 номеров вершин, счетчик 21Блок задания топологии графа со 35держит п одинаковых моделей вершин,каждая из которых содержит элементы И 22 и 23, элементы ИЛИ 24, элементы И 25-27, 1-й вход 28 блока задания топологии, входы 29-32 1-йгруппы блока задания топологии, выход 33 блока задания топологии иэлемент ИЛИ 34,Устройство работает следующим образом,45Перед началом работы по шине 11на триггеры 2,-2 и 9, регистр 7сдвига, регистры 8-8 , распределитель 15 импульсов, который такжепредставляет собой регистр сдвига,счетчик 21 и регистры 18 -18 подает 1 Нся сигнал установки исходного состояния. При этом на нулевых выходахвсех разрядов регистра 7 устанавливаются единичные потенциалы, которые55вызывают появление единичного сигналана выходе элемента И 14, Этот сигналзаписывает единицу в первый разрядраспределителя 15 и через элемент 16 9 2задержки и элемент ИЛИ 1 задним фрон 1том переводит триггер 2 в единичноесостояние, Единичный потенциал с выхода этого триггера поступает на входпервой вершины блока 4 задания топологии графа и появляется на выходепервой вершины и на выходах всех техвершин, которые образуют множествосвязанных вершин, Через дифференцирующие элементы 5 -5 единичные импульсы с возбужденных выходов (вершин графа) блока 4 поступают черезэлементы ИЛИ 11 -1 на единичные входы соответствующих триггеров 2,-2,которые переходят в единичное состояние, фиксируют связанный подграф,Единичные импульсы с дифференцирующих элементов 5, -5 записываются всоответствующие разряды сдвигающегорегистра 7, а также регистра 8 таккак в данный момент разрешающий потенциал имеется на первом выходе распределителя 15 и, кроме того, любойиз этих импульсов через элемент ИЛИ10 переводит триггер 9 в единичноесостояниеПри этом открывается элемент И 12 и тактовые .импульсы с генератора 13 начинают поступать на сдвигающий вход регистра 7,Каждый тактовый импульс сдвигаеткод регистра 7 на один разряд, Приэтом каждая единица с последнегоразряда регистра 7 считывается всчетчик 21. Считывание происходитдо тех пор, пока регистр 7 полностьюне обнулится, Например, если в регистр 7 записан код 1001100, то двапервых тактовых импульса записи всчетчик 21 не дают, третий и четвертый импульсы записывают две единицы,.затем пятый и шестой импульсы состояние счетчика 21 также не изменяюти седьмой импульс записывает третьюединицу в счетчик 21, Это свидетельствует о том, что первый подграф состоит из трех связанных вершин, номеракоторых 1, 4 и 5 записаны в регистр8. При обнулении регистра 7 на егонулевых выходах появляются единичныепотенциалы, которые открывают элемен-.ты И 14, 17, через которые содержимое счетчика 21 считывается в регистр 18 Один тактовый импульс генератора 13 прокдя через элемент И14, записывает единицу во второй разряд распределителя 15 импульсов итем самым разрешает запись в регистр18 и регистр 8, Этот тактовый им 1341649пульс через элемент 16 задержки сбрасывает в "0" счетчик 21, а пройдячерез элемент ИЛИ 6, перебрасываеттриггер 9 в нулевое состояние, чемзаблокируется на время прохождениетактовых импульсов на регистр 7, ачерез один из открытых элементов И3,"3 устанавливает в единичное состояние тот из триггеров 2 -2 ка И фторому предшествуют триггеры, установленные в единичное состояние ра,нее.В соответствии с приведенным вышепримером в единичное состояние переводится триггер 2 , что позволяетвыбрать новую вершину графа, не вошедшую в первый подграф, и аналогично описанному, возбудить все вершины,. образующие второй связанный падграф. При этом также происходит запись номеров вершин второго падграфа, но уже в регистр 8 , В единичное состояние устанавливаются соответствующие триггеры 2,-2 , происходит запись кода в регистр 7 ичерез элемент ИЛИ 10 в единичное состояние устанавливается триггер 9,После этого начинается считываниеиэ регистра 7 в счетчик 21 числавершин второго подграфа. После обнуления регистра 7 тактовый импульспередвигает единицу на третий выходраспределителя 15 импульсов, а черезэлемент 16 задержки поступает на тотиз непереведенных в единичное состояние триггеров 2,-2, которыйимеет минимальный индекс. Если всетриггеры находятся в единичном состоянии, то этот тактовый импульс появляется на выходе элемента И З,сигнал с которого останавливает работуустройства, заблокировав посредствомэлемента ИЛИ 6, триггера 9 и элемента И 12 прохождение тактовых импульсов на регистр 7, и подает сигналразрешения на углы 19 -19 и 20, -20индикации. При этом высвечиваютсясоответственно число вершин в каждом подграфе и их номера,Блок задания топологии графа 4позволяет передавать сигнал на выходвсех связанных вершин при его наличии .на входе хотя бы одной из них.Блок позволяет отображать топологиюлюбого графа на и заданных вершинах,Для этого каждая верШина графа отображается элементом ИЛИ 34 с ичислом входов, элементами И 22 и 23 и элементом ИЛИ 24, а для отображения ребер,которые могут связывать любую вершинуса всеми остальными,используется и элемент И 25-27,5Если данная вершина участвует вграфе, та на вход 29 необходимо подать единичный потенциал, если определенные ребра участвуют в графе, тана соответствующие входы 30, 31 или32 необходима тоже подать единичныепотенциалы, При этом элемент И 22запрещает прохождение сигналов паребрам с участвующей в графе вершины15 на неучаствующую а элемент И 23 осуществляет запрет перебора неучаствующих в графе вершин, При подаче навход 28 одной из вершин единичногопотенциала ан появляется на выходах33 всех вершин, В соответствии с описанным процессом работы устройствав регистре 18, фиксируются 4 вершины,которые высвечиваются на узле 19, индикации, а в регистре 8, фиксируются25 номера вершин, которые высвечиваютсяна узле 20, индикации,Структура блока задания топологииграфа позволяет отображать любую топологию как ориентированных, так инеориентираванных графов, каждое ребра которых отображается парой встречна направленных ребер, соединяющихдве вершины,35 формула изобретенияУстройство для определения числавершин падграфов графа, содержащее генератор тактовых импульсов, группу из и элементов ИЛИ, где и - число вершин исследуемого графа, первую группу из и элементов И, группу из и триггеров, и дифференцирующих элементов, блок задания топологии, вторую группу из 1 элементов И, где 1 - 45число падграфав исследуемого графа, распределитель импульсов, регистр сдвига, первую группу из 1 регистров, элемент задержки,1 узлов индикации числя Вершин к узлов индикации номеров вершин, два элемента ИЛИ, два элемента И, триггер, выход генератора тактовых импульсов подключен к первым входам первого и второго элементов И, выход первого элемента И подключен к тактовому входу регистра сдвига, информационный выход которого подключен к второму входу второго элемента И, выход которого подключенк первому входу задания режима распределителя импульсов и к входу элемента задержки, выход которого подключен к первому входу, первого элемента ИЛИ, к первому входу первого элемента ИЛИ группы, к первым входам элементов И первой группы, к вхо дам установки в "О" регистров первой группы, регистра сдвига, триггеров группы, к второму входу задания режима распределителя импульсов, к вто рому входу первого элемента ИЛИ и к входу установки в О устройства, 1-й выход распределителя импульсов, где 1 = 1.Е, подключен к первому входу 1-го элемента И второй группы и к входу чтения-записи 1-го регистра первой группы, выходы первого и второго элементов ИЛИ подключены соответственно к входу установки в "О" и к входу установки в н 1 и триггера, выход которого подключен к второму входу первого элемента И, выход -го элемента ИЛИ группы (1 и) подключен к входу установки в "1" 1-го триггера группы, выход 1-го триггера группы подключен к (1+1)-му входам элементов И с -го по п-й первой группы и к 1-му входу блока задания топологии, выход 1-го элемента И первой группы, где 11 и, подключен к первому входу (1+1)-го элемента ИЛИ группы, выход и-го элемента И первой группы подключен к третьему входу первого элемента ИЛИ и к управляющим входам узлов индикации числа вершин и номеров вершин, 1-я группа входов задания топологии графа устройства подключена к 1-й группе входов блока. задания топологии, 1-й выход которогоподключен к входу )-го дифференцирующего элемента, выход которого подключен к информационным входам 1-хразрядов регистров первой группы, кинформационному входу 1-го разрядарегистра сдвига., к ) -му входу второго элемента ИЛИ и к второму входу1-го элемента ИЛИ группы, выход 1-горегистра первой группы подключен кинформационному входу 1-го узлаиндикации номеров вершин, о т л и -ч а ю щ е е с я тем, что, с цельюснижения аппара.турных затрат, в устройство введены счетчик и вторая группа из 1 с регистров, причем. выход переноса регистра. сдвига подключен ксчетному входу счетчика, .-й информационный выход которого подключен к 75 второму входу 1-го элемента И второйгруппы, выход второго элемента И подключен к третьим входам элементов Ивторой группы, вход установки в "Оустройства подключен к входам установки в О" счетчика и регистров второй группы, выход 1-го элемента Ивторой группь; подключен к информационному входу " -го регистравторой группы , выход которогоподключен к информационному вхо - 35ду 1-гоузла индикации числавершин,