Том 11. Карты метро и нейронные сети. Теория графов

При n = 1 (а) доказательство тривиально. Допустим, что это утверждение верно для n прямых (b), и рассмотрим карту, на которой изображена n + 1 прямая (с). Если мы удалим одну из линий, то получим карту из n прямых, которую можно раскрасить двумя цветами (верно по индукции). Следовательно, при добавлении (n + 1)-й прямой вверху (или справа) от добавленной прямой все цвета останутся без изменений, а с другой стороны от этой прямой все области изменят цвет на противоположный. Таким образом, карту из n + 1 прямой можно раскрасить всего двумя красками. С учетом соответствующих различий можно заметить, что любую карту из n окружностей, случайным образом распределенных на плоскости, также можно раскрасить двумя красками. И в случае с прямыми, и в случае с окружностями все вершины полученного графа будут иметь четную степень. В любом графе, вершины которого имеют четную степень, бóльшую двух, при удалении цикла получится граф, вершины которого по-прежнему будут иметь четную степень. Как и все графы такого типа, его можно будет представить в виде прямых или окружностей. Теорема о двух красках доказана.

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

Доказательство теоремы о трех красках сложнее, чем предыдущей, поэтому мы не будем приводить его здесь. Сама теорема звучит так:

«Плоский граф с вершинами степени 3 можно раскрасить тремя красками тогда и только тогда, когда все его грани ограничены четным числом ребер».

* * *

ОХРАННИКИ В МУЗЕЯХ И РАСКРАСКА ГРАФОВ

В 1973 году, анализируя задачу о расположении охранников в залах музея, Виктор Клее задался вопросом: если музей имеет форму многоугольника с n сторонами, какое количество охранников необходимо для того, чтобы они могли просматривать все стены, не двигаясь с места? На первом рисунке изображен выпуклый многоугольник, который легко просматривается одним охранником, стоящим в углу. Однако в случае с невыпуклым многоугольником, изображенным на следующем рисунке, одного охранника уже недостаточно. Ответ задачи таков: для многоугольника с n сторонами достаточно [n/3] охранников. (Знак [] обозначает целую часть отделения, то есть результат деления с отброшенными десятичными знаками.)

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

* * *

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

Четырех цветов достаточно