Модель узла для исследования графа Советский патент 1982 года по МПК G06F15/173 

( МОДЕЛЬ УЗЛА ИССЛЕДОВАНИЯ ГРАФА

I

Изобретение относится к электронному моделированию задач теории графов и может быть использовано при построении специализированных цифровых вычислительных устройств для исследования графов, в частности для решения задачи нахождения всех максимальных независимых множеств в графе.

Известно устройство для моделирования сетевого графика, содержащее блок управления, блок регистрации, блок стоимостноресурсных ограничителей , блоки коммутации и блоки моделей ветвей, состоящие из счетчиков, триггеров, элементов И и схем индикации 1 .

Однако это устройство не решает задачу о нахождении максимальных независимых множеств в графе.

Наиболее близким по технической сущности к предлагаемому является устройство для моделирования ветви графа, содержащее триггер, который

единичным выходом связан с блоком . индикации и с первыми входами первого и второго элементов И, вторые входы которых связаны с первым и вто рым полюсами, а выходы первого и второго элементов И соединены с первым и вторым вводами первого элемента ИЛИ 2.

Однако известное устройства также не обеспечивает решение задачи

10 о максимальном независимом множестве графа.

Цель изобретения - расширение функциональных возможностей за счет возможности решения задачи нахожде15ния максимальных независимых множеств графа.

Поставленная цель достигается тем, что в модель узла для исследования графа, содержащую первый триггер,

20 единичный выход которого подключен к входу блока индикации и к первым входам первого и второго элементов И, выходы которых соединены СООТВРТственно с первым и вторым входами первого элемента ИЛИ, вторые входы первого и второго элементов И подклю чены соответственно к первому и второму входам модели, введены два регистра, триггеры, элементы И и элементы ИЛИ, третьи входы первого и второго элементов И подключены к третьему входу модели, входной полюс которой соединен с третьим входом первого элемента ИЛИ, с нулевым входом второго триггера, с нулевым входом первого разряда первого регистра, с первым входом третьего элемента И и с первым входом второго элемента ИЛИ, выход которого подключен к нулевому входу первого триггера, единичный вход которого соединен с выходом четвертого элемента И и с единичным входом третьего триггера, выход которого подключен к информационному входу второго регистра, единичный выход первого разряда которо -о соединен с первым входом четвертого элемента И, с первым выходом модели и с вторым входом третьего элемента И, выход которого подключен к второму выходу модели, четвертый вход которой соединен с вторым входо четвертого элемента И и с первым входом пятого элемента И, выход которого подключен к единичному входу ВТ

рого триггера, единичный выход которого соединен с информационным входом первого регистра, единичный выход первого разряда которого подключен к второму входу пятого элемента И, к третьему выходу модели и к первому входу шестого элемента И, второ вход которого соединен с пятым входом модели и с первым входом седьмого элемента И, выход которого подключен к первому входу третьего элемента ИЛИ, выход которого соединен с четвертым выходом модели, шестой вход которой подключен к первому входу восьмого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ, выход первого элемента И подключен к второму входу второго элемента ИЛИ и к единичному входу первого разряда первого регистра, нулевой выход первого разряда которого соединен с вторым входрм седьмого элемента И, выход второго элемента И подключен к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И и с единичным входом четвертого триггера, единичный выход которого подключен к второму входу восьмого элемента И, выход первого элемента ИЛИ соединен с нулевым входом 5 третьего триггера и с нулевым входом первого разряда второго регистра, вход сдвига и вход реверса которого соединены соответственно с входом сдвига и входом реверса первого регистра и подключены соответственно к седьмому и восьмому входу модели выход четвертого элемента ИЛИ является выходным полюсом модели.

На фиг. изображена структурная.

5 схема модели узла; на фиг. 2 - пример графа, где точками I-VIII обозначены его вершины.

Модель узла содержит регистры 1 и 2 .(Триггеры 3-6, элементы И 7-1, элементы ИЛИ 15-18, блок 19 индикации, входной полюс 20, выходной полюс 21 и входы и 22-23. Регистры 12 реализованы по Схеме реверсивного регистра сдвига, направление сдвига

5 которого зависит от уровня сигнала

реверса на входе 26. I

Решение задачи о нахождении всех

максимальных независимых множеств графа реализуется в предлагаемой

0 модели по спедующему методу.

Пусть дан неориентированный граф G(X,r), где X - вершины; Г -ребра. Независимое множество вершин - это множество вершин графа G такое, что

5 любые две вершины в нем не смежны, т.е. никакая пара вершины не соединена ребром, т.е. любое множество S С л, которое удовлетворяет условие Snr(S) Ф r{S) - множество вершин, составляющее отображение вершин из множества (S, Ф - пустое множество) , является независимым множеством вершин. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило, т.е. множест во S является максимальным независимым множеством, если оно удовлетворяет условиям 50Г{5) Ф, НОГ(Н)ф

0 VHOS (для всех И, включающих множество S),.

Если Q есть семейство всех независимых множество графа G, то число maxisl

seQ

5 называется числом Нзависимости гра

фа G, а множество S , на котором этот максимум достигается, называется наибольшим независимым множеством. Известен метод отыскания максима ных независимых множеств, который я ляестя существенно упрощенным перебором, использующим дерево поиска: Шаг. 1-Пусть $0 Ci., k-0. Прямой ход Шаг 2. Выбрать вершину Чк € Q) и сформировать 5|, к. остав и Q без изменени |. Положить ляя .. . .Шаг 3- Если удовлетворяется условие 3 хв Q такое, что Г().)О Q. ф, то перейти к шагу 5, иначе к шагу 4. Шаг k. Если Ц .: Ф , то значит ма симальное независимое множество S Сформировано и следует перейти к шагу 5. Если Q. ф, л , то перей ти к шагу 5. Иначе п.-.рейти к шагу 2 Обратный ход Шаг 5- Положить . Удалить х из ) чтобы получить TV. Испра- вить (1 и Ц. , удалив вершину из Q иДобавив ее к 0.. Если , 1с ° перейти к шагу 2, если , 1 Ф , то остановиться, так как к этому моменту найдены все мак-симальные независимые множества. Ин че перейти к шагу 3. С целью упрощения модели узла, аппаратно реализующей приведенный метод, принимаем Sj., где X - множество вершин графа. Тогда на каждом шаге S ц-. S к - r(xi 1) , а не SK., Множества . -it+t определяются h формулам u,7,. о.к -г (xik) Qt ( ) Если модель узла принадлежит одному из множеств Q или 0 , то соответственно входной триггер (первый разряд регистра 1 или .) находится в единичном состоянии. Множество моделей узлов, у которых указанные три|- гера находятся в единице, образуют соответственно множества К - Принадле ; ность модели узла максимальному независимому множеству узлов графа определяется единичным состоянием триггера 3 которое индицируется с помощью блока 19 индикации Выходы триггеров А и 5 связаны с информационными входами регистров 1 и Z, т.е. в регистры заносится информация о состоянии этих триггеров на каждом цикле сдвига. Модель узла для исследования графа при решении задачи нахождения максимальных независимых множеств графа работает следующим образом. Предварительно полюса 20 и 21 всех моделей узлов соединяются между собой в соответствии с топологией исследуемого графа. Выходы 22 и входы 23 всех моделей узлов соединены таким образом, что образуется последовательная цепь у которой входным полюсом является вход 23 первой в цепи модели узла, а выходным - выход 22 последней. В первый разряд регистра 2 всех моделей узлов записывается 1, что соответствует выражению Q. Х, где X - множество узлов грайа, а в первый разряд регистра 1 записывается О, т.е. 0. ф, где ф - пустое множество. Остальные разряды регистров 1 и 2 всех моделей узлов находятся в О. Триггеры 3 и 5 предварительно устанавливаются в а триггеры ,6 - в О во всех моделях узлов. В исходном состоянии на входы 26 и 31 подается разрешающийпотенциал (признак прямого хода), а на входы 33 - запрещающий. На входы 25 подается импульс сдвига для запоминания исходных множеств QQ и Q, при этом информация сдвигается на один разряд вправо, а входные триггеры регистров 1 и 2 принимают информацию с триггеров и 5. Для решения задачи о максимальном независимом множестве графа модели узлов последовательно просматриваются в произвольно заданном порядке (прямой ход. Для этого подается опрашивающий сигнал на вход 32, чем осуществляется выбор той или иной модели узла. Наличие единичного сигнала на выходе триггера 3 и разрешающего потенциала на входе 31 обеспечивает прохождение в выбранной модели узла опрашивающего сигнала с входа 31 через элемент И8 и через элемент ИЛИ 15 на нулевые входы триггера 5 и первого триггера регистра 2 для записи О в первый его разряд. Сброс триггера 5 в О означает, что при последующих сдвигах регистра 2 на прямом ходе в него на каждом шаге будет записываться О. Одновременно с этим выходной сигнал элемента И 8 через элемент ИЛИ 17 поступает на выходной полюс 21 и далее (с учетом связей моделей узлов в соответствии с топологией исследуемого ) , на входной полюс 20 тех моделей узлов, которые инцидентны данному. В этих моделях сигнал поступит на нулевые входы регистра и триггера . В первом этот сигнал подтвердит нулевое исходное состояние его первого разряда, а триггер k имеет аналогичное с триггером 5 назначение. Сигнал с полюса 20 через элемент ИЛИ 16 сбросит в О триггер 3, а через элемент ИЛИ 13 устано вит в О триггер первого разряда регистра 2 и триггер 5. В результате записи О в регистр 2 выбранной опрашивающим сигна лом модели узла и всех моделей узлов с ней связа.нных сформируется новое Qj/ , в соответствии с выражением (xik) и xikj, (1) О + - Г -tc+1 к i миглш ti I т а п Р. / п га - из исходного множества лены выбраннь1й узел и узлы ему инцидентные по топологии исследуемого графа. Установив в О триггеров 3 в моделях узлов, связанных с выбранной соответствует выражению S (xik) Поступление сигнала на О вход регистра 1 соотгзетствует действию по формуле ;ti r(xik) (3) Таким образом, множества 7(+, к+С toK этого требует первый шаг алгоритма, сформированы. Вновь сформированные Q. и . необходимо Запомнить , для этого на входы 25 всех моделей узлов подается импульс сдвига, который формируется по сигналу с выходного полюса 21. HaпpaвлeниJ сдвига, который формируется по сигналу с выходного полгоса 21. Напрааление сдвига определяет ся уровнем (1 или О ) сигнала реверса на входах 26. Следующий опрашивающий сигнал на входе 32 выбирает новую модель узла Если в ней триггер 3 стоит в 1, . то описанный выше процесс повторяется. Если триггер 3 был ранее сброшен в О сигналом с полюса 20 от предыдущих опрашиваемых моделей узлов, то в ней на этом шаге опроса ничего не изменится и импульс сдвига регист ров на входах 25 не формируется. Опрос моделей узлов продолжается до тех пор, пока на очередном шаге окажется, что на выходах 2 и 27 всех моделей узлов сформированы нулевые сигналы, т.е. .7 Ф (k) Это означает, что первое максимальное независимое множество сформировано и состоит из моделей узлое, у которых триггеры 3 сохранили единичное состояние, которое индицируется с помощью блока 19 индикации. После этого начинается обратный процесс. Для этого предварительно на входы 26 моделей узлов подается сигнал, соответствующий обратному направлению сдвига регистров ( реверс, а на входы 25 - импульс сдвига, который устанавливает на .выходе регистров информацию, полученную на предыдущем шаге, т-.е. первые разряды регистров 1 будут выдавать данные о принадлежности моделей узлов множеству 0.,, а первые разряды регистров 2 - мно)еству входов 31 снимается, а на входы 33 подается разрешаюидий сигнал (признак обратного хода). Начиная с последней опрошенной модели узла, на которой был остановлен прямой ход решения,на входе 32 вновь последовательно для всех моделей узлов поступают опрашивающие сигналь,но в порядке, обратном прямому ходу. Триггер 3 последней опрошенной на прямом ходе модели узла сохранил 1 состояние, поэтому импульс опроса с входа 32 через элемент 7 И подается на единичный вход первого триггера регистра 1, устанавливая его в 1, через элемент 15 ИЛИ на нулевые входы триггера и триггера первого разряда регистра 2; через элемент ИЛИ 1б ,на нулевой вход триггера. Поступление сигналов на 1 вход регистра 1 и О вход регистра 2 и триггера 3 соответствует тому, что опрашиваемая модель узла вычеркивается из множеств S., добавляется к множеству , как это и требуется на шаге возвращения алгоритма. Далее следует проверка условия Эхе G, такая, что Г(х), , .. т.е. существует ли хотя бы одна модель узла, принадлежащая множеству I , отображение которой (множество , связанных с ней ) и множество моделей узлов, составляющих Q(, , не пересекаются, т.е. у них нет общих элементов. Проверка осуществляется следующим образом. На вход 23 первой в цепочке модел узла подается импульс проверки условия (5). Этот импульс поступает на первый вход элемента И 13, вторым входом которого управляет нулевой выход первого триггера регистра 1. Если множество Q пусто, то импульс проверки условия (5 ) беспрепят ственно проходит через элементы И 13 и ИЛИ 18 во всех моделях узлов и появляется на выходе 22 последней в цепи модели узла. Если Qj не пусто, т.е. есть хотя бы одна модель узла, у которой в регистре 1 первый три|- гер находится на данном шаге в 1, то в этой модели узла импульс проверки условия С) проходит не через элемент И 13, г через элемент И 12, устанавливая триггер 6 в единичное состояние, и далее через элемент ИЛИ 17 поступает на выходной полюс 2 Как упоминалось Bbiuje, с полюса 21 сигнал поступит на полоса 20 тех моделей узлов, которые связаны с данной в соответствии с топологией графа. С полюса 20 сигнал поступит в этих моделях узлов на один из входов элемента И 9, второй вход которого управляется единичным выходом тригге ра первого разряда регистра 2, хранящего информацию о принадлежности данной модели узла множеству Q.J,. На выходе элемента И 9 и на выходе 28 сигнал появится в том случае, если данная модель узла одновременно принадлежит множеству Г(х) и Q| Если это произойдет хотя бы в одной модели узла, то условие (5) для модели узла, принадлежащей lнoжecтвy QK. У первый триггер регистра 1 находится в 1 состоянии), не выполняется. Следовательно, проверку условия 5 ) необходимо продолжить дл других моделей узлов, входящих в QU. Для этого на входы 30 всех моделе узлов подается импульс, который проходит через элемент И 1 в той из них, у которой триггер 6 находится в 1 состоянии, и через элемент ИЛИ 1 появляется на выходном полюсе 22, Таким образом, наличие сигнала на выходе 28 хотя бы у одной модели узла в момент проверки условия (5) говори о том, что это условие не выполняетс и необходимо продолжить проверку. На против, если такой сигнал не сформировался ни у.одной из моделей узлов в момент проверки, то это означает, что условие (3) выполнено хотя бы для одной модели узла и дальнейшая проверка не нужна, что является сигналом для перехода к шагу возврата алгоритма. Итак, если условие СЗ) выполнено то на входы 25 всех моделей узлов вновь поступает импульс сдвига, формируя новые QI , 0.,Т , а на входы 32 продолжают последовательно подаваться опрашивающие импульсы, выбирая каждый раз новую модель узла, но в порядке, обратном прямому ходу.. Если у вновь опрашиваемой модели триггер 3 стоит в 0 то в ней ничего не происходит и импульс сдвига на входах 25 не формируется, напротив, описанный выше шаг возврата с проверкой условия (5) повторится снова, если триггер 3 У очередной опрашиваемой модели узла стоит в 1. Если на очередном шаге возвращения при проверке условия (5) окажется, что оно не выполняется ни для какой модели узла из множества Q),;, то это означает, что обратный процесс окончен и можно переходить к прямому шагу ДЛЯ формирования нового максимального множества независимых верших в графе. Для этого на входы 29 подается импульс, который через элеi 1 менты И 10, 11 установит соответственно триггеры k моделях узлов, которые на данном шаге принадлежат множествамQ и i, что необходимо для выполнения ново-. го процесса прямого хода и т.д. Процесс формирования всех максимальных незаивисимых множеств вер-, шин в графе будет завершен когда Q- Ф т.е. просмотрены все вершины графа. В таблице представлен пример работы алгоритма по нахождению максимальных независимых множеств для графа из восьми вершин (фиг.2). Знаком -Х-отмечены максимальные независимые множества графа G. Использование новых элементов-реверсивных регистров сдвига, дополнительных триггеров, элементов И, и ИЛИ и новых связей позволяет получить существенно новый положительный эффект, т.е. решить важную задачу нахождения всех максимальных независимых множеств в графе..Анализ этих множеств дает возможность определить одно из важных структурV90755212

