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

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

Иллюстрации

Показать все

Реферат

 

Союз Соввтскни

Социалистических

Республик

ОПИСЛНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Опубликовано 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