Дискретная математика:
логика, группы, графы, фракталыАкимов О.Е.
3.5. Раскраска графов и вопросы топологии
Аналогия с Великой теоремой Ферма
История с задачей о четырех красках и поиск ее решения, как мы сказали, чем-то напоминает историю с Великой теоремой Ферма. Подобно тому, как теорема Ферма стимулировала прогресс не только в теории чисел, но и в алгебре в целом, точно так же задача о красках дала толчок к развитию не только теории графов, но и топологии и всех наук, связанных с пространственными представлениями. Дело в том, что число четыре однозначно продиктовано топологическими свойствами плоской или сферической поверхности, на которой наносятся карты. Геометры задумались: что будет, если эту задачу перенести на поверхность тора? Затем они модифицировали задачу, задавшись вопросом о раскраске ребер графа, ввели множество полезных понятий, в частности, понятие о хроматическом числе. Его определение звучит так: если никакие две смежные вершины в графе не получают одну и ту же метку, в роли которой — так уж исторически сложилось — выступает краска определенного цвета, то число различных меток для данного графа называется хроматическим.
Теорема Пьера Ферма (1601—1665) убеждает нас, какие порой колоссальные усилия уходят на доказательства индуктивно открытых математических истин. На полях трактата древнегреческого математика Диофанта «Арифметика» Ферма написал формулу zn = xn + yn и заметил: «Невозможно разложить куб на два куба, или биквадрат на два биквадрата, или вообще степень, большую двух, на две степени с тем же самым показателем». Это-то утверждение математики и окрестили Последней, Великой или Большой теоремой Ферма. После формулировки теоремы Ферма добавил: «Я нашел чудесное доказательство этой теоремы, но для его записи здесь слишком мало места». Математик умер, унеся в могилу тайну своей записи на полях книги. С тех пор ученые мира пытались доказать, что уравнение
zn = xn + yn , при xyz ≠ 0 и n > 2
не имеет целочисленного решения.
Делая заметки на полях, Ферма наверняка не знал правильного доказательства. После смерти математика в его бумагах было найдено правильное доказательство теоремы только для самого элементарного случая, когда n = 4 (даже для n = 3, более сложного, он доказать не смог). Историки математики прекрасно знают, что Ферма нередко ошибался, например, он ошибочно утверждал, что все числа вида (2^2)^n + 1 являются простыми. Эйлер показал, что число, отвечающее этой формуле при n = 5, будет уже составным. Так что нет ничего удивительного в ошибочности утверждения Ферма, оставленного им на полях «Арифметики» Диофанта.
Имя Ферма прилепилось к этой теореме достаточно случайно, поскольку задолго до него, еще в античной Греции, математики размышляли над расширением теоремы Пифагора. И только потому, что французский математик оставил столь претенциозную записку на полях книги Диофанта, теорема стала носить его имя. Это напоминает историю с кометой Галлея. Английский астроном Эдмунд Галлей вместе с геометром, как тогда говорили, Исааком Ньютоном считал, что все кометы двигаются по прямым. Королевский астроном, Джон Флемстид, в течение нескольких лет доказывал им, что они ошибаются и кометы двигаются по эллипсам. Флемстид жутко пострадал от этих двух высокомерных британцев и это при том, что никто лучше его не мог рассчитать траекторию небесного тела, включая комету Галлея. Однако Судьба оказалась несправедлива к Флемстиду. Все думают, что Галлей и Ньютон распространили первый закон Кеплера на кометы, хотя всё было ровно наоборот: вопреки мнению большинства тогдашних астрономов эти двое затеяли совершенно бессмысленный спор с уважаемым астрономом.
История доказательства теоремы Ферма очень долгая и занимательная. В 1768 году Эйлер доказал теорему Ферма для n = 3. В 1825 году она была доказана для n = 5 независимо друг от друга двумя математиками – Дирихле и Лежандром. В 1847 Ламе доказал ее для n = 7. Куммер, Гильберт и ряд других математиков решили эту проблему для определенных классов чисел. Уже Эйлер знал, что среди степеней необходимо выделять такие значения n, при которых ни одно из чисел x, y, z не делится на n. Этот критерий лег в основания так называемого первого случая теоремы Ферма, остальные значения n попали во второй случай. Лежандр показал, что первый случай теоремы Ферма справедлив для простого показателя, если хотя бы одно из пяти чисел 4n + 1, 8n + 1, 10n + 1, 14n + 1 и 16n + 1 является простым числом. Таким образом, для первого случая теорема Ферма была доказана для всех показателей n < 197.
Сейчас я не могу вдаваться в детали, поэтому опишу ситуацию в общих словах. Интерес к теореме Ферма то поднимался, то падал, соответственно, успехи в продвижении ее доказательства были неравномерными. В середине XIX века Парижская академия наук учредила награду в 3000 франков за доказательство теоремы. И хотя теорема не была доказана, объявление денежного приза сильно стимулировало работы в этом направлении. В конце концов, в 1857 году объявленную сумму Академия вручила Куммеру за его цикл математических работ по теории чисел. Затем, в 1908 году состоятельный немецкий любитель математики, Вольфскель, завещал сто тысяч марок тому, кто докажет теорему (сам он долгие годы бился над ее доказательством). Эта премия тоже оказала сильнейшее воздействие. За три года в Геттингенское математическое общество пришло более тысячи работ, связанных с доказательством теоремы Ферма. Таким образом, доказательство теоремы не было одномоментным актом, сравнимым с чудом. К середине XX века общими усилиями математиков мира проблема была решена для всех без исключения степеней, не превышающих границу, пролегающую где-то в районе n = 100 000. При этом существовали особые классы чисел, которые простирались неограниченно далеко за пределы указанной границы.
Наконец, 23 июня 1993 г. на математической конференции в Кембридже (Великобритания) математик из Принстона Эндрю Уайльс анонсировал доказательство так называемой гипотезы Таниямы. Посвященные знают, что доказательство неподдающейся теоремы Ферма сводится к другой задаче, которую уже можно решить. Аналогичная ситуация была, как мы знаем, и с задачей о красках, которую не удалось взять приступом в лобовой атаке. Японский математик Танияма в 1955 г. предложил обходной путь для доказательства теоремы Ферма. Он звучит примерно так: «Всякая эллиптическая кривая с рациональными коэффициентами является модулярной».
Не станем вдаваться в детали этой гипотезы и аналитическое доказательство теоремы; заинтересованного читателя мы отсылаем к книге М. А. Еремина «Последняя теорема Ферма», где он может ознакомиться с громоздкими математическими выкладками. Лучше обратим внимание читателей на обыкновенный математический факт. Никто, пожалуй, из наших читателей не скажет, какая цифра стоит на сотом месте после запятой у числа π. Однако не составит большого труда ее найти, поскольку существует компьютерная программа для вычисления этого трансцендентного числа с огромной, заранее заданной точностью. То же самое относится и к теореме Ферма. Всякий студент способен составить несложную компьютерную программу поиска решения вышеозначенного уравнения. Мощный «Пентиум» можно заставить работать круглосуточно в течение месяца, и тогда значения чисел x, y, z превысят все разумные пределы. Если на экране монитора не появилось чисел, удовлетворяющих кубическому уравнению, о котором говорил Ферма, значит, его утверждение справедливо.
Между тем, перепрограммировав задачу на теорему Пифагора:
x² + y² = z²,
компьютер с первых же мгновений своей работы начнет выдавать бесконечный ряд числовых значений:
x = 3 8 12 16 20 24 28 32 36 40 ... y = 4 15 35 63 99 143 143 255 323 399 ... z = 5 17 37 65 101 145 145 257 325 401 ... Обратите внимание, кроме первого, во всех остальных столбцах y отличается от z на 2. Случайность? Нет, здесь многое зависит от алгоритма поиска чисел, удовлетворяющих теореме Пифагора. Умело составленная программа нашла бы, что для больших z имеется несколько значений x и y, например:
100² = 28² + 96² = 60² + 80²,
1000² = 600² + 800² = 280² + 960² = 352² + 936²,
50000000² = 30000000² + 40000000² = 48923520² + 10319360² =
= 37609600² + 32947200² = 42160000² + 26880000² =
= 46800000² + 17600000² и т.д.
Теорема Пифагора не распространяется на кубы, но для уравнения вида x³ + y³ = z³ – 1³ найдется множество решений:
x = 8 71 242 575 1124 1943 3086 4607 6560 8999 ... y = 6 138 720 2292 5610 11646 21588 36840 59022 89970 ... z = 9 144 729 2304 5625 11664 21609 36864 59049 90000 ... И для других аналогичных выражений компьютер быстро найдет решения, начиная с самых первых чисел, в частности, для
x³ + y³ = z³ – 2³
x = 16 142 484 1150 2248 3886 6172 9214 17998 23956 ... y = 12 276 1440 4584 11220 23292 43176 73680 179940 263472 ... z = 18 288 1458 4608 11250 23328 43218 73728 180000 263538 ... x³ + y³ = z³ – 3³
x = 24 213 726 1725 3372 5829 9258 13821 ... ... ... y = 18 414 2160 6876 16830 34938 64764 110520 ... ... и т.д. z = 27 432 2187 6912 16875 34992 64827 110592 ... ... ... Почему нужно ожидать нарушений теоремы Ферма на астрономически больших числах, если она не была опровергнута в пределах сотни или тысячи? Если равенство x³ + y³ = z³ – 1³ выполняется уже на числах 6, 8, 9, то почему равенство x³ + y³ = z³, отличающееся от первого на единицу, должно выполняться на числах, недоступных компьютеру?
Мы не выступаем против формально-логических доказательств — они, конечно, нужны, — но нельзя же пренебрегать очевидной математической реальностью. Если практика показывает справедливость какого-то математического выражения, то почему им не пользоваться, по крайней мере, до той поры, пока оно не будет опровергнуто формально-логическим способом. Позиция конструктивно настроенного математика должна состоять в «презумпции невиновности» математического выражения, если в практической жизни оно не было изобличено в обратном. Строгость, которой кичатся отдельные формалисты, часто оборачивается какой-то особой интеллектуальной формой мазохизма, или, во всяком случае, самой нездоровой психической аномалией. Всевластие формализма порой сдерживает нормальное развитие науки, мешает движению вперед по пути прогресса. Между тем многие так называемые формально-логические доказательства опираются на конкретные вычислительные процедуры, на которых и держится конструктивный подход.
В самом деле, разве Аппель и Хейкен при решении задачи о четырех красках не пользовались той же вычислительной методикой, что и наш гипотетический студент при проверке уравнения Ферма? Разница заключается только в том, что первым повезло больше, так как множество неприводимых конфигураций оказалось конечным, тогда как студент перебирал бесконечный ряд чисел. Но доказательство Уайльса свелось к тому же, что и доказательство Аппеля и Хейкена — к разбиению бесконечного натурального ряда на конечное число классов и к демонстрации справедливости теоремы Ферма для каждого из классов. Таким образом, под логическими доказательствами часто маскируются обыкновенные вычислительные процедуры или операционные действия, продиктованные элементарным здравым смыслом.
Под последним имеется в виду следующее. Почему никто не берется доказывать, что отрезок имеет два и только два конца, а не один или три? Почему число вершин в остове любого графа на единицу больше числа его ребер? Почему в той же задаче о раскраске карты четырьмя цветами бездоказательно утверждается, что соседними могут стать только три страны, т.е. почему степень узловых точек графа границ равна трем? На все эти вопросы можно сказать: такова геометрическая данность, которую нет нужды доказывать логическими средствами. Между тем сущность поставленных вопросов та же, что и в проблеме с четырьмя красками; в последней нисколько не больше математической тайны, чем в трех предыдущих. Политическая карта насчитывает много стран, которые трудно охватить единым взором. Но для 4, 5 или 6 государств проблема становится столь же очевидной, как и подсчет числа концов у отрезка. Чем больше элементов затрагивается в данной конкретной ситуации, тем сложнее ее представить. Но продолжением воображения является действие, а оно доказывает, что четырех красок для раскраски вполне достаточно, сколько бы ни было стран на карте.
В любом случае дедуктивные рассуждения всегда идут позади воображения и действия, которые добывают истину, логика же последовательно разъясняет то, что возникло у нас в голове в результате интуитивного представления. Вот еще пример, подтверждающий эту простую мысль. Число ребер в графе, как нам известно, определяется полусуммой всех степеней его вершин. Какое здесь нужно доказательство? Практически никакого, так как каждый усматривает у ребра две вершины, не больше и не меньше, стало быть, на каждое ребро приходится по две степени. Из представления и только из него проистекает простая формула сложения всех степеней и деления этой суммы пополам.
После такой гимнастики ума нам будет несложно вообразить себе, что для покраски вершин произвольно взятого графа, степень которых не превосходит числа n, требуется n + 1 цветов. Рассуждаем следующим образом: каждая вершина графа может через ребро контактировать не более чем с n вершинами, которые в самом неблагоприятном для нас случае раскрашены в n цветов; отсюда возникает число n + 1, поскольку для нашей конкретно выбранной вершины потребуется еще один цвет. Регулярный граф-границ имеет вершины степени три, значит, для покраски его вершин потребуется не более четырех красок. Если эти представления облечь в символические одежды, получится формально-логическое доказательство важного положения теории графов. Но без пространственного образа это доказательство будет походить на эзотерические арканы древнеегипетских жрецов.
|
|