ных свойств графа - число независи- ной и электронно-вычислительной аппамости, что имеет самостоятельное зна- ратуры.

чение в теории графов , а также имеет Важной является возможность решеразнообразные непосредственные При- ния задачи нахождения числа незавиложения при ведении проектного пла- 5 симости к решению задачи о хроматичеснирования исследовательских работ, ком числе графа.

в кластерном анализе, параллельных вычислениях на ЭВМ, при решении задач размещения в системах автоматического проектирования радиоэлектрон-ю решения.

Аппаратная реализация метода обеспечивает распараллеливание решения задачи и значительно сокращает время

Формула изобретения

Модель узла для исследования графа, содержащая первый триггер, единичный выход которого подключен к 1входу блока индикации и к первым входам первого и второго элементов

И, выходы которых соединены соответственно с первым и вторым входами первого элемента ИЛИ, вторые входы первого и второго элементов И подключены соответственно к первому и второму входам модели, отличающаяся тем, что, с целью

расширения функциональных возможностей за счет возможности решения задачи нахождения максимальных независимых множеств графа, в нее введены два регистра, триггеры, элементы И и элементы ИЛИ третьи входы первог и второго элементов И подключены к Третьему входу модели, входной полюс которой соединен с третьим входом первого элемента ИЛИ с нулевым входом второго триггера, с нулевым входом первого разряда первого регистра с первым входом третьего элемента И и с первым входом второго элемента ИЛИ, выход которого подключен к нулевому входу первого триггера, единичный вход которого соединен с выходом четвертого элемента И и с единичным входом третьего триггера, выход которого подключен к информацион-20

