Исторический экскурс. 
Применение раскрасок графов в современной науке и технике

Родоначальником теории графов принято считать математика Леонарда Эйлера (1707−1783). Однако теория графов многократно переоткрывалась разными авторами при решении различных прикладных задач.

1. Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году.

рис. 1.

Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году.

Задача о четырех красках. Каждый многоугольный граф можно представить себе как некоторую географическую карту, где граниэто страны, а бесконечная граньокружающий их океан. На такой карте все страны и океан раскрашиваются так, чтобы их можно было отличить друг от друга. Для этого страны с общей границей должны быть раскрашены в разные цвета. Если в нашем распоряжении имеется достаточное количество красок, это не составит никакого труда. Намного сложнее решить вопрос о наименьшем количестве красок, достаточного дпя такого раскрашивания стран данной карты. Широко известное предположение состоит в том, что каждая карта может быть раскрашена с соблюдением требуемых условий при помощи четырех красок. Британский математик А. Кэпи, один из первых исспедователей теории графов, в 1879 г. опубликовал статью о проблеме четырех красок, оказавшуюся вполне уместной в nервом томе трудов Коропевского географического общества. Эту статью часто считают «свидетельством о рождении» проблемы четырех красок. Однако это не совсем правильно. Шотландскпй физик Фредерик Гутри рассказывал, что около 1850 г. эта проблема была достаточно популярна среди студентов-математиков в Лондоне и что его брат Фрэнсис Гутри обратил на нее внимание своего nреподавателя математика А. Де Моргана. Поначалу проблема не казалась слишком серьезной. Математики, по-видимому, рассматривали ее как почти очевидный факт. В дальнейшем появилось несколько неверных доказательств: проблема четырех красок, сбивающая с толку простотой своей формулировки, сопротивлялась всем усилиям самых выдающихся математиков. Большой интерес к теории гpaфов, возникший в связи с этой проблемой, способствовал' открытию многих важных результатов этой теории, поскольку они казались полезными для решения проблемы четырех красок.

В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно — объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.

Теория графов — раздел дискретной математики, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств. G=(V, E), где V есть подмножество любого счётного множества, а E — подмножество VЧV.

Основные понятия теории графов.

• 1) Графом G (V, E) называется совокупность двух множеств — непустого множества V (множества вершин) и множества E двухэлементных подмножеств множества V (E — множество ребер).
• 2) Ориентированным называется граф, в котором — множество упорядоченных пар вершин вида (x, y), где x называется началом, а y — концом дуги. Дугу (x, y) часто записывают как. Говорят также, что дуга ведет от вершины x к вершине y, а вершина y смежная с вершиной x.
• 3) Если элементом множества E может быть пара одинаковых (не различных) элементов V, то такой элемент множества E называется петлей, а граф называется графом с петлями (или псевдографом).
• 4) Если E является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными ребрами, а граф называется мультиграфом.
• 5) Если элементами множества E являются не обязательно двухэлементные, а любые подмножества множества V, то такие элементы множества E называются гипердугами, а граф называется гиперграфом.
• 6) Если задана функция F: V > M и/или F: E > M, то множество M называется множеством пометок, а граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа. Если функция F инъективна, то есть разные вершины (ребра)имеют разные пометки, то граф называют нумерованным.
• 7) Подграфом называется граф G?(V?, E?), где и/или .

a) Если V? = V, то G? называется остовным подграфом G.

b) Если, то граф G? называется собственным подграфом графа G.

c) Подграф G?(V?, E?) называется правильным подграфом графа G (V, E), если G? содержит все возможные рёбра G.

• 8) Степень (валентность) вершины — это количество ребер, инцидентных этой вершине (количество смежных с ней вершин).
• 9) Маршрутом в графе называется чередующаяся последовательность вершин и ребер, в которой любые два соседних элемента инциденты.

a) Если, то маршрут замкнут, иначе открыт.

b) Если все ребра различны, то маршрут называется цепью.

c) Если все вершины (а значит, и ребра) различны, то маршрут называется простой цепью.

d) Замкнутая цепь называется циклом.

e) Замкнутая простая цепь называется простым циклом.

f) Граф без циклов называется ациклическим.

g) Для орграфов цепь называется путем, а цикл — контуром.

В теории графов, раскраска графов является частным случаем разметки графов. При раскраске элементам графа ставятся в соответствие метки с учётом определенных ограничений; эти метки традиционно называются «цветами». В простейшем случае, такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично, раскраска ребер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

Рис. 4 Корректная раскраска вершин графа наименьшим набором цветов.