Модель узла для исследования графа
Союз Соввтскни
Социалистических
Республик
ОПИСЛНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
Опубликовано 23.02 82 Бюллетень ¹ 7 Дата опубликования описания 25. 02, 82 (5I 3<. К . 06 F 15/20 тасударстеенный квинтет СССР (53) У,П, 681.333 (088.8) па делен изобретений н открытий В. В. Васильев, О. Н. Голованова, Е. A. Ралдугин, А. И. Щетинин и Н. В. федотов (72) Авторы изобретения Институт электродинамики АН У (71) Заявитель (54) МОДЕЛЬ УЗЛА ИССЛЕДОВАНИЯ ГРАФА Изобретение относится к электронному моделированию задач теории графов и может быть .использовано при построении специализированных цифровых вычислительных устройств для исследования графов, в частности для решения задачи нахождения всех максимальных независимых множеств в графе. Известно устройство для моделирования сетевого графика, содержащее блок управления, блок регистрации, блок стоимостноресурсных ограничителей, блоки коммутации и блоки моделей ветвей, состоящие из счетчиков, триггеров, элементов И и схем индикации (1 ). Однако это устройство не решает задачу о нахождении максимальных независимых множеств в графе. Наиболее близким по технической сущности к предлагаемому является устройство для моделирования ветви графа, содержащее триггер, который единичным выходом связан с блоком индикации и с первыми входами первого и второго элементов И, вторые входы которых связаны с первым и вто рым полюсами, а выходы первого и с второго элементов И соединены с первым и вторым в одами первого элемента ИЛИ (21. Однако известное устройства так" we не обеспечивает решение задачи то о максимальном независимом множестве графа. Цель изобретения - расширение функциональных возможностей за счет возможности решения задачи нахожде13 ния максимальных независимых множеств графа. Поставленная цель достигается тем, что в модель узла для исследования графа, содержащую первый триггер, единичный выход которого подключен к входу блока индикации и к первым входам первого и второго элементов И, выходы которых соединены соотввт907552 ственно с первым и вторым входами первого элемента ИЛИ, вторые входы первого и второго элементов И подключены соответственно к первому и второму входам модели, введены два регистра, триггеры, элементы И и элементы ИЛИ, третьи входы первого и второго элементов И подключены к третьему входу модели, входной полюс которой соединен с третьим входом 1о первого элемента ИЛИ, с нулевым входом второго триггера, с нулевым входом первого разряда первого регистра, с первым входом третьего элемента И и с первым входом второго элемента ИЛИ, выход которого подключен к нулевому входу первого триггера, единичный вход которого соединен с выходом четвертого элемента И и с единичным входом третьего триггера, выход которого подключен к информационному входу второго регистра, единичный выход первого разряда которо о соединен с первым входом четвертого элемента И, с первым выходом модели и с вторым входом третьего элемента И, выход которого подключен к второму выходу модели, четвертый вход которой соединен с вторым входом четвертого элемента И и с первым входом пятого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с информационным входом первого регистра, единичный вы35 ход первого разряда которого подключен к второму входу пятого элемента И, к третьему выходу модели и к пер" вому входу шестого элемента И, второй вход которого соединен с пятым вхо40 дом модели и с первым входом седьмого элемента И, выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с четвертым выходом модели, шестой 4$ вход которой подключен к первому входу восьмого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, выход первого элемента И подключен к второму входу второго элемента ИЛИ и к единичному 50 входу первого разряда первого регистра, нулевой выход первого разряда которого соединен с вторым входом седьмого элемента И, выход второго элемента И подключен к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И и с единичным входом чет4 вертого триггера, единичный выход которого подключен к второму входу восьмого элемента И, выход первого элемента ИЛИ соединен с нулевым входом третьего триггера и с нулевым входом первого разряда второго регистра, вход сдвига и вход реверса которого соединены соответственно с входом сдвига и входом реверса первого регистра и подключены соответственно к седьмому и восьмому входу модели выход четвертого элемента ИЛИ является выходным полюсом модели. На фиг. 1 изображена структурная схема мод ли узла; на фиг. 2 - пример графа, где точками I-Vlit обозначены его вершины. Модель узла содержит регистры 1 и 2 триггеры 3-6, элементы И 7-14, эле менты ИЛИ 15-18, блок 19 индикации, входной полюс 20, выходной полюс 21 и входы и е"оды 22"23. Регистры 12 реализованы по схеме реверсивного регистра сдвига, направление сдвига которого зависит от уровня сигнала реверса на входе 26. Решение задачи о нахождении всех максимальных независимых множеств графа реализуется в предлагаемой модели по с .едующему методу. Пусть дан неориентированный граф G=(X Ã), где Х - вершины; Г -ребра. Независимое множество вершин - это множество вершин графа G такое, что любые две вершины в нем не смежны, т.е. никакая пара вершины не соединена ребром, т.е. любое множество S С А, которое удовлетворяет условие S h Г(5)= ф Г(5) - множество вершин, составляющее отображение вершин из множества (S, ф — пустое множество), является независимым множеством вершин. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило, т.е. множест, во S является максимальным независимым множеством, если оно удовлетворяет условиям ЫГ(5 j = Ф НОГ(Н) Ф® Q H S (для всех Н, включающих множество S),. Если Q есть семейство всех независимых множество графа G, то число с(,I G j = max)SI Seg называется числом н зависимости графа G, а множество S, на котором ) этот максимум достигается, называется наибольшим независимым множеством. 90755 Для решения задачи о максимальном независимом множестве графа модели узлов последова1ельно просматриваются в произвольно заданном порядке (прямой ход). Для этого подается спрашивающий сигнал на вход 32, чем осуществляется выбор той или иной модели узла. Наличие единичного сигнала на выходе триггера 3 и разрешающего потенциала на входе 31 обеспечивает прохождение в выбранной модели узла опрашивающего сигнала с входа 31 через элемент И8 и через элемент ИЛИ 15 на нулевые входы триггера 5 и первого триггера регистра 2 для записи "0" в первый его разряд. Сброс триггера 5 в "0" означает, что при последующих сдвигах регистра 2 на прямом ходе в него на каждом шаге будет записываться "0". Одновременно с этим выходной сиг" нал элемента И 8 через элемент ИЛИ 17 поступает на выходной полюс 21 и далее (с учетом связей моделей узлов Известен метод отыскания максимальных независимых множеств, который являестя существенно упрощенным перебором, использующим дерево поиска: Шаг. 1 Пусть Бо — — Р =ср, Q. =х, к=-0. Прямой ход Шаг 2. Выбрать вершину х.;к О и сформировать S«< О „, + „, оставляя и Q без изменени . Положить к=к+1. -К к, ! L àã 3. Если удовлетворяется условие : xE, Qk такое, что C(x)n Q+ = ф, то перейти к шагу 5, иначе к шагу 4. Шаг 4. Если (! =" .=ф, †.о значит максимальное независимое множество 5К !5 сформировано и следует перейти к шагу 5. Если О < --- ф, а 1 ф ф, то перейти к шагу 5. Иначе и. †.рейти к шагу 2. Обратный ход Шаг 5. Положить к=к-1. Удалить х„ < 20 из S +, чтобы получить 5 . Исправить (, и с)к, удалив вершину x„ из и добавив ее к Qy. Если к О, Q+ Фф то перейти к шагу 2, если K к=С, " ." =ф, то остановиться, так 2s как к этому моменту найдены все мак. симальные независимые множества. Иначе перейти к шагу С целью упрощения модели узла, аппаратно реализующей приведенный метод, принимаем 5 =X, где Х вЂ” множество вершин графа. Тогда на каждом шаге S, — - Sl< — Г(xik), а не 35 „„=,u (- Множества П и Р +„определяются ho К+ формула 0 y — Г (xik) К + Q „=, + - (Г(х ) u(x i k() Если модель узла принар "ежит одному из множеств О или О,, то соответственно входной триггер (первый разряд регистра 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 подается импульс сдвига для запоминания исходных множеств Q и О, при этом информация сдвигается на один разряд вправо, а входные триггеры регистров 1 и 2 принимают информацию с триггеров 4 и 5. 907552 в соответствии с топологией исследуемого графа), на входной полюс 20 тех моделей узлов, которые инцидентны данному. В этих моделях сигнал поступит на нулевые входы регистра 1 и триггера 4. В первом этот сигнал подтвердит нулевое исходное состояние его первого разряда, а триггер 4 имеет аналогичное с триггером 5 назначение. Сигнал с полюса 20 через 30 элемент ИЛИ 16 сбросит в "О" триггер 3, а через элемент ИЛИ 15 установит в "0" триггер первого разряда регистра 2 и триггер 5. В результате записи "0" в ре- is гистр 2 выбранной опрашивающим сигналом модели узла и всех моделей узлов с ней связанных сформируется новое Qy+, в соответствии с выражением Q+ „=О -,Г (х!! ) u xi ), (1) л+ т.е. йз исходного множества О уда -о лены выбранный узел и узлы ему, лнцидентные по топологии исследуемого графа. Установив в нО" триггеров 3 в мо- 25 делях узлов, связанных с выбранной, соответствует выражению SÊ л =S к-Г (xil;) (2) Поступление сигнала на "О" вход регистра 1 соответствует действию по ЗО формуле Q-„„,,= =O «- Г() (3} Таким образом, множества 5!сл.л, ", +„, 4 +<, как этого требует первый шаг алгоритма, сформированы. Вновь сформированные Q u необходимо запомнить, для этого на входы 25 всех моделей узлов подается импульс сдвига, который формируется по сигналу с выходного полюса 21. 40 Направлени сдвига, который форми руется по сигналу с выходного полюса 21. Направление сдвига определяет. ся уровнем ("1 или "О" ) сигнала реверса на входах 26. Следующий опрашивающий сигнал на входе 32 выбирает новую модель узла. Если в ней триггер 3 стоит в "1", то описанный выше процесс повторяется. Если триггер 3 был ранее сброшен в "0" сигналом с полюса 20 от предыдущих опрашиваемых моделей узлов, то в ней на этом шаге опроса ничего не изменится и импульс сдвига регистров на входах 25 не формируется. Опрос моделей узлов продолжается до тех пор, пока на очередном шаге окажется, что на выходах 24 и 27 всех моделей узлов сформированы нулевые сигналы, т.е. (4) Это означает, что первое максимальное независимое множество сформировано и состоит из моделей узлов, у которых триггеры 3 сохранили единичное состояние, которое индицируется с помощью блока 19 индикации. После этого начинается обратный процесс. Для этого предварительно на входы 26 моделей узлов подается сигнал, соответствующий обратному направлению сдвига регистров (реверс), а на входы 25 — импульс сдвига, который устанавливает на,выходе регистров информацию, полученную на предыдущем шаге, т,е. первые разряды регистров 1 будут выдавать данные о принадлежности моделей узлов множеству Q < <, а первые разряды регистров 2 — множеству О, +„. С входов 31 снимается, + а на входы 33 подается разрешающий сигнал (признак обратного хода) . Начиная с последней опрошенной модели узла, на которой был остановлен прямой ход решения, на входе 32 вновь последовательно для всех моделей узлов поступают опрашивающие сигналы,но в порядке, обратном прямому хору. Триггер 3 последней опрошенной на прямом ходе модели узла сохранил "1" состояние, поэтому имп.-льс опроса с входа 32 через элемент 7 И подается на единичный вход первого триггера регистра 1, устанавливая его в "1", через элемент 15 ИЛИ на нулевые входы триггера 5 и триггера первого разряда регистра 2; через элемент ИЛИ 16,на нулевой вход триггера. Поступление сигналов на "1" вход регистра 1 и "О" вход регистра 2 и триггера 3 соответствует тому, что опрашиваемая модель узла вычеркивается из множеств S q, ",.< и добавляется к множеству ) „ „, как это и требуется на шаге возвращения алгоритма. Далее следует проверка условия ЗХС С,,та-., - Г(х)ЛО;-ф(5), т,е. существует ли хотя бы одйа модель узла, принадлежащая множеству отображение которой (множество узлов, связанных с ней ) и множество + моделей узлов, составляющих О, не пересекаются, т.е. у них нет общих элементов. Проверка осуществляется следующим образом. 9 9075 На вход 23 первой в цепочке модели узла подается импульс проверки условия (5). Этот импульс поступает на первый цход элемента И 13, вторым входом которого управляет нулевой 5 выход первого триггера регистра 1. Если множество О пусто, то импульс проверки условия (5 ) беспрепятственно проходит через элементы И 13 и ИЛИ !8 во всех моделях узлов и 10 появляется на выходе 22 последней в цепи модели узла. Если Q не пусто, т.е. есть хотя бы одна модель узла, у которой B регистре первый триггер находится на данном шаге в "1", 15 то в этой модели узла импульс проверки условия (5) проходит не через элемент И 13, а через элемент И 12, устанавливая триггер 6 в единичное состояние, и далее через элем нт 20 ИЛИ 17 поступает на выходной полюс 21. Как упоминалось выше, с полюса 21 сигнал поступит на полюса 20 тех моделей узлов, которые связаны с данной в соответствии с топологией графа. С полюса 20 сигнал поступит в этих моделях узлов на один из входов элемента И 9, второй вход которого управляется единичным выходом триггера первого разряда регистра 2, хра- зо нящего информацию о принадлежности данной модели узла множеству и . На выходе элемента И 9 и на выходе 28 сигнал появится в том случае, если данная модель узла одновременно при" надлежит множеству Г(х) и Q < Если это произойдет хотя бы в одной модели узла, то условие (5) для модели узла, принадлежащей множеству Я„ (у нее первый триггер регистра 1 находится в "1 состоянии), не выполняется. Следовательно, проверку ,условия (5 ) необходимо продолжить для других моделей узлов, входящих в 0,. Для этого на входы 30 всех моделей узлов подается импульс, который проходит через элемент И 14 в той из них, у которой триггер 6 находится в "1" состоянии, и через элемент ИЛИ 18 появляется на выходном полюсе 22. Таким образом, наличие сигнала на выходе 28 хотя бы у одной модели узла в момент проверки условия (5 ) говорит о том что это условие не выполняется У S5 и необходимо продолжить проверку. Напротив, если такой сигнал не сформировался ни у одной из моделей узлов в момент проверки, то это означает, 10 52 что условие (5) выполнено хотя бы для одной модели узла и дальнейшая проверка не нужна, что является сигналом для перехода к шагу возврата алгоритма. Итак, если условие (5 ) выполнено то на входы 25 всех моделей узлов вновь поступает импульс сдвига, формируя новые Q<<, Q а на входы 32 + продолжают последовательно подаваться опрашивающие импульсы, выбирая каждый раз новую модель узла, но в порядке, обратном прямому ходу . Если у вновь опрашиваемой модели триггер 3 стоит s "0", то в ней ничего не происходит и импульс сдвига на входах 25 не формируется, напротив, описанный выше шаг возврата с проверкой условия (5 ) повторится снова, если триггер 3 у очередной опрашиваемой модели узла стоит в "1". Если на очередном шаге возвращения при проверке условия (5 ) окажется, что оно не выполняется ни для какой модели узла из множества QÊ то это означает, что обратный процесс окончен и мОжно переходить к прямому шагу для формирования нового максимального множества независимых верших в графе. Для этого на входы 29 подается импульс, который через элементы 1! 10, 11 установит в "1" соответственно триггеры 4 и 5 в тех моделях узлов, которые на данном + шаге принадлежат множествам Q< и что необходимо для выполнения ново-, го процесса прямого хода и т.д, Процесс формирования всех максимальных незаивисимых множеств вершин в графе будет завершен когда О+ =ф т.е. просмотрены все вершины графа. В таблице представлен пример работы алгоритма по нахождению максимальных независимых множеств для графа из восьми вершин (фиг.2). Знаком Фотмечены максимальные независимые множества графа G. Использование новых элементов-реверсивных регистров сдвига, дополнительных триггеров, элементов И, и ИЛИ и новых связей позволяет получить существенно новый положительный эффект, т.е. решить важную задачу нахождения всех максимальных независимых множеств в графе.,Анализ этих множеств дает возможность определить одно из важных структур9075 Xik Номер шага 4 5 Q =1,2,3... 0 3,4,5,7 =Ф -o 1,3 Ф 1,3,7 1 3 4,5,7 Ф 1,4 3,4 1,5 1,5,7 1,5 3,4,5 7 I 2,3,4,5,6,7,8 0 4,5,7,8 1 2,4 2,4,8 5,7,8 7,8 2,5 2,5,7 2,5,7,8 2,5,7 ных свойств графа — число независимости, что имеет самостоятельное значение в теории графов, а также имеет разнообразные непосредственные приложения при ведении проектного планирования исследовательских работ, в кластерном анализе, параллельных вычислениях на ЭВИ, при решении задач размещения в системах автоматического проектирования радиоэлектрон- 1в 52 12 ной и электронно-вычислительной аппаратуры. Важной является возможность решения задачи нахождения числа независимости к решению задачи о хроматическом числе графа. Аппаратная реализация метода обеспечивает распараллеливание решения задачи и значительно сокращает время решения. 907552 3 (4 5 (2,5 4,5 1,2 3,6 1,6 3,7 3,7,8 1,8 1,6,7 3,7 4,5,6,7,8 0 1,2,3 6,8 1,2,6 1,2,3,4 5,6,7,8 7,8 1,2 1,2,3,4,5 6,7,8 3,4 7,8 2,3,4,5,7 Р 1,2,3...,8 И, выходы которых соединены соот" ветственно с первым и вторым входами первого элемента ИЛИ, вторые входы первого и второго элементов И подключены соответственно к первому и второму входам модели, о т л ич а ю щ а я с я тем, что, с целью 5 5 5 2 2 3 2 6 5 6 Формула изобретения Модель узла для исследования графа, содержащая первый триггер, единичный выход которого подключен к I входу блока индикации и к первым входам первого и второго элементов 1т 1,2,3,5 1,2, . °,7 14 ПРодолжение таблицы 7,8 3,4,5,6,7,8 0 6,7,8 . 1. Ф 2 7,8 1 90 расширения функциональных возможностей за счет возможности решения задачи нахождения максимальных независимых множеств графа, в нее введены два регистра, триггеры, элементы И и элементы ИЛИ третьи входы первого и второго элементов И подключены к третьему входу модели, входной полюс которой соединен с третьим входом первого элемента ИЛИ с нулевым входом второго триггера, с нулевым входом первого разряда первого регистра, с первым входом третьего элемента И и с первым входом второго элемента ИЛИ, выход которого подключен к нулевому входу первого триггера, единичный вход которого соединен с выходом четвертого элемента И и с единичным входом третьего триггера, выход которого подключен к информационному входу второго регистра, единичный выход первого разряда которого соединен с первым входом четвертого элемента И, с первым выходом модели и с вторым входом третьего элемента 1, выход которого подключен к второ у выходу модели, четвертый вход которой .соединен с вторым входом четвертого элемента И и с первым входом пятого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с информационным входом первого регистра, единичный выход первого разряда которого подключен к второму входу пятого элемента И, к третьему выходу модели и к первому входу шестого элемента И, второй вход которого соединен с пятым входом мо7552 16 дели и с первым входом седьмого элемента И, выход которого подключен к первому входу третьего элемента ИЛИ выход которого соединен с четвертым выходом модели, шестой вход которой подключен к первому, входу восьмого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, выход первого элемента И подклю-! 10 чен к второму входу второго элемента ИЛИ и к единичному входу первого разряда первого регистра, нулевой выход первого разряда которого соединен с вторым входом седьмого эле15 мента И, выход второго элемента И подключен к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И и с единичным входом четвертого 2в триггера, единичный выход которого подключен к второму входу восьмого элемента И, выход первого элемента ИЛИ соединен с нулевым входом третьего триггера и с нулевым входом nep2s вого разряда второго регистра, вход сдвига и вход реверса которого соединены соответственно с входом сдвига и с входом реверса первого регистра и подключены соответственно зв к седьмому и восьмому входу модели, выход четвертого элемента ИЛИ является выходным полюсом модели. Источники информации принятые во внимание при экспертизе 1. Авторское свидетельство СССР N 570060, кл. G 06 6 7/122, 1975, 2. Авторское свидетельство СССР N 363994, кл. G 06 G 7/122, Т970 (прототип). 907552 Составитель А. Яицков Редактор В.Лазаренко Техред А. Ач Корректор Н. Йвыдкая Заказ 592/58 Тираж 732 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Е-35, Раушская наб., д. 4/5 Филиал ППП "Патент", г. Ужгород, ул. Проектная. 4
