Учебное пособие 1161

3.Доказать, что если в n-вершинном графе степень каждой вершины не меньше, чем (n-1)/2 , то он связен.

4.Доказать, что если G несвязный граф, то G связ-

ный.

3.2. Независимые множества

Множество вершин называется независимым (внутренне устойчивым множеством), если никакие две из них не смежны. Например, для графа, изображенного на рис. 3, независимыми являются множества вершин: {x7, x8, x2}, {x3, x1}, {x7, x8, x2, x5}.

х1		х2		х3

х8	х6	х4
х7		х5

Рис. 3 Независимое множество называется максимальным, если

нет другого независимого множества, в которое оно бы входило. Для графа, изображенного на рис. 3, множество {x7, x8, x2, x5} является максимальным, а {x7, x8, x2} таковым не является.

Нахождение всех максимальных независимых множеств

Введем необходимые обозначения обоснуем алгоритм нахождения всех максимальных независимых множеств.

В процессе поиска на некотором этапе k независимое множество вершин Sk расширяется путем добавления к нему подходящим образом выбранной вершины (чтобы получилось новое независимое множество Sk+1) на этапе k+1, и так поступают до тех пор, пока добавление вершин станет невозможным, а порожденное множество не станет максимально незави-

20

симым множеством. Пусть Qk будет на этапе k наибольшим множеством вершин, для которого Sk∩Qk= , то есть после добавления любой вершины из Qk в Sk получится независимое множество Sk+1. В некоторый произвольный момент работы алгоритма множество Qk состоит из вершин двух типов: подмножества Qk- тех вершин, которые уже использовались в процессе поиска для расширения множества Sk, и подмножества Qk+ таких вершин, которые еще не использовались. Тогда дальнейшее ветвление в дереве поиска включает процедуру выбора вершины xik Qk+, добавления ее к Sk

Sk+1 = Sk {xik}

и порождения новых множеств:

Qk-+1 = Qk- \ Г(xik);

Qk++1 = Qk+ \ (Г(xik) {xik}).

Шаг возвращения алгоритма состоит в удалении вершины xik из Sk+1, чтобы вернуться к Sk, изъятии xik из старого множества Qk+ и добавлении xik к старому множеству Qk- для формирования новых множеств Qk- и Qk+.

Множество Sk является максимально независимым множеством только тогда, когда невозможно его дальнейшее расширение, то есть когда Qk+= . Если Qk- , то текущее множество Sk было расширено на некотором предшествующем этапе работы алгоритма путем добавления вершины из Qk-, и поэтому не является максимальным независимым множеством. Таким образом, необходимым и достаточным условием того, что Sk максимально независимое множество, является выполнение равенств:

Qk+ = Qk- = .

Если очередной этап работы алгоритма наступает тогда, когда существует некоторая вершина x Qk-, для которой Г(x) Qk+= , то безразлично, какая из вершин, принадлежащих Qk+, использовалась для расширения Sk, и это справедливо при любом числе дальнейших ветвлений. Вершина x не может быть

21

удалена из Qp- на любом следующем шаге p > k. Таким обра-
зом, существование x, такого что
х Qk-	и Г(x) Qk+ =	(1)
является достаточным для применения шага возвращения, по-
тому что из Sk при всяком дальнейшем ветвлении уже не полу-
чится максимально независимое множество.
Если k=0, то возвращение выполнить невозможно, по-
этому при k=0 осуществляется переход на прямой шаг.
Опишем алгоритм нахождения всех максимальных неза-
висимых множеств вершин графа.
Начальная установка.
Шаг 1. Пусть S0 = Q0- = , Q0+= X, k=0.
Прямой шаг.
Шаг 2. Выбрать вершину xik Qk+ и сформировать Sk+1,
Qk-+1 и Qk++1, оставив Qk- и Qk+ нетронутыми. Положить k=k+1.
Проверка.
Шаг 3. Если выполняется условие (1), то перейти к шагу
5 иначе к шагу 4.
Шаг 4. Если Qk+=Qk- = , то напечатать максимальное не-
зависимое множество Sk и перейти к шагу 5. Если Qk+= , а
Qk- , то перейти к шагу 5, иначе к шагу 2.
Шаг возвращения.
Шаг 5. Положить k=k–1. Удалить xik из Sk+1, чтобы полу-
чить Sk. Исправить Qk+ и Qk-, удалив вершину xik из Qk+		и доба-
вив ее к Qk-. Если k 0, то перейти к шагу 3, иначе если		Q0+= ,
то остановиться (к этому моменту будут напечатаны все мак-
симальные независимые множества), иначе перейти к шагу 2.
Задача. Найти все максимальные независимые множест-
ва графа G.	x1

