Великая проблема, наконец, опубликована 1 страница
Свое знаменитое открытие Ферма совершил в самом начале своей математической карьеры — около 1637 года. Примерно через тридцать лет, исполняя свои судебные обязанности в городе Кастре, Ферма тяжело заболел. 9 января 1665 года он подписал свой последний приговор и тремя днями позднее умер. Открытиям Ферма, все еще находившегося в изоляции от парижской математической школы и отнюдь не добрым словом поминаемого его разочарованными коллегами, грозило полное забвение. К счастью, старший сын Ферма, Клеман-Самюэль, сознававший все значение любимого увлечения отца, пришел к заключению, что его открытия не должны быть потеряны для всего мира. Всем, что мы знаем о замечательных открытиях Ферма в теории чисел, мы обязаны его сыну, и если бы не Клеман-Самюэль, загадка, известная под названием Великой теоремы Ферма, умерла бы вместе во своим создателем.
Пять лет Клеман-Самюэль собирал отцовские заметки и письма, изучал неразборчивые надписи на полях «Арифметики». Заметка на полях с формулировкой Великой теоремы Ферма была лишь одной из вдохновенных мыслей, начертанных на полях этой книги. Клеман-Самюэль взял на себя тяжкий труд опубликовать все эти заметки в специальном издании «Арифметики». В 1670 году он издал в Тулузе книгу под названием «Диофантова Арифметика, содержащая примечания П. де Ферма». В нее наряду с оригинальным текстом на древнегреческом языке и латинском переводом Баше вошли 48 примечаний, сделанных Ферма. Примечание, воспроизведенное на рис. 6, и было тем, которое стало впоследствии известно под названием Великой теоремы Ферма.
Когда «Примечания» Ферма стали известны более широкому научному сообществу, все поняли, что письма, которые он отправлял своим коллегам, были лакомыми кусочками из сказочного сокровища открытий. Примечания, сделанные рукой Ферма, содержат целую серию теорем. К сожалению, они были либо полностью лишены объяснений, либо сопровождались небольшим наброском доказательства. Часто в этих обрывках доказательств было достаточно изящных логических ходов, чтобы у математиков не оставалось сомнения в том, что Ферма располагал доказательствами. Что же касалось восполнения деталей, то оно всегда было вызовом, который математикам приходилось принимать.
Леонард Эйлер, один из величайших математиков XVIII века, предпринял попытку доказать одно из самых изящных примечаний Ферма — теорему о простых числах. Простым называется число, которое не имеет делителей — чисел, которые делили бы его без остатка, — кроме единицы и самого числа. Например, 13 — простое число, а 14 — не простое. Ни одно число не делит 13 без остатка, а 2 и 7 делят 14. Все простые числа подразделяются на числа, представимые в виде 4n +1, и числа, представимые в виде 4n –1, где n — некоторое целое число. Так, число 13 принадлежит к первой группе (13 = 4·3 + 1), а число 19 — ко второй группе (19 = 4·5–1). Теорема Ферма о простых числах утверждает, что простые числа первой группы всегда представимы в виде суммы двух квадратов (13 = 22 + 32), в то время как простые числа второй группы никогда в виде суммы двух квадратов не представимы (19 =?2 +?2). Это свойство простых чисел формулируется изящно и просто, но все попытки доказать, что им обладает любое простое число, наталкиваются на значительные трудности. Для Ферма это доказательство было всего лишь одним из многих доказательств, хранимых им «приватно», для Эйлера восстановить доказательство стало делом чести. В 1749 году, после семи лет работы и почти через сто лет после смерти Ферма, Эйлеру удалось доказать эту теорему о простых числах.
В сокровищнице полученных Ферма результатов встречаются различные теоремы — от фундаментальных до чисто занимательных. Математики судят о важности теоремы по тому, какое влияние она оказывает на остальную математику. Во-первых, теорема считается важной, если она представляет собой некую универсальную истину, то есть если она верна для всей группы чисел. В случае теоремы Ферма о простых числах, теорема верна не только для некоторых простых чисел, а для всех простых чисел. Во-вторых, важная теорема должна раскрывать какую-нибудь более глубоко лежащую истину об отношениях между числами. Теорема может быть трамплином для создания целого сонма других теорем и даже стимулом для развития новых областей математики. Наконец, теорема считается важной, если существование целых областей исследования может оказаться под угрозой из-за отсутствия одного-единственного логического звена. Многие математики исходили бессильными слезами при мысли, что могли бы получить важный результат, если бы могли восстановить одно недостающее звено в цепочке логических рассуждений.
Поскольку математики используют теоремы как ступени, ведущие к другим результатам, было чрезвычайно важно доказать каждую из анонсированных Ферма теорем. Использовать Великую теорему только потому, что, по утверждению Ферма, он располагал ее доказательством, было невозможно. Прежде чем пустить Великую теорему в дело, ее необходимо было доказать со всей строгостью, иначе последствия могли быть самыми ужасными. Например, представьте себе математиков, которые приняли одну из теорем Ферма на веру. Эта теорема была бы включена ими как отдельный элемент в целую серию других, более обширных, доказательств. Со временем эти более обширные доказательства были бы включены в еще более обширные доказательства, и т. д. В результате появились бы сотни теорем, которые бы опирались на истинность той самой недоказанной, принятой на веру, теоремы. Но что если Ферма ошибся, и недоказанная теорема в действительности ложна? Все теоремы, в доказательствах которых была бы использована ложная теорема, также оказались бы ошибочными, и огромные разделы математики рухнули бы. Теоремы — фундамент математики: если истинность теорем установлена, то, опираясь на них, можно возводить, пребывая при этом в полной безопасности, новые теоремы. Необоснованные (недоказанные) идеи имеют бесконечно меньшую ценность и называются гипотезами. Любая логика, опирающаяся на гипотезу, сама гипотетична.
Ферма утверждал, что располагает доказательством любого из своих примечаний, поэтому для него все они были теоремами. Но до тех пор, пока математическое сообщество в целом не восстановит каждое доказательство, все утверждения, содержащиеся в примечаниях, рассматриваются лишь как гипотезы. На протяжении последних 350 лет Великую теорему Ферма правильнее было бы называть Великой гипотезой Ферма.
За прошедшие столетия одно за другим были доказаны все утверждения Ферма, содержавшиеся в примечаниях на полях «Арифметики» Диофанта, и только Великая теорема Ферма упорно не поддавалась усилиям математиков. Ее даже стали называть «последней теоремой Ферма», так как она осталась последним его примечанием, которое требовалось доказать. Триста лет все попытки найти ее доказательство одна за другой терпели поражение. Великая теорема ферма обрела известность как самая трудная «головоломка» математики. Но всеми признанная трудность проблемы не обязательно означает, что Великая теорема Ферма важна в том смысле, в каком это понимается выше. Великая теорема Ферма, по крайней мере вплоть до самого последнего времени, не удовлетворяла нескольким критериям: казалось, что если бы ее удалось доказать, то это не привело бы ни к какому сколько-нибудь заметному прогрессу в развитии теории чисел и не способствовало бы доказательству других гипотез.
Слава Великой теоремы Ферма обусловлена исключительно тем, что доказать ее необычайно трудно. Есть и еще один дополнительный стимул: «князь любителей» заявил, что располагает доказательством этой теоремы, над восстановлением которой с тех пор ломали голову поколения профессиональных математиков. Небрежные замечания Ферма на полях принадлежавшего ему экземпляра «Арифметики» Диофанта читались как вызов всему миру. Ферма доказал свою Великую теорему, удастся ли какому-нибудь математику превзойти или сравняться с ним по блеску ума?
Г.Г. Харди обладал весьма своеобразным чувством юмора. Как-то раз он задумался, что в математическом наследии прошлого могло бы сравниться с Великой теоремой Ферма по тщетности всех попыток найти доказательство. К найденному им аналогу Великой теоремы Ферма Харди обращался всякий раз, когда ему приходилось преодолевать страх перед морскими путешествиями. Для него это было своего рода страхованием от несчастного случая. Если Харди предстояло пересечь Атлантический океан на борту лайнера, он предварительно посылал кому-нибудь из коллег телеграмму следующего содержания:
ДОКАЗАЛ ГИПОТЕЗУ РИМАНА ТЧК ПОДРОБНОСТИ ПО ВОЗВРАЩЕНИИ ТЧК
Гипотеза Римана — проблема, которой математика «больна» с XIX века. Логика Харди состояла в том, что Бог не даст ему утонуть потому, что тогда математики устремились бы в погоню за еще одним неуловимым призраком.
Великая теорема Ферма — задача невероятно трудная, и тем не менее ее можно сформулировать так, что она станет понятной даже школьнику. Ни в физике, ни в химии, ни в биологии нет ни одной проблемы, которая формулировалась бы так просто и определенно и оставалась нерешенной так долго. В своей книге «Великая проблема» Э.Т. Белл высказал предположение, что возможно, наша цивилизация подойдет к концу прежде, чем удастся доказать Великую теорему Ферма. Доказательство Великой теоремы Ферма стало самым ценным призом в теории чисел, и поэтому не удивительно, что поиски его привели к некоторым наиболее захватывающим эпизодам в истории математики. В эти поиски оказались вовлеченными величайшие умы на нашей планеты, за доказательство назначались огромные премии. Из-за Великой теоремы Ферма люди дрались на дуэли, а некоторые, отчаявшись найти доказательство, даже кончали с собой.
Статус Великой головоломки вышел за рамки замкнутого мира математики. В 1958 году Великая теорема Ферма проникла даже в легенду о Фаусте. В сборнике «Как иметь дело с дьяволом» была опубликована новелла Артура Порджеса «Дьявол и Саймон Флэгг». В ней дьявол обращается к профессору математики Саймону Флэггу с предложением задать ему, дьяволу, какой-нибудь вопрос. Если дьяволу удастся найти ответ за двадцать четыре часа, то он получает душу Саймона. В случае неудачи дьявол обязуется уплатить Саймону 100000 долларов. Саймон задает дьяволу вопрос: «Верна ли Великая теорема Ферма?» Дьявол исчезает и носится по свету, собирая по крохам все достижения математики. На следующий день он возвращается и признает свое поражение: «Вы выиграли, Саймон, — сказал дьявол, почтительно глядя на профессора. — Даже мне не под силу выучить всю математику, которая необходима для решения столь трудной задачи за столь короткое время. Чем глубже я погружаюсь в проблему, тем труднее она становится. Неединственное разложение на множители, идеальные числа… Да что зря говорить! Знаете, — признался дьявол, — даже самые лучшие математики на других планетах, а они, должен вам сказать, намного опередили ваших, не решили ее. Взять хотя бы того парня на Сатурне, что очень похож на гриб на ходулях. Он в уме решает дифференциальные уравнения в частных производных. Так даже он не справился с этой задачей».
Глава 3. Позор математики
Математика — не церемониальный марш по гладкой дороге, а путешествие по незнакомой местности, где исследователи часто рискуют заблудиться. Строгость должна стать указанием для историка о том, что данная местность нанесена на карту, а настоящие исследователи отправились дальше.
У.С. Энглин
«С тех пор, как я еще мальчиком впервые столкнулся с Великой теоремой Ферма, она стала моим увлечением на всю жизнь, — вспоминает Эндрю Уайлс, и его дрогнувший голос выдает тот трепет, с которым он относится к этой задаче. — Я обнаружил, что эта проблема оставалась нерешенной на протяжении трех столетий. Не думаю, чтобы многие из моих школьных друзей подхватили математическую лихорадку, поэтому я не стал обсуждать проблему Ферма с моими одногодками. Но мой учитель математики сам занимался исследованиями, и он дал мне книгу по теории чисел, из которой я почерпнул кое-какие указания относительно того, как приступить к решению проблемы. Прежде всего я решил (и принял это в качестве исходной гипотезы), что Ферма не мог знать намного больше математики, чем я. И я попытался найти его утерянное доказательство, используя те разделы математики, которые мог использовать он сам».
Уайлс был наивным ребенком, преисполненным честолюбивых замыслов, который мечтал достичь успеха там, где потерпели неудачу поколения математиков. Кому-нибудь другому такое намерение могло бы показаться глупой мечтой, но юный Эндрю был совершенно прав, полагая, что он, двенадцатилетний школьник, живущий в XX веке, знает математику в ничуть не меньшем объеме, чем Пьер де Ферма — гений, живший в XVII веке. В своей наивности он действительно мог наткнуться на доказательство, которое пропустили Другие, более искушенные, математики.
Но, несмотря на весь энтузиазм Эндрю, все его попытки доказать Великую теорему Ферма неизменно оканчивались неудачей.
Изрядно поломав голову и подробнейшим образом изучив школьные учебники, он не сумел добиться ничего. После года бесплодных поисков Эндрю решил изменить стратегию и попытаться извлечь что-нибудь полезное для себя из ошибок известных математиков. История Великой теоремы Ферма была необычайно романтичной. Много людей размышляли над ней, и не один великий математик в прошлом пытался доказать ее и потерпел неудачу, отчего Великая проблема становилась все большим вызовом и все большей тайной. «Многие математики XVIII и XIX веков. пытались самыми различными способами доказать Великую теорему Ферма, и я, мальчишка, решил изучить все эти методы и понять, что делали великие математики прошлого».
Юный Уайлс принялся изучать методы всех, кто когда-либо делал серьезную попытку доказать Великую теорему Ферма. И начал он с изучения трудов одного из наиболее плодовитых математиков в истории, которому удалось осуществить первый прорыв в битве с Великой теоремой Ферма.
Математик-циклоп
Создание математики — занятие мучительное и таинственное. Объект доказательства часто бывает ясен, но путь к доказательству теряется в тумане, и математик бредет наощупь, производя выкладки и опасаясь, что каждый шаг может увлечь ход рассуждений в совершенно неверном направлении. Кроме того, всегда существует возможность того, что пути к доказательству вообще не существует. Решив, что некоторое утверждение истинно, математик может годами пытаться доказать его, хотя в действительности это утверждение ложно. По существу, математик в этом случае пытается доказать невозможное.
За всю историю математики лишь горстке математиков удалось избежать такого рода сомнений, которые страшили их коллег. Возможно, наиболее известным из математиков, не ведающих страха и упрека, был живший в XVIII веке математический гений Леонард Эйлер. Именно ему удалось совершить первый крупный прорыв к доказательству Великой теоремы Ферма. Эйлер обладал столь невероятной интуицией и такой обширной памятью, что, по преданию, мог держать в голове весь объем производимых вычислений, не прикасаясь пером к бумаге. Вся Европа называла его «прирожденным аналитиком», а французский академик Франсуа Араго сказал о нем: «Эйлер вычислял без видимых усилий, как люди дышат или как орлы парят в поднебесье».
Леонард Эйлер родился в Базеле в 1705 году в семье кальвинистского пастора Пауля Эйлера. Хотя юный Эйлер проявил недюжинный математический талант, его отец решил, что сын должен изучать теологию, и готовил ему церковную карьеру. Леонард повиновался отцовской воле и стал изучать теологию и древнееврейский язык в Базельском университете.
К счастью для Эйлера, Базель был родиной знаменитого клана Бернулли. Бернулли могли бы с полным основанием претендовать на звание самого математического рода: восемь представителей семьи Бернулли принадлежали к числу самых выдающихся умов Европы на протяжении всего лишь трех поколений. Говорили, что семья Бернулли стала для математики тем же, чем семья Баха была для музыки. Слава рода Бернулли распространилась за пределы математического сообщества, и одна легенда ярко рисует «профиль» семейства. Однажды Даниил Бернулли путешествовал по Европе и вступил в беседу с незнакомцем. Спустя какое-то время он скромно представился своему собеседнику: «Я — Даниил Бернулли». «А я, — саркастически ответил тот, — Исаак Ньютон». Даниил охотно вспоминал этот случай несколько раз, считая его самым искренним признанием своих заслуг, которое ему когда-либо довелось получать.
Даниил и Николай Бернулли были близкими друзьями Леонарда Эйлера, и они первыми поняли, что на их глазах происходит превращение блестящего математика в самого заурядного теолога. Они обратились к Паулю Эйлеру и упросили его разрешить Леонарду оставить теологию ради чисел. Эйлер-старший сам в прошлом изучал математику у старшего Бернулли, Якоба, и испытывал к семье Бернулли глубочайшее почтение. С большой неохотой Пауль Эйлер был вынужден признать, что его сын рожден не для молитв, а для вычислений.
Вскоре Леонард Эйлер покинул Швейцарию, сменив родной Базель на дворцы Берлина и Санкт-Петербурга, где он и провел бóльшую часть своей творческой жизни. В эпоху Ферма математиков считали любителями жонглировать числами, но к началу XVIII века их уже рассматривали как профессиональных «решателей задач». Культура чисел резко изменилась, и произошло это отчасти благодаря сэру Исааку Ньютону и его научным результатам.
Ньютон полагал, что математики лишь впустую тратят время, поддразнивая друг друга пустыми и никчемными задачами-головоломками. Вместо этого он вознамерился применять математику к физическому миру и вычислять все, что только можно, — от орбит планет до траекторий пушечных ядер. К тому времени, когда Ньютон умер (это произошло в 1727 году), в Европе произошла научная революция. В тот же год Эйлер опубликовал свою первую работу. И хотя она содержала изящные и свежие математические идеи, ее главная цель состояла в описании решения одной технической проблемы, связанной с постановкой мачт на парусных кораблях.
Европейские державы не были заинтересованы в использовании математики для изучения эзотерических и абстрактных понятий; математика была им необходима для решения практических проблем, и правительства состязались в привлечении к себе на службу лучших умов. Эйлер начал свою математическую карьеру в России, затем его пригласил в Берлинскую академию король Пруссии Фридрих Великий. В царствование Екатерины Великой Эйлер вернулся в Россию, где он и провел последние годы жизни. За годы своей деятельности Эйлер решил множество задач из самых различных областей — от навигации до финансов, от акустики до ирригации. Практический мир решения насущных проблем не притупил математические способности Эйлера. Наоборот, для решения каждой новой проблемы Эйлер изобретал новый остроумный математический подход. Столь «односторонняя» направленность его ума приводила к тому, что в иной день Эйлеру случалось писать по несколько работ. Рассказывают, что между первым и вторым приглашением к обеденному столу Эйлер как-то раз попытался выполнить вычисления, заслуживающие публикации. Эйлер не терял ни минуты. Укачивая одной рукой младенца в колыбели, он другой рукой набрасывал доказательство теоремы.
Одним из величайших достижений Эйлера стала разработка алгоритмического мышления. Отличительная особенность эйлеровских алгоритмов состояла в том, что они предназначались для решения проблем, казавшихся неразрешимыми. Одной из таких проблем было высокоточное предсказание фаз Луны — информация о фазах Луны имела жизненно важное значение для составления таблиц, необходимых для мореплавания. Еще Ньютон показал, что можно сравнительно легко предсказывать орбиту одного тела, обращающегося вокруг другого, но в случае Луны ситуация не столь проста.
Луна обращается вокруг Земли, но третье тело — Солнце — существенно усложняет картину. Земля и Луна притягивают друг друга, а Солнце возмущает положение Земли и сталкивает Луну с ее идеальной орбиты вокруг Земли. Уравнения позволяли описать поведение Земли и Луны, но математики XVIII века не умели учитывать в своих вычислениях влияние третьего тела. Даже сегодня невозможно предсказать, как будет вести себя точное решение этой задачи (класс таких задач называется «задачей трех тел»). Эйлер понял, что мореплавателям нет необходимости знать фазу Луны с абсолютной точностью — вполне достаточно такой точности, которая позволяет определить положение судна с точностью до нескольких морских миль. И он разработал рецепт, позволяющий получать не идеальное, а достаточно точное решение. Такой рецепт, называемый алгоритмом, позволяет получить сначала весьма приближенное, грубое решение. Затем это решение можно ввести в качестве исходных данных в тот же алгоритм и получить уже более точное решение. В свою очередь, уточненное решение, если его также ввести в алгоритм, порождает еще более точное решение, и т. д. После ста или около того итераций Эйлер получил возможность определить положение Луны с точностью, достаточной для нужд мореплавания. Свой алгоритм Эйлер представил британскому Адмиралтейству и получил награду в триста фунтов стерлингов.
Эйлер заслужил репутацию человека, способного решить любую поставленную ему задачу, причем не только математическую. В бытность свою при дворе Екатерины Великой он встретил великого французского философа Дени Дидро. Тот был убежденным атеистом и пытался обратить в атеизм представителей русской знати. Разгневанная этим Екатерина обратилась к Эйлеру с просьбой пресечь деятельность французского безбожника.
Эйлер поразмыслил над просьбой императрицы и объявил, что располагает алгебраическим доказательством существования Бога. Екатерина Великая пригласила Эйлера и Дидро во дворец и собрала на теологический спор всех придворных. Эйлер встал перед аудиторией и заявил:
«Сир! (a + bn )/n = x , следовательно Бог существует. Что Вы имеете возразить?»
Дидро не был силен в алгебре и не мог ничего возразить величайшему математику Европы. Ему оставалось только безмолвствовать. Потерпев унизительное поражение, он покинул Санкт-Петербург и вернулся в Париж. Эйлер же на какое-то время вернулся к занятиям теологией и опубликовал еще несколько шутливых доказательств относительно природы Господа Бога и человеческого духа.
Более «земная» задача, привлекшая внимание Эйлера, большого любителя головоломных проблем, связана с прусским городом Кёнигсбергом (ныне — российский город Калининград). Город стоит на берегах реки Прегили и состоит из четырех частей, соединенных между собой семью мостами. План города схематически изображен на рис. 7. Некоторые из любопытных жителей Кенигсберга заинтересовались, можно ли обойти все семь мостов, не переходя ни по одному из них дважды. Кое-кто из обитателей Кенигсберга попытался проложить различные маршруты, но ничего хорошего из этого не вышло. Эйлеру также не удалось обойти все семь кёнигсбергских мостов, побывав на каждом только один раз, но зато он сумел объяснить, почему сделать это невозможно.
Рис. 7. Река Прегиль делит Кёнигсберг на четыре несвязанные части A, B, C и D. Различные части города соединены между собой семью мостами. Можно ли обойти все семь мостов побывав на каждом один и только один раз?
Рис. 8. Упрощенная схема семи кёнигсбергских мостов
Эйлер взял план города и заменил его упрощенной схемой, на которой части города изображены точками (узлами), а мосты — линиями (ребрами), как на рис. 8. Затем Эйлер стал рассуждать так. Чтобы существовал маршрут, позволяющий обойти ровно по одному разу все мосты, каждая точка на схеме должна принадлежать четному числу линий. Это связано с тем, что в середине обхода путешественник, проходя какую-то из частей города, должен войти в нее по одному мосту, а выйти — по другому. Из этого правила существуют лишь два исключения: когда путешественник начинает или завершает обход. В самом начале обхода путешественник покидает некую часть города, и для выхода из нее необходим только один-единственный мост. Если обход начинается и заканчивается в различных частях города, то число мостов, ведущих к каждой из них нечетно. Но если обход начинается и заканчивается в одной и той же части города, то соответствующая ей точка на схеме, как и все другие точки, должна принадлежать четному числу линий (т. е. эта часть города должна быть соединена с другими частями четным числом мостов).
Таким образом, заключил Эйлер, какой бы ни была сеть мостов, обойти все мосты, побывав на каждом по одному и только одному разу, можно только в том случае, если все части города соединены с другими четным числом мостов или если ровно две части города соединены с другими частями нечетным числом мостов. В Кенигсберге город подразделяется всего на четыре части, — и все они соединены с другими частями нечетным числом мостов. На схеме Кенигсберга три точки принадлежат трем линиям, а одна — пяти линиям. Тем самым Эйлер не только сумел объяснить, почему все семь кёнигсбергских мостов невозможно обойти, побывав на каждом один и только один раз, но и придумал правило, применимое к любой сети мостов в любом городе мира. Рассуждения Эйлера отличаются замечательной красотой. По-видимому, такого сорта логические задачи Эйлер и любил решать за обедом.
Задача о семи кёнигсбергских мостах принадлежит к числу так называемых задачах о графах в прикладной математике. Именно она побудила Эйлера к рассмотрению более абстрактных графов. В ходе своих исследований Эйлер открыл фундаментальную истину, относящуюся ко всем графам, — так называемую формулу Эйлера для графов, которую ему удалось доказать за несколько логических шагов. Формула Эйлера для графов выражает незыблемое соотношение между тремя элементами любой графа:
V — R + L = 1,
где
V — число вершин (узлов, или пересечений) в графе,
R — число линий (ребер) в графе,
L — число замкнутых областей в графе.
Таким образом, по утверждению Эйлера, если к числу вершин любого графа прибавить число замкнутых областей и вычесть число его ребер — результат всегда окажется равен единице. Например, все графы на рис. 9 удовлетворяют формуле Эйлера.
Вершины = 4
Области = 3
Линии = 6
Вершины = 6
Области = 1
Линии = 6
Вершины = 5
Области = 10
Линии= 6
Рис. 9. Различные графы, удовлетворяющие формуле Эйлера
Рис. 10. Эйлер доказал свою формулу для графов, продемонстрировав, что она выполняется для простейшего графа, а затем показав, что формула остается верной при любых «дополнениях» к единственной вершине
Можно проверить формулу Эйлера на целой серии графов, и всякий раз она оказывается верной; возникает искушение предположить, что формула Эйлера верна для всех графов. И хотя такой проверки было бы достаточно для физической теории, для обоснования математической теории ее совершенно недостаточно. Единственный способ показать, что формула Эйлера остается в силе для любого мыслимого графа, — построить безупречное с точки зрения логики доказательство. Именно так и поступил Эйлер.
Свое доказательство Эйлер начал с простейшего из графов — с графа, состоящего из одной единственной вершины (рис. 10а ). Ясно, что для такого графа формула Эйлера верна: имеется всего одна вершина, линий и областей нет, поэтому
V + R — L = 1 + 0–0 = 1 .
Затем Эйлер рассмотрел вопрос о том, что произойдет в том случае, если он что-нибудь добавит к этому простейшему графу. Любое добавление к нему требует добавления линии. Любая линия может соединять существующую вершину либо с самой собой, либо с какой-нибудь новой вершиной.
Во-первых, рассмотрим случай, когда дополнительная линия соединяет существующую вершину с самой собой. Как видно из рис. 10б , при добавлении линии в этом случае добавляется также новая область. Следовательно, формула Эйлера для графов остается в силе, так как добавление одной области (+) компенсируется добавлением одной линии (—). При добавлении новых линий того же типа формула Эйлера для графов также останется в силе, так как каждая новая линия порождает новую область.
Во-вторых, рассмотрим, что произойдет, если дополнительная линия соединит существующую вершину с новой вершиной, как на рис. 10в . И в этом случае формула Эйлера остается в силе, так как новая вершина (+) компенсирует новую линию (—). При добавлении новых линий того же типа формула Эйлера также остается в силе, поскольку каждая дополнительная линия рассматриваемого типа заканчивается в новой вершине.
Вот и все, что требовалось Эйлеру для его доказательства. Он рассуждал так. Формула верна для простейшего из всех графов — одной-единственной вершины. Все остальные графы, сколь бы сложными они ни были, могут быть построены из простейшего путем прибавления линий — по одной линии за один раз. Всякий раз при добавлении к графу новой линии формула остается верной, потому что вместе с линией добавляется либо новая вершина, либо новая область, и тем самым компенсируется добавление линии. Эйлер разработал простую, но мощную стратегию. Он доказал, что его формула верна для простейшего графа, состоящего из одной-единственной вершины, и что любая операция, приводящая к усложнению графа, не нарушает формулу для графов. Следовательно, формула верна для бесконечного множества всех возможных графов.