Программирования.

Пусть - матрица раскраски графа,

1, если вершина окрашена в цвет j,

0,в противном случае.

Если A= - матрица смежности графа G с диагональными элементами равными 0, то следующие 2 условия гарантируют допустимые раскраски вершин графа G:

, n (1)

,

здесь q – верхняя оценка хрономического числа графа G. Условие (1) обеспечивает раскраску вершины в один и только один цвет. В(2) L- любое очень большое положительное число , больше чем n.

Если вершина окрашена в цвет j, то , то первый член в (2) равен 0.

Тогда и 2-й член =0, чтобы выполнялось неравенство , т.к. числа и неотрицательны. Итак, (2) обеспечивает раскраски, т.е., если вершина окрашена в цвет

j , то нет смежной с вершины того же цвета.

Если вершина окрашена в цвет, отличный от j, то нет смежной с вершины того же цвета .Если вершина окрашена в цвет отличный от j() , то первый член в (2) равен L .Т.к. 2-й член в(2) не может достигнуть L( его значение наибольшее равно n-1 , то какое-бы число вершин ,смежных с вершиной , ни было окрашено в цвет j , неравенство (2) по-прежнему будет выполнено.

Пусть теперь каждому цвету j сопоставлен штраф выбранный тем , что (штраф =1) –ф-и ( рекурентный).(3), где h –верхние оценки для наибольшего числа вершин в графе, которые могут быть окрашены в 1 цвет, т.е. h – произвольное число , больше , чем G)- число независимости графа(максимальные ……… подмножества S такого , что граф (S) вместе несвязный –число независимости.

Любые 2 вершины в нём несмежны (G)= , где Q – семейство всех независимых множеств графа G .)

Можно положить h=n!!!

Итак, имеем задачу минимизировать Z=min(4) при ограничениях (1)(2).

Минимизация (4) обеспечивает выполнимость следующего условия :

Цвет j+1 будет ………. в раскраске вершин , если цвета от 1 до j достаточны для …….. раскраски.

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

Бернс вместо условия (2) предложил следующее:

(5)

-матрица инцеденции. Условие(5)отражает тот факт, что не более, чем 1 из 2-х концевых вершин любого ребра может быть окрашено в цвет j.

В(5) требуется mq ограничений

В(2) nq ограничений, обычно m>n!!!

Приведём ряд теорем:

1. Ели наибольшее из степеней вершин графа G равен p, то он ( p+1)-раскашиваемый
2. a) Любой пленарный граф 5-………

б) любой пленарный граф, не содержит треугольников 3- раскрашенный (терема Грега).

с)граф G -2-x раскраски тогда и только тогда, когда он эйлеров.(теорема Кароля)

д) усиление a) еслиG –простой связный граф , то он p-…….(р),где р –наибольший из степеней вершин.

е) для nвершина 4 – раскраски ……. и красок.

Рёберная окраска

Граф G- рёберно к раскрашенный , если его рёбра можно раскрасить К окрасками таким образом, что некие 2 смежные ребра не окажутся 1 цвета. Если граф К раскраски …….. , но не явится (к-1)………, то К –хрономическое число(……..)графа G.

Ясно, что если наибольшее из степеней вершин граф G равен р, то .