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

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	2	3	4	5	6	7	8
1		1			1	1
2	1		1	1
3		1
4		1			1			1
5	1			1		1
6	1				1		1	1
7						1		1
8				1		1	1

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

	Вершина 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}