В неорграфе 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.
К задачам о двудольных графах сводится большое число задач, называемых задачами о назначениях. К ним относятся задачи:
· распределения множества задач по процессорам в многопроцессорной системе;
· распределения деталей по обрабатывающим центрам в гибких автоматизированных системах;
· назначения сотрудников на должности;
· распределения товаров со складов по торговым точкам.
Во всех этих задачах исходное множество состоит из двух различных по смыслу подмножеств, а связи могут быть только между элементом одного и элементом второго из этих подмножеств.
Свойство бихроматического графа определяет следующая теорема.
Теорема. Граф является бихроматическим тогда и только тогда, когда он не содержит циклов нечётной длины.
Необходимость доказывается просто: если в графе находится цикл нечётной длины, раскраска двумя красками его вершин невозможна. Достаточность доказывается сложнее и здесь не приводится.
