отображение вершин, входящих в это множество

Если множество S внутренне устойчиво, то для произвольной пары вершин из этого множества <x_i, x_j>, если і ≠ j, отображение S не должно пересекаться с S. Действительно, если вершина x_i является отображением x_j, или есть дуга, которая выходит из x_i и входит в x_j, то одна из вершин, x_i или x_j, не должна принадлежать S:

(1)

Это – формулировка внутренней устойчивости вершин графа.

Для того, чтобы произвольные вершины x_k, x_p принадлежали внутренне устойчивому множеству вершин графа S, должно выполняться:

(2)

Возьмем конъюнкцию левых и правых частей выражений (1) и (2)

(3)

Геометрический смысл выражения (3):

							=
=

В выражении (3)перебираются всевозможные способы исключения вершин x_i, x_j, x_k, x_p из множества S так, чтобы оно было внутренне устойчивым.

Тогда можно составить следующий алгоритм:

Алгоритм поиска всех максимальных внутренне устойчивых множеств:

1. Для каждой пары (x_i, x_j) графа выписывается выражение (1).

2. Берется конъюнкция всех полученных выражений (для всех пар), раскрываются скобки, и производится поглощение ().

3. В полученной записи для каждой конъюнкции выписываются все вершины графа, которые в нее (конъюнкцию) не вошли. Они и образуют максимальные внутренне устойчивые множества вершин графа.

На практике выражение (1) используют в более формализованном виде:

Тогда выражение (1) будет иметь вид:

Добавим конъюнкции слева и справа . Получим:

Для всех вершин графа

Пример. Дана матрица смежности графа.

R=

Запишем выражение (1) для всех вершин графа (для всех пар):

v v ∙ =1 Þ v =1

v v ∙ =1 Þ v v 1=1 Þ 1≡1, т.е. эта строка нам далее не нужна

v v ∙ =1 Þ v =1

v v ∙ =1 Þ v =1

v v ∙ =1 Þ v =1

v v ∙ =1 Þ v v 1=1 Þ 1≡1, т.е. эта строка нам далее не нужна

v v ∙ =1 Þ v =1

v v ∙ =1 Þ v v 1=1 Þ 1≡1, т.е. эта строка нам далее не нужна

v v ∙ =1 Þ v =1

v v ∙ =1 Þ v =1

( v )( v )( v )( v )( v )( v )( v ) = 1

( v )( v )( v ) = 1

( v )( v v v ) =1

v v v v v =

Процесс определения внутренне устойчивых множеств можно формализовать – вместо будем пользоваться только индексом i

Формальное использование метода Магу:

1. Взять i -ую строку матрицы смежности и записать для нее выражение

, где ;

соответствуют номерам столбцов матрицы, содержащим на пересечении со строкой i единицы.

2. Операцию (п.1) провести для всех строк.

3. Выполнить конъюнкцию полученных выражений и упростить.

4. В итоговом выражении для каждой конъюнкции выписать не вошедшие в нее индексы.

5. Сформировать соответствующие внутренне устойчивые множества и определить число внутренней устойчивости графа .

ПРИМЕЧАНИЯ: А. Петли игнорируются!!!

Б. Пустые строки не учитываются!!!

Для этой же матрицы смежности (R)

()

Результат тот же

Метод Магу определения числа внешней устойчивости графа.

Внешне устойчивое множество Т – это такое множество вершин графа G, что в каждую вершину x_i графа, не принадлежащую Т, заходит дуга, исходящая из вершины множества Т:

Х – множество всех вершин графа.

Для всех вершин графа выполняется:

Другими словами, любая вершина x_i либо принадлежит внешне устойчивому множеству Т, либо для нее всегда найдется вершина из множества Т, из которой исходит дуга, заходящая в данную вершину x_i.

На основании выше изложенного запишем:

Формула (1) показывает все возможные варианты положения вершины x_i относительно внешне устойчивого множества Т.

