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

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

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

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

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

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

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

Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа L(G). Для произвольного неориентированного мультиграфа G= реберным мульграфом L(G) называется тройка , где U M и выполняется тогда и только тогда, когда в мультиграфе G вершина является концом ребер и . Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L(G).

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

Неорграф G называется бихроматическим, если χ(G)=2. Неорграф G= называется двудольным, если множество всех ребер графа G образует разрез графа G, т.е. для некоторого разбиения множества вершин концы любого ребра принадлежат разным частям разбиения.

Теорема 4.14.1. Пусть G-неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны:

1) G-бихроматический граф;

2) G-двудольный граф;

3) G не содержит циклов нечетной длины.

Следствие 4.14.2. Если G-лес, то χ(G) 2.

Оценим хроматическое число графа G через его параметры. Обозначим через deg(G) максимальную степень вершин графа G.

Теорема 4.14.3. Для любого неорграфа G без петель выполняется неравенство χ(G) deg(G)+1.

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

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

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

2. Если вершины раскрашены цветами 1,2, …, , то новой произвольно взятой вершине припишем минимальный цвет, не использованный при раскраске вершин из множества .

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

Планарные графы.

Неорграф G называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости называется плоским. Таким образом, если граф имеет плоское изображение, то он является планарным.

П р и м е р 4.15.1. Граф (рис. 4.48а) планарен, поскольку может быть изображен, как показано на рис. 4.48б.

а б

рис. 4.48

Граф, описанный в примере 4.14.2,п.2, является планарным. Также планарным является граф, вершины которого –отверстия печатной платы, а ребра-проводники печатной платы, соединяющие отверстия.

Рассмотрим операцию подразбиения ребра в графе G= . После подразбиения ребра получается граф G̕= , где = ,R̕= т.е. ребро заменяется на - цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с помощью последовательности подразбиений ребер.

Не всякий неорграф является планарным. Критерий планарности описывает

Теорема 4.15.1 (теорема Понтрягина-Куратовского).

Граф G планарен тогда и только тогда, когда G не содержит подграфа, гомеоморфного K₅ или K_3,3 (рис. 4.49).

K₅ K₃,₃

рис. 4.49

Эквивалентная форма критерия планарности описана в следующей теореме.

Теорема 4.15.2. Тогда и только тогда неорграф G планарен, когда G не содержит подграфов, стягиваемых (т.е. получаемых последовательностью отождествлений вершин, связанных ребрами) к графу K₅ или K_3,3 (рис. 4.49).

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

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

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

Известна оценка хроматического числа планарных графов.

Теорема 4.15.4 (теорема о четырех красках). Если G- планарный граф, то χ(G) 4.

При исследовании принципиальной электрической схемы радиоэлектронного устройства с точки зрения возможности ее реализации с помощью печатного монтажа или монтажа на слоях микросхемы важно знать ответ на следующие вопросы: 1) является ли граф, соответствующий рассматриваемой принципиальной схеме, планарным? 2) если граф планарен, то как получить его изображение без пересечения ребер? На первый вопрос принципиальный ответ дает теорема Понтрягина-Куратовского, а методы получения плоских изображений планарных графов можно найти в книге Б.Н. Деньдобренко, А.С. Малика .

Если граф G непланарен, то для его геометрической реализации удаляют отдельные ребра (переносят на другую плоскость). Минимальное число ребер, которое необходимо удалить из графа для получения его плоского изображения, называется числом планарности графа G. При вынесении этих ребер на вторую плоскость получают часть графа, которая также может оказаться неплоской. Тогда вновь решают задачу вынесения отдельных ребер на следующую плоскость и т.д. Минимальное число плоскостей m, при котором граф G разбивается на плоские части G₁, G₂, …, G_m (разбиение ведется по множеству ребер), называется толщиной графа G.

Таким образом, толщина планарного графа равна 1.

П р и м е р 4.15.2. Каждый из графов K₅ и K_3,3 имеет толщину 2.