Задача коммивояжёра: Имеется p городов, расстояния между которыми известны

посетить все p городов по одному разу, вернувшись в тот,

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

и задан матрицей весов.
Будем считать, что матрица весов необязательно

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

решений, в котором каждому узлу x соответствует некоторое подмножество М(х)

множества всех маршрутов.
Корню поставлено в соответствие множество всех маршрутов.
Пусть х – некоторый узел дерева. Выберем дугу (v, w), которая входит хотя бы в один маршрут из М(х).

которых можно отнести все маршруты, содержащие дугу (v, w), а

в другое – не содержащие её.
Будем считать, что первое подмножество соответствует левому сыну узла х, а второе – правому. Получаем в общих чертах правило ветвления.
Узел дерева решений, для которого строятся сыновья называется активным.

перебором заключается в том, что активными являются лишь те узлы,

в которых может содержаться оптимальный маршрут.
Правило активизации узлов, которое сводится к правилу подсчёта границ.
Предположим, что для узлов дерева решений вычислено значение f(x) такое, что вес любого маршрута из множества М(х) не меньше, чем f(х). Такое число называется нижней границей или границей узла х.

качестве активного выбирается узел с наименьшей нижней границей.
Дерево решений

прирастает за счёт сыновей активного узла.
Узел, для которого построены оба сына, активным стать в дальнейшем не может.

не будет объявлен узел, для которого множество М(х) состоит из

одного маршрута, а границы всех других узлов не меньше чем вес этого маршрута.

этой же строки (столбца) называют редукцией.
Процедуру, которая сначала осуществляет

редукцию каждой строки, а затем по изменённой матрице редукцию всех столбцов, называют редукцией матрицы, а саму матрицу – редуцированной.
При этом в каждой строке и каждом столбце имеется хотя бы один нулевой элемент.

является нижней границей всех маршрутов коммивояжёра для исходной нередуцированной матрицы

весов. Получили правило вычисления нижней границы корневого узла дерева решений.
Правило построения нижней границы для каждого узла аналогично.

этого подмножества не смежны.
Во многих приложениях рассматриваются разбиения вершин на

независимые подмножества.
Такие разбиения удобно описывать следующим образом.

вершин графа на конечное множество цветов;
n-раскраска графа - раскраска

с использованием n цветов.
Раскраска называется правильной, если никакие две вершины одного цвета не смежны.
Очевидно, что для графа без петель всегда существует правильная раскраска в |V| цветов.

существует правильная n-раскраска.

Лемма 1. В любом планарном графе без

петель и кратных ребер существует вершина степени не более пяти.

ребер является не более чем 5-хроматическим.

Доказательство: (индукцией по числу вершин).

При p=1 утверждение теоремы верно. Допустим, что утверждение верно для всех p

p0 вершинами; по лемме 1 в нем есть вершина v0

степени не более 5.
По предположению индукции граф G', получаемый удалением из G вершины v0 (очевидно, также планарный), может быть раскрашен не более, чем в 5 цветов.
Пусть v1...vk, k=deg(v0) - все вершины-соседи вершины v0, расположенные по часовой стрелке относительно v0.

то "покрасим" вершину v0 в оставшийся 5-й цвет и получим

правильную раскраску.

Осталось рассмотреть случай, когда в раскраске вершин v1...vk в графе G' используется 5 цветов (k=5).
Пусть ci - цвет вершины vi (i=1..5). Рассмотрим множество A, состоящее из вершины v1 и всех вершин графа G, исключая v0, в которые можно дойти из v1 только по вершинам цветов c1 и c3.

вершин множества A (c1«c3); окраска при этом останется правильной.
Действительно,

множество A состоит по определению из всех вершин цветов c1 и c3, в которые можно дойти из v1, поэтому среди вершин, смежных вершинам, принадлежащим A, нет вершин цветов c1 или c3.

с3, следовательно, можно использовать цвет c1 для "окраски" вершины v0

и получить таким образом правильную раскраску графа G.

Остается второй случай. Из принадлежности вершины v3 множеству A следует, что существует путь из v1 в v3 (v1Sv3), проходящий только по вершинам цветов c1 и c3

в геометрической реализации графа.

Вершина v2 находится внутри этой замкнутой

кривой, а v4 - снаружи. Это следует из того, что линии, соответствующие ребрам графа в его геометрической реализации, не могут пересекаться (не считая концов).

Определим множество B, состоящее из вершины v2 и всех вершин графа G, исключая v0, в которые можно дойти из v2 только по вершинам цветов c2 и c4.

в v4 должен проходить, по крайней мере, через одну вершину,

принадлежащую циклу L - т.е. либо через вершину v0, либо через вершину, окрашенную в цвета c1 или c3.
Следовательно, как и в первом случае, можно поменять цвета вершин множества B (c2«c4) и "покрасить" v0 в c2. 

ребер является не более чем 4-хроматическим.

Проблема четырех красок оставалась

нерешенной в течение многих лет. Утверждается, что эта теорема была доказана с помощью хитроумных рассуждений и компьютерной программы в 1976 году .

порядке не возрастания числа связей.
Начинаем раскрашивание в очередной цвет.
Последовательно перебираем

вершины и, если рассматриваемая вершина не раскрашена, а также не имеет связей с вершинами раскрашенными в этот цвет, то красим её в этот цвет.

пункт 3, с цветом на единицу больше, пока все вершины

не раскрашены. Число цветов это и есть хроматическое число.