14.Раскраска графа. Алгоритм А.П.Ершова. Двудольные графы. Свойства двудольного графа.

В неорграфе G(A,U) взвесим вершины целыми положительными числами и потребуем при этом, чтобы смежным вершинам были сопоставлены разные числа. Если число трактовать как номер краски (цвета), то такое взвешивание вершин называют раскраской графа.

Раскраска графа, в которой используется минимальное число красок, называется минимальной. Число красок минимальной раскраски является одной из характеристик графа и называется хроматическим числом.

К задаче определения минимальной раскраски графа сводятся многие задачи. В качестве примера назовем задачу нахождения минимального числа внутренних переменных в программе. При построении программ необходимо вводить добавочные временные переменные, например, переменную - счетчик цикла в операторе   for (int i=1;i<10;i++).

Если вершинам сопоставить вхождение переменной в программу, а ребром обозначить зависимость одной переменной от другой, то идентификатору переменной будет соответствовать краска. Действительно, зависимые переменные должны иметь разные имена. Тогда нахождение минимального числа внутренних переменных сведётся к минимальной раскраске вершин графа.  В этой трактовке задача рассматривалась А.П. Ершовым, одним из крупнейших теоретиков и практиков программирования, предложившим интересный эвристический алгоритм решения этой задачи.

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

1. Выберем вершину и присвоим ей первую краску.
2. Выберем из 2-окрестности этой вершины любую вершину и присвоим ей ту же краску. Объединим эти две вершины в одну так, что все ребра, связывающее не раскрашенные вершины с этими вершинами, заменяются ребрами к этой объединенной вершине. 
3. Для полученного графа находим новую нераскрашенную вершину из 2-окрестности, если таковая есть, красим ее в ту же краску  и объединяем с объединенной вершиной.
4. Пункты 2 и 3 выполняются до тех пор, пока существуют нераскрашенные вершины в 2 - окрестности объединенной вершины.
5. Затем из числа нераскрашенных вершин выбирается новая вершина и для нее процедура раскраски повторяется, и так до тех пор, пока все вершины не будут раскрашены.

Алгоритм достаточно просто реализуется, если граф представлен в виде матрицы смежности, однако приведены примеры, когда  решение имеет не минимальное количество красок. Алгоритм А.П. Ершова относится к так называемым эвристическим алгоритмам, построенным на основе некоторых разумных с точки зрения здравого смысла методах, для которых гарантий оптимальности нет. В алгоритме Ершова исходят из того, что нужно в одну и ту же краску покрасить как можно больше вершин. Для этого предлагается выбирать следующую вершину для раскраски на минимально возможном расстоянии от уже покрашенных в ту же краску вершин, чтобы обеспечить больше простора следующим шагам выбора.

Если хроматическое число графа равно двум, граф называется бихроматическим,. В таких графах все вершины делятся на два непересекающихся подмножества А1 и А2, в каждом из которых элементы не связаны между собой. Такие графы называют ещё двудольными и обозначаются как G=<A1,A2,U>, где А1Ç А2=Æ, U ÍA1x A2.