ному входу второго регистра, единичный выход первого разряда которого соединен с первым входом четвертого элемента И, с первым выходом модели и с вторым входом третьего элемента И, выход которого подключен к второиу выходу модели, четвертый вход которой .соединен с вторым входом четвертого элемента И и с первым входом пятого элемента И, выход которого подключен к единичному входу второго триггера, единичный выход которого соединен с информационным входом первого регистра, единичный выход первого разряда которого подключен к второму входу пятого элемента И, к третьему выходу модели и к первому входу шестого элемента И, второй вхо которого соединен с пятым входом модели и с первым входом седьмого элемента И, выход которого подключен к первому входу третьего элемента ИЛИ выход которого соединен с четвертым

выходом модели, шестой вход которой подключен к первому .входу восьмого элемента И, выход которого соединен с вторым входом третьего элемента ИЛИ,выход первого элемента И подключен к второму входу второго элемента ИЛИ и к единичному входу первого разряда первого регистра, нулевой выход первого разряда которого соединен с вторым входом седьмого элемента И, выход второго элемента И подключен к первому входу четвертого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И и с единичным входом четвертого

подключен к второму входу восьмого элемента И, выход первого элемента ИЛИ соединен с нулевым входом третьго триггера и с нулевым входом первого разряда второго регистра, вход сдвига и вход реверса которого соединены соответственно с входом сдвига и с входом реверса первого регистра и подключены соответственно к седьмому и восьмому входу модели, выход четвертого элемента ИЛИ является выходным полюсом модели. Источники информации принятые во внимание при экспертизе

о

«44

О

гъ См .- г to

т

I::