Раскраска графов

Пусть G = <V, U> - нефграф без петель.

Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если (Vi, Vj)-дуга, то вершины Vi, Vj имеют различные цвета. Хроматическим числом Х (G) графа G называется минимальное число цветов, требующиеся для раскраски G (рис.)

Пример. Так как в полном графе Gn любые две различные вершины связаны ребром, то Х (Gn) = n.

Многие практические задачи сводятся к построению раскрасок графов.

Пример 1. Рассмотрим задачу составления расписания. Предположим, что нужно прочесть несколько лекций за кратчайшее время. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно. Построим граф G, вершины которого биективно соответствуют лекциям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам одного цвета, могут читаться одновременно. Напротив, любое допустимое расписание определяет раскраску графа G. Оптимальные расписания соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно Х (G).

Пример 2. Рассмотрим граф G, вершины которого – страны, а ребра соединяют страны, имеющие общую границу. Число Х (G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.

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

Неорграф G называется бихроматическим, если Х (G) = 2. Неорграф G = <V, U> называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин {V1, V2} концы любого ребра принадлежат разным частям разбиения.

Примером служит задача «Три дома, три колодца».

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

1. Произвольная вершина V1 графа G принимает цвет 1.

2. Если вершины V1, …, Vi раскрашены l цветами е, 2, … е, е ≤ i, то новой произвольно взятой вершине Vi+1 припишем минимальный цвет, не использованный при раскраске вершин из множества {Vj | ρ (Vi+1, Vj) = 1, j < i}.

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

Все двудольные графы бихроматические, Х (G) = 2.

Пример:

бихроматический двудольный

Любой бихроматический граф является двудольным.

Теорема: для того, чтобы граф был бихроматическим, необходимо и достаточно, чтобы он был связным и не содержал элементарных циклов нечетной длины.

Дано: G – бихромат. граф

Док-ть: связный и не содержит циклов нечетной длины

Док-во (от противного)

Пусть граф содержит циклический элемент

Х = 3, но G – бихромат – противоречие.

Обратная теорема:

Дано: G – связный, не содержит циклов нечет. длины

Док-ть: Х (G) = 2

Док-во:

1) рассм. связный граф, который не имеет циклов

2) граф, содержит циклы четной длины

Дата добавления: 2015-10-13