x2		x3
x4		x5
x6	22	x7

Матрица смежности графа G:

		x1	x2	x3	x4	x5	x6	x7
	x1	0	1	1	0	0	0	0
	x2	1	0	0	1	0	1	0
А=	x3	1	0	0	0	1	0	1
	x4	0	1	0	0	1	1	0
	x5	0	0	1	1	0	0	1
	x6	0	1	0	1	0	0	1
	x7	0	0	1	0	1	1	0

1.Начальная установка:

S0 = Ø; Q0- = Ø; Q0+ = {x1, x2, x3, x4, x5, x6, x7}; k=0.

2.Прямой шаг:

x1; S1 = {x1}; Q1- = Ø; Q1+ = {x4, x5, x6, x7}; k = 1. 3. Проверка.

Условие не выполняется, переходим к шагу 4 (→ 4). 4. Условие не выполняется → 2.

2.x4; S2 = {x1, x4}; Q2- = Ø; Q2+ = {x7}; k = 2.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x7; S3 = {x1, x4, x7}; Q3- = Ø; Q3+ = Ø; k = 3.

3.Условие не выполняется → 4.

4.S3 = {x1, x4, x7} максимальное независимое множество → 5.

5.k = 2; S2 = {x1, x4}; Q2- = {x7}; Q2+ = Ø → 3.

3. Условие выполняется → 5.

5. k = 1; S1 = {x1}; Q1- = {x4}; Q1+ = {x5, x6, x7} → 3.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x5; S2 = {x1, x5}; Q2- = Ø; Q2+ = {x6}; k = 2.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x6; S3 = {x1, x5, x6}; Q3- = Ø; Q3+ = Ø; k = 3.

3.Условие не выполняется → 4.

23

4.S3 = {x1, x5, x6} максимальное независимое множество → 5.

5.k = 2; S2 = {x1, x5}; Q2- = {x6}; Q2+ = Ø → 3.

3. Условие выполняется → 5.

5. k = 1; S1 = {x1}; Q1- = {x4, x5}; Q1+ = {x6, x7} → 3.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x6; S2 = {x1, x6}; Q2- = {x5}; Q2+ = Ø; k = 2.

3.Условие выполняется → 5.

5. k = 1; S1 = {x1}; Q1- = {x4, x5, x6}; Q1+ = {x7} → 3. 3. Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1}; Q0+ = {x2, x3, x4, x5, x6, x7} → 2.

2.x2; S1 = {x2}; Q1- = Ø; Q1+ = {x3, x5, x7}; k = 1.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x3; S2 = {x2, x3}; Q2- = Ø; Q2+ = Ø; k = 2.

3.Условие не выполняется → 4.

4.S2 = {x2, x3} — максимальное независимое множество → 5.

5.k = 1; S1 = {x2}; Q1- = {x3}; Q1+ = {x5, x7} → 3.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x5; S2 = {x2, x5}; Q2- = Ø; Q2+ = Ø; k = 2.

3.Условие не выполняется → 4.

4.S2 = {x2, x5} — максимальное независимое множество → 5.

5.k = 1; S1 = {x2}; Q1- = {x3, x5}; Q1+ = {x7} → 3.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x7; S2 = {x2, x7}; Q2- = Ø; Q2+ = Ø; k = 2.

3.Условие не выполняется → 4.

4.S2 = {x2, x7} — максимальное независимое множество → 5.

