Раскраска планарных графов

Проблема раскраски планарных графов является одной из самых знаменитых проблем теории графов. Первоначально вопрос формулируется следующим образом: достаточно ли четырех красок для такой раскраски произвольной географической карты, при которой соседние страны окрашены в различные цвета? В 1879 г. британский математик А. Кэли выдвинул гипотезу четырех красок: «Всякий планарный граф вершинно 4-раскрашиваем.» Гипотеза четырех красок привлекала внимание многих исследователей. Уже в 1880 г. появилось первое доказательство А.Кемпе. Ошибка в этом доказательстве была обнаружена Р. Хитвудом в 1890 г. Одновременно он показал, что если в формулировке гипотезы слова “четыре” заменить на “пять”, то полученная теорема легко доказывается.

Теорема.о пяти красках. Всякий планарный граф 5-раскрашиваем.

Доказательство (метод математической индукции по количеству вершин). Для планарных графов, у которых меньше шести вершин теорема очевидна.

Предположим, что G планарный граф с n вершинами, и что все планарные графы с n-1 вершинами 5-раскрашиваемы. Можно считать, что G плоский граф, и что он содержит вершину v, степень которой не больше пяти. Удаление вершины v и всех инцидентных ей ребер приводит нас к графу с n-1 вершиной, который, по предположению индукции 5-раскрашиваем, раскрасим его. Тогда в исходном графе G останется окрасить только одну вершину v.

Если степень вершины v меньше пяти, то ее можно окрасить в любой цвет, не участвующий в окраске смежных с ней вершин.

Пусть степень вершины v равна пяти. Если среди смежных вершин есть две вершины одинакового цвета, то ее можно окрасить в цвет, не использованный для окраски этих вершин.

Итак, остался последний случай: всем вершинам, смежным с v присвоены различные цвета. Обозначим вершины, смежные с v через v1,v2,...,v5. Пусть они окрашены в цвета c1,c2,...,c5. Определим H(i,j) как подграф графа G, вершинами которого являются все вершины цвета ci или cj, а ребрами - все ребра, соединяющие вершину цвета ci с вершиной цвета cj. Рассмотрим два случая.

1). v1 и v3 не принадлежат одной компоненте связности графа H(1,3). В этом случае можно поменять цвета всех вершин той компоненты H(1,3), которая содержит v1 (цвет с1 на цвет с3, а цвет с3 на цвет с1). В результате v1 приобретет цвет c3, что позволит окрасить v в цвет c1.

2). v1 и v3 принадлежат одной компоненте связности графа H(1,3). В этом случае существует цикл C вида v->v1->..->v3->v, часть которого, заключенная между v1 и v3 целиком лежит в H(1,3). Так как v2 находится внутри цикла C, а v4 - вне его, то не существует простой цепи из v2 в v4, целиком лежащей в H(2,4). Поэтому v2 и v4 принадлежат разным компонентам связности графа H(2,4). В этом случае можно поменять цвета всех вершин той компоненты H(2,4), которая содержит v2 (цвет с2 на цвет с4, а цвет с4 на цвет с2). В результате v2 приобретет цвет c4, что позволит окрасить v в цвет c2.

Таким образом, все вершины исходного графа можно окрасить в 5 цветов, что и требовалось доказать.

Задачи по теории графов

Дата добавления: 2014-12-29