РГР_ПО_ДИСКРЕТКЕ

2.2. Раскраска в графах

Задача раскраски вершин или рёбер графа занимает особое место в теории графов. Характерной особенностью этих задач является существование объектов, которые по какой-либо причине не могут быть объединены в одну группу.

Если G=<V,U> – некоторый граф, а k – натуральное число, то произвольная функция f: V{1,2,…,k} называется вершинной k-раскраской или просто k-раскраской графа G.

Раскраска называется правильной, если

V{1,2,…,k},

f (v)f (u)

для любых соседних вершин v и u.

Граф, для которого существует правильная k-раскраска, называется k-раскрашиваемым (или раскрашиваемый k цветами). Правильную k-раскраску можно интерпретировать как окрашивание каждой вершины G в один из k цветов, при этом смежные вершины должны получить различные цвета. При k- раскраске может быть использовано меньше k цветов и правильную раскраску можно рассматривать как разбиение

V =V₁V₂…V _l, где l  k

Множества вершин V графа G, на не более чем k-непустых классов, каждый из которых является независимым множеством. Классы V₁,V₂,… называются цветными классами.

Минимальное число k, при котором граф G имеет правильную раскраску, называется хроматическим числом этого графа и обозначается (G). Если (G)=k, то граф называется k-хроматическим и его раскраска является минимальной.

Рис. 2.3. Пример правильной раскраскиграфа.

Пример правильной раскраски приведен на рис. 2.3. Меньшим числом цветов этот граф раскрасить нельзя, так как имеется цикл, для правильной раскраски которого требуется не менее 2-х цветов, и ещё один цвет – для вершины 3 (=3).

Примеры задач, сводящихся к правильной раскраске:

Задача составления расписаний. Предположим, что нужно прочесть несколько лекций в кратчайший срок. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (один и тот же лектор). Строится граф G, вершины которого соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим один цветной класс, читаются одновременно. И, наоборот, любое правильное расписание определяет правильную раскраску графа G. Оптимальные расписания соответствуют минимальным раскраскам, и число часов, необходимое для прочтения всех лекции, равно (G).
Задача распределения оборудования. Заданы множества V={v,…v_N} и S={s₁,…,s_m} работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть занят одновременно на 2-х или более работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным. Строится граф G, в котором v_i и v_j (ij) смежны тогда и только тогда, когда для выполнения работ v_i и v_jтребуется хотя бы один общий механизм. При правильной раскраске графа G работы, соответствующие вершинам одного цвета, можно выполнить одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.

Для некоторых графов несложно найти хроматические числа: (K_M)=M; (K_M-r)=M-1; (K_N_,_M)=2; (C₂_M)=2; (C₂_M₊₁)=3. Очевидно, что граф 1- хроматический, когда он пустой. 2- хроматический – когда он двудольный и непустой.

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

Алгоритм последовательной раскраски:

Шаг 1. Произвольной вершине v₁графаGприсваивается цвет1.

Шаг 2. Если вершины v₁, v₂,…v_iраскрашеныLцветами1,2,…L, L i, то новой произвольно взятой вершинеv_i₊₁приписывается цвет, не использованный при раскраске вершин из её окружения.

Поскольку точная раскраска граф невозможна, имеет смысл привести некоторые оценки хроматического числа.

Для любого графа G верно неравенство:

(G)  1+ max (H), H ,

где - минимальная из степеней вершин графа G;

- множество всех порождённых подграфов графа G.

Для любого графа G верно неравенство:

(G) 1+G

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

Рис 2.4

Если G – связный граф, не являющийся полным, и G3, то (G) G.

Эта оценка может быть завышенной, например, (K_1,_n)  n, в то время как для двудольного графа (K_1,_n)=2, (рис. 2.4.).

Одной из самых знаменитых задач о раскрасках является раскраска планарных графов.

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

Позже задача была формализована: картой стали называть связный плоский мультиграф без мостов. Грани карты, имеющие общее ребро, называются смежными. Функция О, ставящая в соответствие каждой грани натуральное число О:Г{1,2,…k} –цвет грани Г – называется k-раскраской, если цвета смежных граней различны.

В 1879 году британский математик А. Кэли сформулировал гипотезу четырёх красок (задача была известна и ранее):

Всякая карта 4-раскрашиваема (другими словами, для раскраски планарного графа достаточно точно четырёх красок).

По аналогии с вершинной раскраской существует рёберная.

Содержание