Для вершины x_k из множества Т:

(2)

Выполним конъюнкцию левых и правых частей выражений (1) и (2):

(*)

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

Соотношение (1) запишем более формально, приняв новые обозначения:
;
Значит, ,

Получим
(1)

В общем виде: - основное соотношение.

(* *)

После раскрытия скобок в последнем выражении (* *) и проведения операции поглощения () получим дизъюнкцию конъюнкций. В каждой конъюнкции перечисляются все вершины графа, образующие минимальные внешне устойчивые множества. Сколько конъюнкций, столько и множеств.

Пример: Дана матрица смежности графа

R=

x₁ v x₁ α₁₁ v x₂ α₂₁ v x₃ α₃₁ v x₄ α₄₁ v x₅ α₅₁ = 1

x₂ v x₁ α₁₂ v x₂ α₂₂ v x₃ α₃₂ v x₄ α₄₂ v x₅ α₅₂ = 1

x₃ v x₁ α₁₃ v x₂ α₂₃ v x₃ α₃₃ v x₄ α₄₃ v x₅ α₅₃ = 1

x₄ v x₁ α₁₄ v x₂ α₂₄ v x₃ α₃₄ v x₄ α₄₄ v x₅ α₅₄ = 1

x₅ v x₁ α₁₅ v x₂ α₂₅ v x₃ α₃₅ v x₄ α₄₅ v x₅ α₅₅ = 1

Выпишем все αij:	α11 = 0; α11 = 1; α13 = 0; α14 = 1; α15 = 1;
	α21 = 0; α22 = 0; α23 = 1; α24 = 0; α25 = 0;
	α31 = 0; α32 = 1; α33 = 0; α34 = 0; α35 = 1;
	α41 = 0; α42 = 0; α43 = 0; α44 = 0; α45 = 0;
	α51 = 0; α52 = 1; α53 = 0; α54 = 1; α55 = 0;

Перемножаем и выписываем в строку (конъюнкция):

x1 = 1
x2 v x1 v x3 v x5 = 1	x2 v x3 v x5 = 1
x3 v x2 = 1
x1 v x4 v x5 = 1
x5 v x1 v x3 = 1	x1 v x5 v x3 = 1

x₁ (x₂ v x₃ v x₅)(x₃ v x₂)(x₁ v x₄ v x₅)(x₁ v x₃ v x₅) = 1

(x₂ v x₃)(x₂ v x₃ v x₅)(x₁ v x₃ v x₅)(x₁ v x₄ v x₅) = 1

(x₂ v x₂x₃ v x₂x₅ v x₃ v x₃x₅)(x₁ v x₁x₄ v x₁x₅ v x₁x₃ v x₃x₄ v x₃x₅ v x₁x₅ v x₅x₄ v
v x₅) = 1

(x₂ v x₃ v x₂x₅)(x₁ v x₅ v x₁x₄ v x₁x₃ v x₃x₄ v x₃x₅)(x₂ v x₃)(x₁ v x₅ v x₃x₄) = 1

x₁x₂ v x₂x₅ v x₂x₃x₄ v x₁x₃ v x₃x₅ v x₃x₄ = 1

x₁x₂ v x₂x₅ v x₃x₄ v x₁x₃ v x₃x₅ = 1

x₁x₂ v x₁x₂x₅ v v x₁x₃ = 1

Формальное использование метода Магу.

1. Для j-го столбца матрицы смежности записать выражение вида:

, i, j, k, l,…p – строки матрицы смежности, дающие на пересечении со столбцом j число 1.

2. Выполнить п.1 для всех столбцов матрицы смежности.

3. Взять произведение всех полученных выражений и упростить его, раскрывая скобки и выполняя операцию поглощения.

4. В полученном выражении каждая конъюнкция определяет внешне устойчивое множество.

5. Среди полученных внешне устойчивых множеств выбираем минимальное для определения .

