Задача о Кенигсберских мостах

Размещено на http: //www. allbest. ru/

МИНОБРНАУКИ РОССИИ

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Восточно-Сибирский государственный университет технологий и управления» (ВСГУТУ)

Электротехнический факультет

Кафедра «Электронно-вычислительные системы»

РЕФЕРАТ

на тему: Задача о Кенигсберских мостах

Выполнил: ст. гр. 658 Галсанов Н. В.

Проверил: ст. преп. Машеева Е. П.

Улан-Удэ 2018

Содержание

• Введение
• 1. История
• 2. Проблема семи мостов
• 3. Решение задачи
• Список используемой литературы

• Введение
• математический кенигсберский мост эйлер
• Семь мостов Кёнигсберга, или Задача о семи кёнигсбергских мостах (лат. Problema Regiomontanum de septem pontibus, нем. Kцnigsberger Brьckenproblem[источник не указан 950 дней]) -- старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году математиком Леонардом Эйлером, доказавшим, что это невозможно, и изобретшим таким образом эйлеровы циклы.


1. История

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем городским мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Джованни Джакобо Маринони от 13 марта 1736 года. В этом письме Эйлер приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя»[1]. В письме Карлу Готлибу Элеру от 3 апреля 1736 года Эйлер обосновывает найденное им правило, а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae».

2. Проблема семи мостов

Кёнигсберга или Задача о кёнигсбергских мостах (нем. Konigsberger Bruckenproblem) -- старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.

Мосты были местом шествий, религиозных и праздничных процессий, а в годы так называемого «Первого русского времени» (1758--1762 годы), когда во время Семилетней войны Кёнигсберг ненадолго вошёл в состав Российской империи, по мостам проходили православные крестные ходы. Один раз такой крестный ход даже был посвящён православному празднику Водосвятия реки Прегель, вызвавшему неподдельный интерес у жителей Кёнигсберга.

По традиции, чтобы впоследствии вернуться в Кёнигсберг, гость города должен был бросить в Прегель с одного из мостов монету. Во время очистки русла Преголи земснарядом в девяностых годах XX века коллекционеры-нумизматы буквально дрались за право постоять с ситом у «кишки», из которой выливался донный ил.

К началу XX века все семь мостов были разводными, но в связи с упадком судоходства по Преголе сохранившиеся мосты более не разводятся, за исключением Высокого моста. Он разводится периодически; для профилактики механизма и проводки мачтовых судов.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

3. Решение задачи по Леонарду Эйлеру

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города -- точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

- Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.

- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

- Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Старинная карта Кёнигсберга. Буквами обозначены части города: А -- Альтштадт, Б -- Кнайпхоф, В -- Ломзе, Г -- Форштадт. Цифрами обозначены мосты (в порядке строительства): 1 -- Лавочный, 2 -- Зелёный, 3 -- Рабочий, 4 -- Кузнечный, 5 -- Деревянный, 6 -- Высокий, 7 -- Медовый Граф кёнигсбергских мостов

Упрощённая схема мостов Кёнигсберга. Буквами обозначены части города: А -- Альтштадт, Б -- Кнайпхоф, В -- Ломзе, Г -- Форштадт. Цифрами обозначены мосты (в порядке строительства): 1 -- Лавочный, 2 -- Зелёный, 3 -- Рабочий, 4 -- Кузнечный, 5 -- Деревянный, 6 -- Высокий, 7 -- Медовый

Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете).

В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути.

Список использованной литературы

1. https://ru.wikipedia.org

Размещено на Allbest.ru