5.k = 1; S1 = {x2}; Q1- = {x3, x5, x7}; Q1+ = Ø → 3.

3. Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1, x2}; Q0+ = {x3, x4, x5, x6, x7} → 3.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

24

2.x3; S1 = {x3}; Q1- = {x2}; Q1+ = {x4, x6}; k = 1.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x4; S2 = {x3, x4}; Q2- = Ø; Q2+ = Ø; k = 2.

3.Условие не выполняется → 4.

4.S2 = {x3, x4} — максимальное независимое множество → 5.

5.k = 1; S1 = {x3}; Q1- = {x2, x4}; Q1+ = {x6} → 3.

3.Условие не выполняется → 4.

4.Условие не выполняется → 2.

2.x6; S2 = {x3, x6}; Q2- = Ø; Q2+ = Ø; k = 2.

3.Условие не выполняется → 4.

4.S2 = {x3, x6} — максимальное независимое множество → 5.

5.k = 1; S1 = {x3}; Q1- = {x2, x4, x6}; Q1+ = Ø → 3.

3. Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1, x2, x3}; Q0+ = {x4, x5, x6, x7} → 2.

2.x4; S1 = {x4}; Q1- = {x1, x3}; Q1+ = {x7}; k = 1.

3.Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1, x2, x3, x4}; Q0+ = {x5, x6, x7} → 2.

2.x5; S1 = {x5}; Q1- = {x1, x2}; Q1+ = {x6}; k = 1.

3.Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1, x2, x3, x4, x5}; Q0+ = {x6, x7} → 2.

2.x6; S1 = {x6}; Q1- = {x1, x3, x5}; Q1+ = Ø; k = 1.

3.Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1, x2, x3, x4, x5, x6}; Q0+ = {x7} → 2.

2.x7; S1 = {x7}; Q1- = {x1, x2, x4}; Q1+ = Ø; k = 1.

3.Условие выполняется → 5.

5. k = 0; S0 = Ø; Q0- = {x1, x2, x3, x4, x5, x6, x7}; Q0+ = Ø → останов.

Таким образом, данный граф имеет семь максимальных независимых множеств:

S1 = {x1, x4, x7}; S2 = {x1, x5, x6}; S3 = {x2, x3}; S4 = {x2, x5}; S5 = {x2, x7}; S6 = {x3, x4}; S7 = {x3, x6}.

Задачи и упражнения

1. Найти все максимальные независимые множества гра-

фа

25

а)

б)

д)

е)

4. АЛГЕБРА ЛОГИКИ

Теоретические сведения

Для любой ПФ имеет место равносильность

F(X1,X2,...,Xn ) X1 F(1, X2,...,Xn ) X1 F(0, X2,...,Xn ),

называемая дизъюнктивным разложением по переменной Х1.

Пример. Для ПФ X1 X2 X3 определить дизъюнк-

тивное разложение по переменной Х1.

X1 X2 X3 X1 (1 X2 X3) X1 (0 X2 X3)

X1 X2 X3 X1.

Для любой ПФ F(X1,X2,...,Xn) и любого натурального k

имеет место равносильность

F(X

, X

2

,...,X

n

)

Xv1

Xv2

... Xvk

1

(v ,v

,...,v

) 1

2

k

1 2

k

F(v1,...,vk, Xk 1,...,Xn),

F(X1,X2,...,Xn)

называемая дизъюнктивным

разложением

по переменным X1,X2,...,Xn .

Для любой ПФ имеет место равносильность

F(X1,X2,...,Xn) (X1 F(0,X2,...,Xn)) (X1 F(1,X2,...,Xn))

называемая конъюнктивным разложением по переменной Х1.

26

Пример. Для ПФ определить конъюнктивное разложение по переменной Х1.

X1 X2 X3 (X1 (0 X2 X3)) (X1(1 X2 X3) X1 (X2 X3))

Для любой ПФ F(X1,X2,...,Xn) и любого натурального k

имеет место равносильность

