Модель узла для исследования графа

Союз СоввтскнкСоцнапнстнческниРеспублик ОП ИГРАНИ ЕИЗОБРЕТЕНИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 11907552(22)Заявлено 18,02.80 (21) 2884945/18-24с присоединением заявки йе -па делан изобретений н открытий(72) Авторы изобретения нститут электродинамики АН(54) МОДЕЛЬ УЗЛА ИССЛЕДОВАНИЯ ГРАФА Изобретени ному моделиро фов и может б е относится к электронванию задач теории граыть .использовано приециализированных цифтельных устройств дляграфов, в частности дляи нахождения всех макависимых множеств в построении сп ровых вычисли исследованиярешения задачсимальных нез графе.Известно устройство для моделирования сетевого графика, содержащее блок управления, блок регистрации, блок стоимостноресурсных ограничителей, блоки коммутации и блоки моделей ветвей, состоящие из счетчиков, триггеров, элементов И и схем индикации 11 .Однако это устройство не решает задачу о нахождении максимальных не зависимых множеств в графе.Наиболее близким по технической сущности к предлагаемому является устройство для моделирования ветви графа, содержащее триггер, который единичным выходом связан с блокоминдикации и с первыми входами первого и второго элементов И, вторыевходы которых связаны с первым и вторым полюсами, а выходы первого исвторого элементов И соединены с первым и вторым взводами первого элемента ИЛИ 1 21,Однако известное устройства так"же не обеспечивает решение задачитоо максимальном независимом множест"ве графа.Цель изобретения - расширениефункциональных возможностей за счетвозможности решения задачи нахожде 15ния максимальных независимых множестграфа.Поставленная цель достигается темцто в модель узла для исследованияграфа, содержащую первый триггер,единичный выход которого подключен квходу блока индикации и к первымвходам первого и второго элементовИ, выходы которых соединены соотввт90552Составитель А. Яицков Редактор В.Лазаренко Техред А. Ач Корректор Н. шОвыдкая Заказ 592/58 Тираж 732 Подписное ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий 113035, Москва, Е, Раушская наб., д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная.907552 ственно с первым и вторым входами первого элемента ИЛИ, вторые входы первого и второго элементов И подключены соответственно к первому и второму входам модели, введены два регистра, триггеры, элементы И и элементы ИЛИ, третьи входы первого и второго элементов И подключены к третьему входу модели, входной полюс которой соединен с третьим входом 1 О первого элемента ИЛИ, с нулевым входом второго триггера, с нулевым входом первого разряда первого регистра, с первым входом третьего элемента И и с первым входом второго эле мента ИЛИ, выход которого подключен к нулевому входу первого триггера, единицный вход которого соединен с выходом четвертого элемента И и с единичным входом третьего триггера, выход которого подключен к информационному входу второго регистра, единицный выход первого разряда которо .0 соединен с первым входом четвертого элемента И, с первым выходом модели и с вторым входом третьего элемента И, выход которого подключен к второму выходу модели, четвертый вход которой соединен с вторым входом четвертого элемента И и с первым входом пятого элемента И, выход которого подключен к единичному входу вто. рого триггера, единичный выход которого соединен с информационным входом первого регистра, единичный вы 35 ход первого разряда которого подключен к второму входу пятого элемента И, к третьему выходу модели и к пер" вому входу шестого элемента И, второй вход которого соединен с пятым вхо 40 дом модели и с первым входом седьмого элемента И, выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с четвертым выходом модели, шестой45 вход которой подключен к первому входу восьмого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, выход первого элемента И подключен к второму входу второго элемента ИЛИ и к единичному50 входу первого разряда первого регистра, нулевой выход первого разряда которого соединен с вторым входом седьмого элемента И, выход второго элемента И подключен к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И и с единичным входом чет 4вертого триггера, единичный выход которого подключен к второму входу восьмого элемента И, выход первого элемента ИЛИ соединен с нулевым входом третьего триггера и с нулевым входом первого разряда второго регистра, вход сдвига и вход реверса которого соединены соответственно с входом сдвига и входом реверса первого регистра и подключены соответственно к седьмому и восьмому входу модели выход четвертого элемента ИЛИ является выходным полюсом модели.На фиг. 1 изображена структурная схема модли узла; на фиг. 2 - пример графа, где точками 1-Ч 1 обозначены его вершины.Модель узла содержит регистры 1 и 2 триггеры 3-6, элементы И 7-1 ч, эле менты ИЛИ 15-18, блок 19 индикации, входной полюс 20, выходной полюс 21 и входы и еуоды 22"23. Регистры 1- 2 реализованы по схеме реверсивного регистра сдвига, направление сдвига которого зависит от уровня сигнала реверса на входе 26.Рещение задачи о нахождении всех максимальных независимых множеств графа реализуется в предлагаемой модели по с.едующему методу.Пусть дан неориентированный граф С=(Х,Г), где Х - вершины; Г -ребра. Независимое множество вершин - это множество вершин графа С такое, что любые две вершины в нем не смежны, т,е, никакая пара вершины не соединена ребром, т.е. любое множество 5 С , которое удовлетворяет условие 5 П Г(5)= ф Г(5) - множество вершин, оставляющее отображение вершин из множества (5, ф - пустое множество), является независимым множеством вершин. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило, т.е. множество 5 является максимальным независимым множеством, если оно удовлетворяет условиям 5 ЙГ(5)=Ф 1 НОГ(Н) ФФНЗ 5 (для всех Н, включающих множество 5),.Если Я есть семейство всех независимых множество графа С, то числос(,1 С = вах 151сЕОназывается числом независимости графа 6, а множество 5 , на котором)этот максимум достигается, называется наибольшим независимым множеством.90755 ЗО Для решения задачи о максимальном независимом множестве графа модели узлов последова 1 ельно просматриваются в произвольно заданном порядке ( прямой ход). Для этого подается спрашивающий сигнал на вход 32, чем осуществляется выбор той или иной модели узла. Наличие единичного сигнала на выходе триггера 3 и разрешающего потенциала на входе 31 обеспечивает прохождение в выбранной модели узла опрашивающего сигнала с входа 31 через элемент И 8 и через элемент ИЛИ 15 на нулевые входы триггера 5 и первого триггера регистра 2 для записи "0" в первый его разряд, Сброс триггера 5 в "0" означает, что при последующих сдвигах регистра 2 на прямом ходе в него на каждом шаге будет записываться "0".Одновременно с этим выходной сиг" нал элемента И 8 через элемент ИЛИ 17 поступает на выходной полюс 21 и далее (с учетом связей моделей узлов Известен метод отыскания максимальных независимых множеств, который являестя существенно упрощенным перебором, использующим дерево поиска:Шаг 1 Пусть 50= "-о р 0 (ф к=0. 5Прямой ход4Шаг 2. Выбрать вершину х,;к 6 О исформировать В О , + , оставляя 1 и 0 без изменени . Положитьк=к+1."КОШаг 3. Если удовлетворяется условие: ХЕ, О, такое, что Г(х)й Ок = ф, топерейти к шагу 5, иначе к шагуШаг 4. Если (1 =" .=ф, в .о значит максимальное независимое множество 5 К 15сформировано и следует перейти к шагу 5. Если Оф, а (1 ф, то перейти к шагу 5. Иначе и. в .рейти к шагу 2.Обратный ходШаг 5 Положить к=к. Удалить х 20из 51+, цтобы получить 5 . Исправить О и 0+, удалив вершину х изи добавив ее к П к. Если к=0,0 ф Фф то перейти к шагу 2, еслиК.к=0, " ." =ф, то остановиться, так 25как к этому моменту найдены все максимальные независимые множества, Иначе перейти к шагу 3.С целью упрощения модели узла,аппаратно реализующей приведенныйметод, принимаем5 =Х, где Х - множество вершинграфа,Тогда на каждом шаге5,- - 5 - Г(х), а не35;,:,О хМножества П и Рк определяются Ьо: Ок -Г (х)К 1 +О+ - (Г(х) 0 хЕ) 40Если модель узла принар"ежит одному из множеств О или 0 , то соответственно входной триггер (первыйразряд регистра 1 или 2) находится вединицном состоянии, Множество моделей узлов, у которых указанные триггера находятся в единице, образуютсоответственно множествак+Принадлежность модели узла максимальному независимому множеству узлов графа определяется единичным состоянием триггера 3, которое индицируется с помощью блока 19 индикации.Выходы триггеров 4 и 5 связаны с информационными входами регистров 1 и2, т.е. в регистры заносится информация о состоянии этих триггеров накаждом цикле сдвига. 2 бМодель узла для исследования графа при решении задачи нахождения максимальных независимых множеств графа работает следующим образом.Предварительно полюса 20 и 21 всех моделей узлов соединяются между собс й в соответствии с топологией исследуемого графа. Выходы 22 и входы 23 всех моделей узлов соединены таким образом, что образуется последовательная цепь у которой входным полюсом является вход 23 первой в цепи модели узла, а выходным - выход 22 последней. В первый разряд регистра 2 всех моделей узлов записывается , что соответствует выражению Ос, =Х, где Х - множество узлов графа, а в первый разряд регистра 1 записывается "0", т,е.= ф, где ф - пустое множество. оОстальные разряды регистрови 2 всех моделей узлов находятся в "0". Триггеры 3 и 5 предварительно устанав.ливаются в "1" а триггеры 4,6 - в "0" во всех моделях узлов.В исходном состоянии на входы 26 и 31 подается разрешающийпотенциал (признак прямого хода), а на входы 33 - запрещающий. На входы 25 подается импульс сдвига для запоминания исходных множеств Оо и Опри этом информация сдвигается на один разрядвправо, а входные триггеры регистров1 и 2 принимают информацию с триггеров 4 и 5в соответствии с топологией исследуемого графа), на входной полюс 20 тех моделей узлов, которые инцидентны данному, В этих моделях сигнал поступит на нулевые входы регистра 1 и триггера 4. В первом этот сигнал подтвердит нулевое исходное состояние его первого разряда, а триггер 4 имеет аналогичное с триггером 5 назначение. Сигнал с полюса 20 через 1 о элемент ИЛИ 16 сбросит в "0" триггер 3, а через элемент ИЛИ 15 установит в "0" триггер первого разряда регистра 2 и триггер 5.В результате записи "0" в ре гистр 2 выбранной опрашивающим сигналом модели узла и всех моделей узлов с ней связанных сформируется новое+в соответствии с выражениемО+ =О+ -(Г (хс) Охс, (1)л+ т.е, йэ исходного множества О уда-о лены выбранный узел и узлы ему, лнцидентные по топологии исследуемого графа.Установив в н 0" триггеров 3 в мо делях узлов, связанных с выбранной соответствует выражению5-- 5, -Г (хЕ) (2) Поступление сигнала на "0" вход регистра 1 соответствует действию по зО формуле0-.,: О- Г(х 1) (3) Таким образом, множества Балл, " +лкак этого требует первый шаг алгоритма, сформированы,Вновь сформированные 0и Ял л необходимо запомнить, для этого на входы 25 всех моделей узлов подается импульс сдвига, который формируется по сигналу с выходного полюса 21.40 Направлени сдвига, который формируется по сигналу с выходного полюса 21. Направление сдвига определяет ся уровнем ( "н или "0" ) сигнала реверса на входах 26.Следующий опрашивающий сигнал на входе 32 выбирает новую модель узла, Гсли в ней триггер 3 стоит в "1", то описанный выше процесс повторяется. Если триггер 3 был ранее сброшен в "0" сигналом с полюса 20 от предыдущих опрашиваемых моделей узлов, то в ней на этом шаге опроса ничего не изменится и импульс сдвига регистров на входах 25 не формируется. 55Опрос моделей узлов продолжается до тех пор, пока на очередном шаге окажется, что на выходах 24 и 27 всех моделей узлов сформированы нулевые сигналы, т.е.(4)Это означает, что первое максимальное независимое множество сформировано и состоит из моделей узлов, укоторых триггеры 3 сохранили единицное состояние, которое индицируетсяс помощью блока 19 индикации,После этого начинается обратныйпроцесс. Для этого предварительно навходы 26 моделей узлов подается сигнал, соответствующий обратному направлению сдвига регистров ( реверс), ана входы 25 - импульс сдвига, которыйустанавливает на,выходе регистров информацию, полученную на предыдущем шаге, т,е. первые разряды регистровбудут выдавать данные о принадлежности моделей узлов множеству 0 1 ,а первые разряды регистров 2 - множеству О +. С входов 31 снимается,+а на входы 33 подается разрешающийсигнал 1,признак обратного хода) .Начиная с последней опрошенноймодели узла, на которой был остановлен прямой ход решения, на входе 32 вновьпоследовательно для всех моделей узловпоступают опрашивающие сигналы,но впорядке, обратном прямому хору.Триггер 3 последней опрошенной напрямом ходе модели узла сохранил "1"состояние, поэтому импульс опроса свхода 32 через элемент 7 И подаетсяна единичный вход первого триггера регистра 1, устанавливая его вчерез элемент 15 ИЛИ на нулевые входытриггера 5 и триггера первого разрядарегистра 2; через элемент ИЛИ 16,нанулевой вход триггера.Поступление сигналов на "1" входрегистра 1 и "0" вход регистра 2 итриггера 3 соответствует тому, чтоопрашиваемая модель узла вычеркивается из множеств Вк л, ",и добавляется к множеству ), как это итребуется на шаге возвращения алгоритма.Далее следует проверка условияС С такая, что Г(х)Д =ф (5)т,е. существует ли хотя бы одйа модель узла, принадлежащая множествуотображение которой (множествоузлов, связанных с ней ) и множество9 9075На вход 23 первой в цепочке модели узла подается импульс проверки условия5). Этот импульс поступает на первый цход элемента И 13, вторым входом которого управляет нулевой 5 выход первого триггера регистра 1.Если множество Опусто, то импульс проверки условия5 ) беспрепятственно проходит через элементы И 13 и ИЛИ 8 во всех моделях узлов и 10 появляется на выходе 22 последней в цепи модели узла. Если Я, не пусто, т.е. есть хотя бы одна модель узла, у которой в регистре 1 первый триггер находится на данном шаге в "1", 15 то в этой модели узла импульс проверки условия ( 5) проходит не через элемент И 13, а через элемент И 12, устанавливая триггер 6 в единичное состояние, и далее через элемент 20 ИЛИ 17 поступает на выходной полюс 21.Как упоминалось выше, с полюса 21 сигнал поступит на полюса 20 тех моделей узлов, которые связаны с данной в соответствии с топологией гра Фа, С полюса 20 сигнал поступит в этих моделях узлов на один из входов элемента И 9, второй вход которого управляется единичным выходом триггера первого разряда регистра 2, хра- зо нящего информацию о принадлежности данной модели узла множеству и , На выходе элемента И 9 и на выходе 28 сигнал появится в том случае, если данная модель узла одновременно при" надлежит множествуГ(х) и 0Если это произойдет хотя бы в одной модели узла, то условие5) для модели узла, принадлежащей множеству Я (у нее первый триггер регистра 1 находится в "1 состоянии), не выполняется, Следовательно, проверку ,условия 5 ) необходимо продолжить длядругих моделей узлов, входящих в Ц.Для этого на входы 30 всех моделей узлов подается импульс, который проходит через элемент И 4 в той из них, у которой триггер 6 находится в "1" состоянии, и церез элемент ИЛИ 18 появляется на выходном полюсе 22.Таким образом, наличие сигнала на выходе 28 хотя бы у одной модели узла в момент проверки условия 1,5 ) говорит о том что это условие не выполняетсяЭ55 и необходимо продолжить проверку. Напротив, если такой сигнал не сформировался ни у одной из моделей узлов в момент проверки, то это означает,1 О52что условие 5) выполнено хотя бы для одной модели узла и дальнейшая проверка не нужна, цто является сигналом для перехода к шагу возврата алгоритма.Итак, если условие 5 ) выполненото на входы 25 всех моделей узловвновь поступает импульс сдвига, формируя новые 0 к, 0, а на входы 32продолжают последовательно подаваться опрашивающие импульсы, выбираякаждый раз новую модель узла, но впорядке, обратном прямому ходу Если у вновь опрашиваемой модели триггер 3 стоит в "0", то в ней ничего непроисходит и импульс сдвига на входах 25 не формируется, напротив, описанный выше шаг возврата с проверкой условия5 ) повторится снова, если триггер 3 у очередной опрашиваемой модели узла стоит в "1".Если на очередном шаге возвращения при проверке условия ( 5 ) окажется, цто оно не выполняется ни для какой модели узла из множества ЯК, тоэто ознацает, цто обратный процессокончен и мОжно переходить к прямому шагу для формирования нового максимального множества независимых верших в графе. Для этого на входы 29подается импульс, который через элементы 1 10, 11 установит в "1"соответственно триггеры 4 и 5 в техмоделях узлов, которые на данном+шаге принадлежат множествам О и чцто необходимо для выполнения ново-,го процесса прямого хода и т.д,Процесс Формирования всех максимальных незаивисимых множеств вершин в графе будет завершен когдаО+ =фт.е. просмотрены все вершины графа,В таблице представлен пример работы алгоритма по нахождению максимальных независимых множеств для графа из восьми вершинфиг.2). Знаком4.отмечены максимальные независимыемножества граФа С,Использование новых элементов-реверсивных регистров сдвига дополнительных триггеров, элементов И, и ИЛИ и новых связей позволяет получить существенно новый положительный эффект, т.е. решить важную задачу нахождения всех максимальных независимых множеств в графе.,Анализ этих множеств дает возможность определить одно из важных структур=Фо 7 Ф 1,3,7 4,5,7 3 Ф 1,4 1,5,7 1)5 7 12,3,4,5,6,7,8 О 4,5,7,8 1 2,4 2,4,8 7 7,8 2,5,72,5,7, Р 2,5,7 ных свойств графа - число независимости, что имеет самостоятельное значение в теории графов, а также имеетразнообразные непосредственные приложения при ведении проектного планирования исследовательских работ,в кластерном анализе, параллельныхвычислениях на ЭВИ, при решении задач размещения в системах автоматического проектирования радиоэлектрон 52 12ной и электронно-вычислительной аппаратуры.Важной является возможность решения задачи нахождения числа независимости к решению задачи о хроматическом числе графа.Аппаратная реализация метода обеспечивает распараллеливание решения задачи и значительно сокращает время решения,907552 34 2,5 4,5 1,2 3,6 1,6 3,73,7,8 1,81,6,7 3,7 4,5,6,7,8 О 1,2,3 1,2,61,2,3 4 5,6,7,8 7,8 1,2 1,2,3,4,5 6,7,8 7,8 2,3,4,5,7 Ф 1,2,3,8 И, выходы которых соединены соот"ветственно с первым и вторым входамипервого элемента ИЛИ, вторые входыпервого и второго элементов И подключены соответственно к первомуи второму входам модели, о т л ич а ю щ а я с я тем, что, с целью 5 52 2 3 2 6 5 6 формула изобретения Модель узла для исследования графа, содержащая первый триггер, единичный выход которого подключен к входу блока индикации и к первым входам первого и второго элементов 1 т 2.)61,2,3,512,,7 Продолжение таблицы 7,8 1 3,4,5,6,7,8 О 6,7,8 1 Ф 2 7,8 190расширения функциональных возможностей за счет возможности решения задачи нахождения максимальных независимых множеств графа, в нее введены два регистра, триггеры, элементы И и элементы ИЛИ третьи входы первого и второго элементов И подключены к третьему входу модели, входной полюс которой соединен с третьим входом первого элемента ИЛИ с нулевым входом второго триггера, с нулевым входом первого разряда первого регистра, с первым входом третьего элемента И и с первым входом второго элемента ИЛИ, выход которого подключен к нулевому входу первого триггера, единичный вход которого соединен с выходом четвертого элемента И и с единичным входом третьего триггера, выход которого подключен к информационному входу второго регистра, единичный выход первого разряда которого соединен с первым входом четвертого элемента И, с первым выходом модели и с вторым входом третьего элемента 4, выход которого подключен к второу выходу модели, четвертый вход которой .соединен с вторым входом четвертого элемента И и с первым входом пятого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с информационным входом первого регистра, единичный выход первого разряда которого подключен к второму входу пятого элемента И, к третьему выходу модели и к первому входу шестого элемента И, второй вход которого соединен с пятым входом мо 7552 16дели и с первым входом седьмого элемента И, выход которого подключен кпервому входу третьего элемента ИЛИвыход которого соединен с четвертымвыходом модели, шестой вход которойподключен к первому, входу восьмогоэлемента И, выход которого соединенс вторым входом третьего элементаИЛИ, выход первого элемента И подклю1 О чен к второму входу второго элементаИЛИ и к единичному входу первогоразряда первого регистра, нулевойвыход первого разряда которого соединен с вторым входом седьмого эле 15 мента И, выход второго элемента Иподключен к первому входу четвертого элемента ИЛИ, второй вход которогосоединен с выходом шестого элементаИ и с единичным входом четвертого20 триггера, единичный выход которогоподключен к второму входу восьмогоэлемента И, выход первого элементаИЛИ соединен с нулевым входом третьего триггера и с нулевым входом пер 25 вого разряда второго регистра, входсдвига и вход реверса которого соединены соответственно с входом сдвига и с входом реверса первого регистра и подключены соответственноЗо к седьмому и восьмому входу модели,выход четвертого элемента ИЛИ является выходным полюсом модели,Источники информациипринятые во внимание при экспертизеАвторское свидетельство СССР8 570060, кл. 6 06 б 7/122, 1975.2, Авторское свидетельство СССРй 363994, кл. С 06 С 7/122, 1970