Русская Википедия:Задача о семи кёнигсбергских мостах
Зада́ча о кёнигсбе́ргских моста́хШаблон:SfnШаблон:SfnШаблон:Sfn (Шаблон:Lang-laШаблон:SfnШаблон:Sfn, Шаблон:Lang-enШаблон:SfnШаблон:SfnШаблон:Sfn, Шаблон:Lang-deШаблон:SfnШаблон:Sfn) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам центра старого Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в статье, датированной 1736 годомШаблон:SfnШаблон:Sfn, математиком Леонардом Эйлером, который доказал, что это невозможно, и по ходу доказательства изобрёл эйлеровы циклы. Решение Эйлером задачи о кёнигсбергских мостах явилось первым в истории применением теории графов, но без использования термина «граф» и без рисования диаграмм графов.
История
В центре Кёнигсберга (ныне Калининград) на реке Прегель (ныне Преголя) находятся два острова: Кнайпхоф (ныне остров Иммануила Канта) и Ломзе (ныне Октябрьский остров). На берегах Прегеля к северу от острова Кнайпхоф расположен Альтштадт, к югу — Форштадт. Были построены мосты через Прегель, соединяющие эти четыре районаШаблон:Sfn. На рисунке справа показан центр Кёнигсберга на карте 1652 года с обозначениями: А — Альтштадт, Б — Кнайпхоф, В — Ломзе и Г — Форштадт.
История строительства мостов Кёнигсберга
Семь первых мостов центра Кёнигсберга, соединяющие Альтштадт, Кнайпхоф, Ломзе и Форштадт, были построены в указанные ниже годы в следующем порядкеШаблон:Sfn. Номера мостов в порядке их постройки показаны на рисунке справа.
1. Лавочный мост (1286)
Первый мост Кёнигсберга датируется 1286 годом. Соединил Альтштадт и Кнайпхоф. Принадлежал городу Альтштадт и обеспечивал городу легкий доступ к рынкам КнайпхофаШаблон:Sfn.
2. Зелёный мост (1322)
Второй мост Кёнигсберга построен в 1322 году. Соединил Кнайпхоф с Форштадтом и обеспечил легкий доступ к удалённым районам. Мост назывался Зелёным из-за зелёных волн, которые служат фоном герба КнайпхофаШаблон:Sfn.
3. Рабочий мост (1377)
В XIV веке на востоке Форштадта была скотобойня. Чтобы облегчить транспортировку мяса, в 1377 году между Кнайпхофом и Форштадтом был построен третий мостШаблон:Sfn.
4. Кузнечный мост (1397)
в 1397 году в северо-восточной части Кнайпхофа был построен четвёртый Кузнечный мост, который начинался недалеко от кузнечных мастерских в АльтштадтеШаблон:Sfn.
Если по этим четырём мостам нарисовать граф, то он будет эйлеровым, то есть все четыре моста можно обойти по одному разу по замкнутому маршруту, начиная с любого места. Жители могли совершать такие прогулкиШаблон:Sfn.
5. Деревянный мост (1404)
На острове Ломзе заготавливали древесину, и пятый мост между Альтштадтом и Ломзе, построенный между 1400 и 1404 годами, облегчил доставку древесиныШаблон:Sfn.
6. Высокий мост (1506)
Шестой мост был построен в 1506 году, чтобы соединить Ломзе и ФорштадтШаблон:Sfn.
7. Медовый мост (1542)
Седьмой из мостов Эйлера, соединивший оба острова, был завершен в 1542 году. Он был построен жителями Кнайпхофа для прохождения на северный берег, минуя два моста из Кнайпхофа, контролируемые Альтштадтом. Согласно легенде, Кнайпхоф передал бочку меда Альтштадту, чтобы получить разрешение на строительство мостаШаблон:Sfn.
Итак, в 1542 году все семь мостов Кёнигсберга, рассмотренных Эйлером, были на месте. Теперь жители не могли обойти все мосты за один разШаблон:Sfn.
История задачи
Возникновение раздела математики теория графов связано с математическими головоломками, и некоторое достаточно продолжительное время теория графов была «несерьёзна» и целиком связана с играми и развлечениями. Такая судьба теории графов повторяет судьбу теории вероятностей, также сначала находившей себе применение только в азартных играхШаблон:Sfn.
Жители Кёнигсберга играли в своего рода игру: как пройти по всем городским мостам так, чтобы маршрут не пролегал ни по одному из них дваждыШаблон:Sfn. «Как я слышал, — писал Леонард Эйлер, — некоторые отрицают, что это можно сделать, другие сомневаются, но никто не подтверждает такой возможности.Шаблон:Sfn»
История публикации статьи Леонарда Эйлера
Леонард Эйлер, выдающийся швейцарский, прусский и русский Шаблон:Математик и Шаблон:Механик, академик Петербургской академии наук заинтересовался этой игрой. История публикации знаменитой статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения», написанной в связи с этим, имеет следующие известные по современным публикациям этапы:
- сначала Шаблон:СС3Шаблон:Sfn Эйлер представил статью на Конференции Петербургской академии наукШаблон:Sfn;
- затем в 1736 году Эйлер, в рамках своей научной переписки, отправил два следующих письма:
- Шаблон:СС3 — письмо Шаблон:Iw, австрийскому астроному и математику, от 13 [24] марта 1736 года, Петербург. Это письмо целиком посвящено задаче о кёнигсбергских мостахШаблон:SfnШаблон:Sfn;
- Шаблон:СС3 — письмо Шаблон:Iw, немецкому политическому деятелю и астроному, от 3 [14] апреля 1736 года, Петербург. В конце этого письма идёт речь об основных идеях статьиШаблон:SfnШаблон:Sfn;
- в 1741 году в Санкт-Петербурге наконец вышла статья Эйлера на латинском языке с датой 1736 годаШаблон:SfnШаблон:Sfn:
Шаблон:Начало цитаты Leonhardus Eulerus. Solutio problematis ad geometriam situs pertinentis / Commentarii academiae scientiarum Petropolitanae. 8 (1736). 1741. P. 128—140. Шаблон:Конец цитаты В переводеШаблон:Sfn: Шаблон:Начало цитаты Леонард Эйлер. Решение одной задачи, связанной с геометрией положения / Труды Петербургской академии наук. 8 (1736). 1741. С. 128—140. Шаблон:Конец цитаты
Поскольку выход статьи Леонарда Эйлера «Решение одной задачи, связанной с геометрией положения» из печати датируется 1736 годом, а также этим годом датируются оба упомянутых выше письма, этот год мировым математическим сообществом назначен датой рождения раздела математики теория графовШаблон:Sfn.
Современное решение задачи
Формулировка задачи
Задача о кёнигсбергских мостах разными авторами формулируется по-разному.
1. Маршрут произвольный
Шаблон:Начало цитаты В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу. Шаблон:Конец цитаты
Шаблон:Начало цитаты Для жителей Кёнигсберга существовала своего рода игра: найти такой маршрут прогулки по городу, который бы проходил через каждый из показанных на рисунке мостов ровно один раз. Шаблон:Конец цитаты
2. Маршрут должен быть замкнутым
Шаблон:Начало цитаты Задача состояла в следующем: найти маршрут прохождения всех четырёх частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Шаблон:Конец цитаты
3. Замкнутые маршруты должны начинаться в каждой части города
Фактически требуется найти четыре маршрута обхода кёнигсбергских мостов, начинающиеся в четырёх частях города.
Шаблон:Начало цитаты Вопрос заключался в том, можно ли совершить прогулку таким образом, чтобы, выйдя из дома, вернуться обратно, пройдя в точности один раз по каждому мосту? Шаблон:Конец цитаты
Построение графа задачи
Современное решение задачи о кёнигсбергских мостах начинается с построения графа задачи (см. рисунок справа)Шаблон:Sfn:
- вершины графа — это четыре части центра Кёнигсберга, на которые разделён город двумя рукавами и протокой реки;
- ребра графа — это семь мостов в центре города;
- концевые вершины рёбер — это части центра Кёнигсберга, соединённые этими мостами.
Задачу о кёнигсбергских мостах можно переформулировать в терминах теории графов следующим образомШаблон:Sfn:
- существует ли в графе задачи о кёнигсбергских мостах эйлеров цикл или хотя бы эйлерова цепь?
Теоремы Эйлера
Начнём с определений, перейдём к теоремам и закончим следствиямиШаблон:Sfn:
- эйлерова цепь — последовательность рёбер (соседние рёбра имеют общую вершину), которая обходит все рёбра графа по одному разу;
- эйлеров цикл — замкнутая эйлерова цепь.
Следующие две теоремы впервые появились в статье Леонарда Эйлера о кёнигсбергских мостахШаблон:Sfn:
- первая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет эйлеров цикл тогда и только тогда, когда в каждую вершину входит чётное число рёбер;
- вторая теорема Эйлера, 1736. Граф с двумя или более вершинами имеет единственную эйлерову цепь тогда и только тогда, когда ровно в две вершины входит нечётное число рёбер.
Из этих двух теорем можно вывести три следствияШаблон:Sfn:
- если граф с двумя вершинами, в которые входит нечётное число рёбер, имеет эйлерову цепь, то эти две вершины — начальная и конечная вершины цепи;
- граф с двумя или более вершинами имеет эйлерову цепь тогда и только тогда, когда либо в каждую вершину входит чётное число рёбер, либо ровно в две вершины входит нечётное число рёбер;
- задача о кёнигсбергских мостах не имеет решения, поскольку в графе этой задачи нечётную степень имеют четыре вершины.
Решение задачи по Леонарду Эйлеру
Формулировка задачи
Леонард Эйлер в своей знаменитой статье сформулировал задачу о семи кёнигсбергских мостах следующим образомШаблон:Sfn: Шаблон:Начало цитаты 2. Эта задача, как мне сказали, довольно хорошо известна и связана вот с чем. В городе Кёнигсберге, в Пруссии, есть остров, называемый Кнайпхоф; река, окружающая его, делится на два рукава, что можно увидеть на рисунке. Рукава этой реки пересекают семь мостов а, b, с, d, e, f и g. В связи с этими мостами был поставлен вопрос, можно ли совершить по ним прогулку так, чтобы пройти по каждому из этих мостов, причём ровно по одному разу.
Решение задачи
Леонард Эйлер сформулировал свой метод следующим образом (см. рисунок выше)Шаблон:Sfn: Шаблон:Начало цитаты 4. Весь мой метод основан на надлежащих обозначениях для отдельных прохождений мостов. Я использую заглавные буквы А, В, С, D для обозначения отдельных областей, на которые река разделяет сушу. Таким образом, если некто движется из области А в область В через мост а или b, то я обозначаю прохождение моста символом АВ. Шаблон:Конец цитаты
На современном языке это означает, что схеме мостов города соответствует граф, представляющий собой:
- четыре вершины <math>A, B, C, D\ </math> по обозначениям четырёх частей центра города;
- вершины соединены семью рёбрами-мостами <math>a, b, c, d, e, f, g\ </math> по обозначениям семи мостов.
Достаточно современное и простое решение Леонардом Эйлером задачи о кёнигсбергских мостах выглядит следующим образом. Только следует иметь в виду, что Эйлер современной терминологии не знал, термин «граф» не использовал, называл ребро «мостом», а вершину — «областью» или «буквой» и не рисовал современные изображения графовШаблон:Sfn.
- «Таким образом, становится очевидным, что если можно пройти по семи мостам, причём по каждому из них ровно по одному разу, то этот маршрут будет изображаться восемью буквами».
- «…я разработал правило, по которому можно легко решить — как для этой задачи, так и для всех подобных задач, — может ли быть осуществлено такое расположение букв.
- «8. Чтобы вывести подобное правило, я рассматриваю некоторую конкретную область <math>A\ </math>, в которую может вести произвольное число мостов <math>a, b, c, d\ </math> и т. д. Из этих мостов сначала я рассмотрю конкретный мост <math>a\ </math>, ведущий в область <math>A\ </math>. Если путешественник пройдёт по этому мосту, то он либо находился в области <math>A\ </math> до того, как прошёл по этому мосту, либо окажется в области <math>A\ </math> после этого. Поэтому чтобы обозначить этот проход по мосту, как описано выше, необходимо, чтобы один раз возникла буква <math>A\ </math>.»
- «Если в область <math>A\ </math> ведут три моста, например <math>a, b, c\ </math>, и путешественник проходит по всем трём мостам, то буква <math>A\ </math> будет встречаться в описании его движения по мостам дважды независимо от того, начинался его маршрут из <math>A\ </math> или нет. Точно так же, если в область <math>A\ </math> ведут пять мостов, то буква <math>A\ </math> должна встретиться при описании его движения три раза. И когда количество мостов — произвольное нечётное число, то если увеличить его на единицу, половина полученного числа показывает, сколько раз должна встретиться буква <math>A\ </math>.»
- «9. Следовательно, в случае с кёнигсбергскими мостами, поскольку на остров <math>A\ </math> ведут пять мостов <math>a, b, c, d, e\ </math>, необходимо, чтобы буква <math>A\ </math> встретилась в описании движения по этим мостам трижды. Кроме того, дважды должна встретиться буква <math>B\ </math>, так как в область <math>B\ </math> ведут три моста, и буквы <math>D, C\ </math> должны встретиться по два раза каждая. Поэтому в последовательности из восьми букв, с помощью которой описывается рассматриваемый маршрут, проходящий через семь мостов, буква <math>A\ </math> должна встретиться три раза, а каждая из букв <math>B, C, D\ </math> — по два раза. Такого, однако, в последовательности из восьми букв быть не может. Таким образом, ясно, что подобная прогулка по семи мостам Кёнигсберга невозможна.»
Обобщение решения задачи
Решая задачу в общем виде, Леонард Эйлер попутно доказал, что для любого графа число вершин с нечётным количеством рёбер чётноШаблон:Sfn:
- «Вначале я отмечу, что все количества мостов», ведущих в области, «сложенные вместе, дают удвоенное число всех мостов. Причина состоит в том, что при таком подсчёте каждый мост считается дважды, с тем чтобы все мосты, ведущие в данную область, были учтены, ибо каждый мост ведёт в две области, которые он соединяет.
- 17. Из этого наблюдения вытекает, что сумма [чисел] всех мостов, ведущих в каждую область, есть чётное число, так как половина этой суммы есть в точности число мостов. Поэтому не может случиться так, чтобы среди чисел мостов, ведущих в любую область, в точности одно было нечётным; не может также случиться, чтобы нечётных чисел было три, пять и т. д. Следовательно, если числа мостов», ведущих в области, «суть нечётные числа, их сумма чётна.»
В конце статьи Леонард Эйлер записал общие выводы для любого графа вполне современным языкомШаблон:Sfn: Шаблон:Начало цитаты 20. Значит в каждом возможном случае следующее правило позволяет непосредственно и без труда выяснить, можно ли осуществить прогулку по всем мостам без повторений:
Если имеется более двух областей, в которые ведет нечётное число мостов, можно заявить с уверенностью, что такая прогулка невозможна.
Если, однако, имеются только две области, в которые ведет нечётное число мостов, то прогулка осуществима при условии, что она начинается в одной из этих двух областей.
Если, наконец, нет ни одной области, в которую ведет нечётное число мостов, прогулка с требуемыми условиями осуществима, причём начинаться она может в любой области.
Следовательно, с помощью этого правила поставленная задача может быть полностью решена. Шаблон:Конец цитаты
См. также
Примечания
Литература
- Шаблон:H
- Шаблон:H
- Шаблон:H
- Шаблон:H
- Шаблон:H
- Шаблон:Книга Содержит оригинальный латинский текст писем и перевод на русский язык Ю. Х. Копелевич (письмо к Маринони) и Т. А. Лукиной (письмо к Элеру).
- Шаблон:H* Шаблон:H
- Шаблон:H
- Шаблон:H
- Шаблон:H
- Русская Википедия
- Страницы с неработающими файловыми ссылками
- История математики
- Теория графов
- Занимательные задачи
- Кёнигсберг
- Математические задачи
- Открытия 1736 года
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии
