Раскраска ребер

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

В правильной раскраске ребер множество ребер одного цвета образует паросочетание. Поэтому такую раскраску можно трактовать как разбиение множества ребер графа на паросочетания.

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

Теорема Визинга. Для любого графа G справедливо неравенство .

Задачи

8.1. Найдите хроматическое число графов , , , .

8.2. Найдите хроматическое число графа 1) ; 2) ; 3) .

8.3. Примените алгоритм раскрашивания, основанный на дереве решений, к графу из

задачи 6.9.

8.4. Примените алгоритм последовательной раскраски к графу, изображенному на

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

номеров.

8.5. Для каких из следующих графов алгоритм последовательной раскраски дает точный

результат при любом упорядочении вершин: , , , , ?

8.6. Найдите хроматический индекс графов , , , , , .