2018-01-08
578
Раскраска представляет собой маркирование вершин графа таким образом, чтобы у смежных вершин маркеры не совпадали. Вместо красок используются числа 0, 1, 2… Условие оптимальности раскрашивания - использование минимального числа красок j. Это число называется хроматическим числом графа.
Граф, который можно представить на плоскости без пересечения его рёбер, называется плоским.
Теорема. Для плоских графов j £ 4.
Отметим, что проблема раскраски - алгоритмически неразрешима.
Пример 3.13. Рассмотрим граф G (рис. 3.13). Убедившись в том, что он – плоский (ребро (x1, x5) может быть проведено вне контура (x1, x2, x3, x5)), произведём его раскраску. Имеем: j=3 (краски - 0, 1, 2).
Рис. 3.13
В общем случае строим таблицу для определения максимальных внутренне-устойчивых подмножеств множества вершин графа, т. е. множеств несмежных вершин графа. Строки таблицы – внутренне-устoйчивые множества. Столбцы этой таблицы - номера вершин графа, а последний столбец - имя очередного максимального внутренне-устойчивого подмножества.
|
|
|
Несмежные вершины отмечены в таблице единицами. Далее решается задача построения одного кратчайшего покрытия (методом минимального столбца - максимальной строки). Вершины, принадлежащие каждому подмножеству, вошедшему в найденное кратчайшее покрытие, окрашивается одной краской. Если некоторая вершина принадлежит нескольким вошедшим в покрытие подмножествам, то она в одном остаётся, из остальных исключается. Для нашего примера получим три подмножества: Y1,Y2,Y3, определяющие три краски 0, 1, 2 соответственно.
как показано на рис. 3.13, если x 1 покрасить краской 0, то все смежные с ней вершины x 2, x 3, x 4, x 5 нельзя покрасить 0. Вершины x 2, x 4- смежные, для них необходимы две разные краски (1 и 2); аналогично - для x 3, x 4. Однако вершины x 2, x 3 - не смежные, и их можно покрасить одной краской.
Таким образом, изображенная на рис. 3.13 раскраска - минимальна.
Дополнительно об использованных алгоритмах можно прочитать в [1, 2]. Элементы теории графов изложены в [3].
