На этом шаге мы рассмотрим раскраски графов.
Вершинной раскраской (далее - просто раскраской) графа называется отображение множества вершин графа на конечное множество (множество цветов); n-раскраска графа - раскраска с использованием n цветов. Раскраска называется правильной, если никакие две вершины одного цвета не смежны. Очевидно, что для графа без петель всегда существует правильная раскраска в |V| цветов.
Хроматическим числом графа G называется минимальное число n=c(G), такое, что существует правильная n-раскраска.
- Лемма 1.
- В любом планарном графе без петель и кратных ребер существует вершина степени не более пяти.
- Доказательство.
- Допустим, что степени всех вершин превосходят 5. Тогда 2q=Sum(deg(vi), i=1..|V|)<6p и q<3p. Но по следствию 1 теоремы 2 должно выполняться неравенство q<=3(p-2)<3p - получили противоречие.
- Теорема о пяти красках.
- Каждый планарный граф без петель и кратных ребер является не более чем 5-хроматическим.
- Доказательство (индукцией по числу вершин).
- При p=1 утверждение теоремы верно. Допустим, что утверждение верно для всех p<p0.
Докажем, что тогда оно верно и для p0.
Рассмотрим планарный граф G без петель и кратных ребер с p0 вершинами; по лемме 1 в нем есть вершина v0 степени не более 5. По предположению индукции (*) граф G', получаемый удалением из G вершины v0 (очевидно, также планарный), может быть раскрашен не более, чем в 5 цветов. Пусть (**) v1, ..., vk, k=deg(v0) - все вершины-соседи вершины v0, расположенные по часовой стрелке относительно v0. Если в раскраске вершин v1, ..., vk используется не более 4-х цветов, то "покрасим" вершину v0 в оставшийся 5-й цвет и получим правильную раскраску.
Осталось рассмотреть случай, когда в раскраске вершин v1, ..., vk в графе G' используется 5 цветов (k=5). Пусть ci - цвет вершины vi (i=1..5). Рассмотрим множество A, состоящее из вершины v1 и всех вершин графа G, исключая v0, в которые можно дойти из v1 только по вершинам цветов c1 и c3. Возможны два случая:
- v∉A;
- v∈A.
В первом случае поменяем цвета вершин множества A (c1<c3); окраска при этом останется правильной. Действительно, множество A состоит по определению из всех вершин цветов c1 и c3, в которые можно дойти из v1, поэтому среди вершин, смежных вершинам, принадлежащим A, нет вершин цветов c1 или c3. После замены цветов вершин множества A вершина v1 получит цвет с3, следовательно, можно использовать цвет c1 для "окраски" вершины v0 и получить таким образом правильную раскраску графа G.
Рис.1. Пример планарного графаОстается второй случай. Из принадлежности вершины v3 множеству A следует, что существует путь из v1 в v3 (v1->v3), проходящий только по вершинам цветов c1 и c3 (см. рисунок 1). Рассмотрим цикл L=v1->v3(v3,v0)v0(v0,v1)v1 и замкнутую кривую, которая соответствует этому циклу в геометрической реализации графа. Вершина v2 находится внутри этой замкнутой кривой, а v4 - снаружи. Это следует, во-первых, из того, что линии, соответствующие ребрам графа в его геометрической реализации, не могут пересекаться (не считая концов), и, во-вторых, из (**). Определим множество B, состоящее из вершины v2 и всех вершин графа G, исключая v0, в которые можно дойти из v2 только по вершинам цветов c2 и c4. Вершина v4 не принадлежит B, поскольку любой путь из v2 в v4 должен проходить, по крайней мере, через одну вершину, принадлежащую циклу L - т.е. либо через вершину v0, либо через вершину, окрашенную в цвета c1 или c3. Следовательно, как и в первом случае, можно поменять цвета вершин множества B (c2<c4) и "покрасить" v0 в c2.
- Теорема о четырех красках.
- Каждый планарный граф без петель и кратных ребер является не более чем 4-хроматическим.
Проблема четырех красок оставалась нерешенной в течение многих лет. Утверждается, что эта теорема была доказана с помощью хитроумных рассуждений и компьютерной программы в 1976 году (Kenneth Appel and Wolfgang Haken. Every Planar Map is Four Colorable. Contemporary Mathematics 98, American Mathematical Society, 1980)
На следующем шаге мы рассмотрим графы с атрибутами.
