ТЕОРЕМА О 4-х КРАСКАХ

В.П. Титов

Смоленский государственный университет, г. Смоленск

Аннотация: в статье приводится доказательство утверждения, известного в теории графов, как теорема о 4-х красках.

Задача о раскраске планарного графа 4-мя различными цветами уже долгое время привлекает внимание математиков. Она имеет как теоретический, так и практический интерес. В частности к решению рассматриваемой задачи можно свести решения таких задач, как составление расписаний движения транспортных средств и распределение регистров или частот в микропроцессорах [1]. Но не смотря на продолжительные исследования данной проблемы, пока не существует общепринятого доказательства теоремы о 4-х красках.

Основной целью настоящей статьи является проведение строго математического доказательства утверждения, известного в теории графов, как теорема о 4-х красках.

Далее будем пользоваться в основном терминами и обозначениями, принятыми в [2].

Предварительно докажем следующее важное утверждение.

Лемма.Планарный граф можно дополнить ребрами так, чтобы граф остался планарным, и плоская укладка этого графа содержала только грани с 3-мя ребрами (соответственно и с 3-мя вершинами).

Замечание 1.В дальнейшем такой граф будем называть треугольным графом, соответствующим .

Доказательство. Рассмотрим произвольный планарный граф . Если он содержит кратные ребра, то рассмотрим граф, отличающийся от лишь тем, что кратность всех ребер равна 1.

Рассмотрим плоскую укладку произвольного планарного графа В ней выберем произвольную грань, содержащую более 3-х вершин – (см. рис. 1). Если такой грани нет, значит, граф уже является треугольным.

Заметим, что существуют вершины причем не смежна с . Если бы таких вершин не нашлось, то подграф содержащий вершины , был бы полным, а ( – полный граф с вершинами) не может содержать нетреугольные грани. Отметим, что при он не является даже планарным (см. рис. 2).

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

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

Рис. 1 Рис. 2

Теорема о 4-х красках.Любой планарный граф можно раскрасить 4-мя различными цветами.

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

1) Для ( ) утверждение очевидно (количество вершин меньше количества цветов).

2) Предположим, что утверждение верно для , где – некоторое произвольное, но фиксированное натуральное число ( ).

3) Докажем рассматриваемое утверждение для . Для этого рассмотрим планарный граф треугольного вида с ( )-ой вершиной. Так как – планарный, то существует его плоская укладка, и, по следствию из формулы Эйлера, существует вершина со степенью не выше 5. Рассмотрим граф , отличающийся от только отсутствием вершины (и смежных с ребер). По предположению можно раскрасить 4-мя различными красками (в нем вершин). Если в смежные к вершины в оказались раскрашены в 3 цвета, то покрасив А в 4-й цвет, получим раскраску 4-мя различными цветами. В противном случае рассмотрим плоскую укладку .

С точностью до переобозначения цветов и симметрии возможны 2 варианта: первый (I) наглядно изображен на рисунке 3, второй (II) – на рисунке 4.

Рис. 3 Рис. 4 Рис. 5

I. Рассмотрим чередующиеся цепи и (см. рис. 3). Если какой-то из них нет, то соответствующий цвет 4 или 3 можно перекрасить в 2, а вершину в цвет 4 или 3 соответственно. Раз эти цепи существуют, значит, не существует цепей и . Таким образом, пришли к противоречию планарности (см. рис. 5). А значит, можно перекрасить одну из вершин цвета 1 (см. рис. 5) в цвет 3, а вторую – в 4. Следовательно, для вершины освобождается цвет 1.

II. Воспользуемся тем (см. рис. 4), что доказательство проводится для треугольного графа, а значит все его грани, которым принадлежит , – треугольные (см. рис. 6). Но вершины одного цвета не могут быть смежными, значит, грань содержит больше 3-х ребер (вершин), что противоречит предположению о треугольности графа.

Рис. 6

4) По принципу математической индукции заключаем, что теорема верна для любого .

Замечание 2. Теорема доказана для любого планарного графа , так как полученная раскраска не зависит от кратности ребер.

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

Литература

1. Оре О. Графы и их применение. – М.: Мир, 1965.

2. Зыков А.А. Основы теории графов. – М.: Наука, 1987.

3. Горбатов В.А. Фундаментальные основы дискретной математики. – М.: Наука, 2000.

4. Оре О. Теория графов. – М.: Наука, 1968.

5. Харрари Ф. Теория графов. – М.: Мир, 1973.