F(X	, X	2	,...,X	n	)			)	(Xv1	Xv2	... Xvk
1						(v ,v	,...,v		1	2	k
						1 2	k

F(v1,...,vk, Xk 1,...,Xn)),

называемая конъюнктивным разложением F(X1,X2,...,Xn) по переменным X1,X2,...,Xn .

Определим некоторые канонические представления ПФ.

ПФ называется элементарной конъюнкцией (дизъюнкци-

ей), если она является конъюнкцией (дизъюнкцией) переменных и отрицаний переменных.

Пример. X Y Z - элементарная конъюнкция.

X Z - элементарная дизъюнкция.

Говорят, что ПФ задана в дизъюнктивной нормальной форме (ДНФ), если она является дизъюнкцией элементарных конъюнкций.

Пример. X Y Z X Y Y Z - ДНФ.

Говорят, что ПФ задана в конъюнктивной нормальной форме (КНФ), если она является конъюнкцией элементарных дизъюнкций.

Пример. (X Y Z) (X Y) - КНФ.

Алгоритм 1

(приведение ПФ к нормальной форме)

1. Если ПФ содержит операции → и ↔, то их исключают с помощью равносильностей

X Y X Y , X Y (X Y) (X Y).

27

2.Приводят отрицания к независимым переменным, используя законы де Моргана.

3.Раскрывают скобки по дистрибутивному закону конъюнкции относительно дизъюнкции для приведения к ДНФ или по дистрибутивному закону дизъюнкции относительно конъюнкции для приведения к КНФ.

Пример. Определить нормальные формы для ПФ

(X Y) Z .

Действуя, в соответствии с алгоритмом 1, получим

(X Y) Z X Y Z X Y Z ДНФ.

Применяя к полученной ДНФ дистрибутивный закон дизъюнкции относительно конъюнкции, получим

Замечание. Для данной ПФ существует множество ДНФ

(X Y ) Z (X Z) (Y Z) КНФ

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

Совершенной дизъюнктивной нормальной формой

(СДНФ) данной ПФ называется ДНФ, в которой каждая элементарная конъюнкция содержит все переменные – без отрицания или с отрицанием, но не вместе.

Совершенной конъюнктивной нормальной формой

(СКНФ) данной ПФ называется КНФ, в которой каждая элементарная дизъюнкция содержит все переменные – без отрицания или с отрицанием, но не вместе.

Существует два способа перехода к совершенным формам табличный и аналитический [2, 3, 4].

Алгоритм 2 (аналитический способ приведения к СДНФ)

1.С помощью равносильных преобразований привести ПФ к ДНФ.

2.Те элементарные конъюнкции, в которые сомножителями входят не все переменные, умножить на единицы, пред-

28

ставленные в виде дизъюнкций каждой недостающей переменной с ее отрицанием.

3.Раскрыть скобки по соответствующему дистрибутивному закону.

4.Для получения искомой СДНФ исключить повторе-

ния.

Приведение к СКНФ осуществляется аналогично, но только к элементарным дизъюнкциям, содержащим слагаемыми не все переменные, прибавляют нули, представленные в виде конъюнкций каждой недостающей переменной с ее отрицанием.

Пример. Пусть ПФ, содержащая переменные X, Y, Z,

имеет ДНФ вида X Z Y Z .

Заметим, что в первую элементарную конъюнкцию не входит переменная Y, а во вторую – переменная Х. В соответствии с процедурой приведения к СНДФ первую элементар-

ную конъюнкцию умножим на 1 Y Y , а вторую – на

X Z Y Z X Z (Y Y ) Y Z (X X)

1 X X . Получим

X Z Y X Z Y Y Z X Y Z X

X Z Y X Z Y Y Z X СДНФ

Алгоритм 3 (табличный способ приведения к СДНФ)

1.Составляется таблица истинности данной ПФ.

2.Рассматриваются те строки, в которых формула принимает истинностное значение 1. Каждой такой строке ставится в соответствие элементарная конъюнкция, причем переменная, принимающая значение 1, входит в нее без отрицания, а 0

–с отрицанием.

3.Образуется дизъюнкция всех полученных элементарных конъюнкций, которая и составляет СДНФ.

29