Даже сегодня невозможно предсказать, как будет вести себя точное решение этой задачи (класс таких задач называется «задачей трех тел»). Эйлер понял, что мореплавателям нет необходимости знать фазу Луны с абсолютной точностью — вполне достаточно такой точности, которая позволяет определить положение судна с точностью до нескольких морских миль. И он разработал рецепт, позволяющий получать не идеальное, а достаточно точное решение. Такой рецепт, называемый алгоритмом, позволяет получить сначала весьма приближенное, грубое решение. Затем это решение можно ввести в качестве исходных данных в тот же алгоритм и получить уже более точное решение. В свою очередь, уточненное решение, если его также ввести в алгоритм, порождает еще более точное решение, и т. д. После ста или около того итераций Эйлер получил возможность определить положение Луны с точностью, достаточной для нужд мореплавания. Свой алгоритм Эйлер представил британскому Адмиралтейству и получил награду в триста фунтов стерлингов.
Эйлер заслужил репутацию человека, способного решить любую поставленную ему задачу, причем не только математическую. В бытность свою при дворе Екатерины Великой он встретил великого французского философа Дени Дидро. Тот был убежденным атеистом и пытался обратить в атеизм представителей русской знати. Разгневанная этим Екатерина обратилась к Эйлеру с просьбой пресечь деятельность французского безбожника.
Эйлер поразмыслил над просьбой императрицы и объявил, что располагает алгебраическим доказательством существования Бога. Екатерина Великая пригласила Эйлера и Дидро во дворец и собрала на теологический спор всех придворных. Эйлер встал перед аудиторией и заявил:
«Сир! (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 .
Затем Эйлер рассмотрел вопрос о том, что произойдет в том случае, если он что-нибудь добавит к этому простейшему графу.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
Эйлер заслужил репутацию человека, способного решить любую поставленную ему задачу, причем не только математическую. В бытность свою при дворе Екатерины Великой он встретил великого французского философа Дени Дидро. Тот был убежденным атеистом и пытался обратить в атеизм представителей русской знати. Разгневанная этим Екатерина обратилась к Эйлеру с просьбой пресечь деятельность французского безбожника.
Эйлер поразмыслил над просьбой императрицы и объявил, что располагает алгебраическим доказательством существования Бога. Екатерина Великая пригласила Эйлера и Дидро во дворец и собрала на теологический спор всех придворных. Эйлер встал перед аудиторией и заявил:
«Сир! (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 .
Затем Эйлер рассмотрел вопрос о том, что произойдет в том случае, если он что-нибудь добавит к этому простейшему графу.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81