21.2.6 Реберная раскраска графа

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

Для реберной раскраски имеется достаточно точная оценка требуемого числа красок в виде

,

где максимальная степень вершин графаG.

Число красок, необходимое для реберной раскраски, при которой смежные ребра имеют разный цвет, обозначается и называется хроматическим классом или хроматическим индексом.

Для некоторых видов графов хроматический класс определяется достаточно просто, например, для графа в виде цикла с nвершинами2 или 3 в зависимости от того, четноnили нечетно. Для двудольных полных графов= max(m,n). Для полных графов=n, еслиnнечетно, и=n– 1, еслиnчетно.

Для раскраски ребер графа рис. 8.2 требуется 3 краски. Раскрасьте граф самостоятельно.