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

рис. 2 3. Задача о четырех красках.

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

 

3 2 2 3 3 3

3 3 4 4 2 3 3

Доказательство . Пусть a 1 , a 2 , a 3 , …, a k — это степени четных вершин графа, а b 1 , b 2 , b 3 , …, b m — степени нечетных вершин графа. Сумма a 1 + a 2 + a 3 +…+ a k + b 1 + b 2 + b 3 +…+ b m ровно в два раза превышает число ребер графа. Сумма a 1 + a 2 + a 3 +…+ a k четная (как сумма четных чисел), тогда сумма b 1 + b 2 + b 3 +…+ b m должна быть четной. Это возможно лишь в том случае, если m — четное, то есть четным является и число нечетных вершин графа. Что и требовалось доказать. Эта теорема имеет немало любопытных следствий. 

Доказательство . Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2, ..., ( n - 1 ). Предположим, что в некотором графе все его вершины имеют различную степень, то есть, и покажем, что этого быть не может. Действительно, если р(А)=0, то это значит, что А — изолированная вершина, и поэтому в графе не найдется вершины Х со степенью р(Х)= n - 1. В самом деле, эта вершина должна быть соединена с ( n - 1) вершиной, в том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе, имеющем n вершин, не могут быть одновременно вершины степени 0 и (n-1). Это значит, что из n вершин найдутся две, имеющие одинаковые степени. 

Доказательство . Воспользуемся формулой Эйлера : В-Р+Г=2, где В — число вершин плоского графа, Р — число его ребер, Г — число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого. Эту формулу можно доказать методом математической индукции. Это доказательство мы опускаем. Заметим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с другом . Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если через 1 обозначить число таких граней, то 2 =0. Далее рассуждаем от противного, а именно: предположим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В =5, число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7. Это число можно представить в виде суммы : Г = 1 + 2 + 3 +…, где 3 – число граней, ограниченных тремя ребрами, 4 — число граней, ограниченных четырьмя ребрами и т. д. С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р =20= 3 3 + 4 4 +... . Умножив равенство Г=7= 3 + 4 + 5 + … на три, получим ЗГ=21=3( 3 + 4 + 5 + …). Ясно, что (3 3 +3 4 +3 5 +…) 3 +4 4 + 5 5 +…) или 3Г