1 (2 v 1 v 3 v 5)(3 v 2)(4 v 1 v 5)(5 v 1 v 3) =
= (23 v 2 v 13 v 12 v 3 v 32 v 53 v 52)(45 v 41 v 43 v 15 v 1 v 13 v 5 v v 53) =
= (3 v 2)(1 v 5 v 43) = 31 v 35 v 43 v 12 v 25 v 234 =
= 31 v 35 v 43 v 12 v 25 = 31 v 135 v 12 v 125 v 143 =
= 13 v 135 v 12 v 125 v 143 = 13 v 12 v 143

Определяем ядро графа:

{ 3,4} ∩ { 3, 4} = {3,4}

Метод Магу определения хроматического числа.

Разбиваем граф на внутренне устойчивые взаимно непересекающиеся множества.

Алгоритм определения хроматического числа графа:

1. В формуле (1) метода Магу для поиска внутренне устойчивых множеств раскрываем скобки, упрощаем выражение. Получим дизъюнкцию конъюнкции некоторых выражений , содержащих все вершины графа, которые не входят в максимальное внутренне устойчивое множество ρ_i

(2)

2. Каждому Ф_i из (2) поставить в соответствие булеву переменную y_i, такую, что только на вершинах max внутренне устойчивого множества ρ_i, и для остальных вершин.

3. Для каждой вершины x_i графа найти все элементы , в которые вершина x_i не входит, и записать выражение

(3)

Записать выражение (3) для всех вершин графа.

4. Взять конъюнкцию всех полученных выражений. Раскрыть скобки и произвести все упрощения.

Получим выражение вида:

(4)

5. В выражении (4) найти такой член Ψ_i, который содержит минимальное количество букв:

и произвести раскраску max внутренне устойчивых множеств

S_m1, S_m2 … S_mp следующим образом:

вершины множества S_m1 - в цвет 0;

за исключением общих S_m2 - в цвет 1;

за исключением общих S_m3 - в цвет 2

и т. д.

Хроматическое число γ равно числу переменных в конъюнкции Ψ_i.

По методу Магу:

	Вершина 1 не входит в Ф1, Ф7
	Вершина 2 не входит в Ф5, Ф6, Ф8
	…
	…
	…

Записываем это в виде:

	1 Ï Ф1, Ф7
	2 Ï Ф5, Ф6, Ф8
	3 Ï Ф1, Ф2, Ф3, Ф4, Ф7
Вершины	4 Ï Ф1, Ф4
	5 Ï Ф2, Ф3, Ф5, Ф6
	6 Ï Ф4, Ф8
	7 Ï Ф1, Ф3, Ф6
	8 Ï Ф2, Ф5, Ф7

Запишем выражение (3) для вершины x₁, x₂, x₃,…., x₈ (т.е. для 1, 2, 3,….8) и возьмем конъюнкцию:

(y₁ v y₇)(y₅ v y₆ v y₈)(y₁ v y₂ v y₃ v y₄ v y₇)(y₁ v y₄)(y₂ v y₃ v y₅ v y₆)(y₄ v y₈)(y₁ v v y₃ v y₆)(y₂ v y₅ v y₇) = 1

Раскроем скобки и упростим:

Ψ = y₁y₂y₈ v y₁y₄y₅ v y₁y₂y₈ v y₄y₆y₇ v y₁y₂y₄y₆ v y₁y₃y₇y₈ v y₁y₆y₇y₈ v y₃y₄y₅y₇ v

v y₃y₄y₇y₈

Хроматическое число

Ф1 = 2568	Ф2 = 12467	Ф8 = 134578
↓	↓	↓
S1 = {1,3,4,7}	S2 = {3,5,8}	S8 = {2,6}

↓

В цвет «0»	S1 = {1,3,4,7}
В цвет «1»	S2 \ S1 = {5,8}
В цвет «2»	S8 \ (S2 \ S1) = {2,6}