Загадка семи мостов кенигсберга

Обновлено: 22.11.2024

Вот такая картинка сейчас бродит по всему интернету. Зачастую это сопровождается таким текстом : "В израильской военной разведке есть специальное подразделение, в котором служат юноши и девушки, страдающие разными нарушениями аутического спектра. Аутисты занимаются в основном анализом карт и аэрофотоснимков, появляющихся на экранах компьютеров. В силу особенностей мышления они обращают внимание на мельчайшие подробности, учет которых при подготовке военных операций на местности позволяет не допустить возможных потерь личного состава. Таким образом аутисты-разведчики спасают жизни солдат."

Вы пробовали проходить этот лабиринт ?

Давайте выясним подробнее этот вопрос ..

еще при упоминании этого лабиринта уточняется, что "Аутист способен обрабатывать визуальную и текстовую информацию в несколько раз быстрее, чем человек, не страдающий заболеваниями аутического спектра. Эта их особенность оказалась незаменимой в хайтеке. В датской компании Specialisterne, специализирующейся на технологическом консультировании, 75 процентов работников — аутисты и люди, у которых диагностирован синдром Аспергера, также относящийся к аутическому спектру. От обычных работников они отличаются невероятным вниманием к деталям, сверхчеловеческой сосредоточенностью, способностью быстро обрабатывать огромные массивы информации. Эти умения особенно полезны для тестировщиков программ. Качество работы аутистов, занимающихся этой работой, в несколько раз выше, чем качество работы обычных людей. Аутисты могут проверить техническую документацию на 4000 страниц в 10 раз быстрее обычных людей и не пропустить ни одной ошибки."

Но оставим в стороне аутистови выясним в конце концов как можно пройти этот лабиринт ! А вот как .

Задача нерешаема! У нас 3 комнаты с нечетным количеством дверей (аналогия с рисунками "не отрывая карандаша"). Что бы задача имела решение необходимо, что бы было не более 2 точек( в нашем случае комнат) с нечетным количеством линий (в нашем случае проходов)

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

Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.

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

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


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

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

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

Вот еще такой вариант решения предлагал xlazex

Посмотрим на картинку1: окружим квадратами каждую отдельную часть, исключим "лишние" точки, т.е. те точки, использование которых повысило бы возможное количество путей, и исключение которых не повлияет на количество дверей, пройденных линией и замкнутость контура. За начало пути возьмем, к примеру, точку 2.
Посмотрим на картинку2: на ней я изобразил тот же контур, но так, чтобы были виднее связи начальной точки с последующими. На изображении явно видно, что часть контура, обведенная синим цветом не может быть единожды замкнута, т.е. даже если бы эта часть контура была единственна, то не существовало бы путей, по которым можно было бы построить замкнутую линию.
Итог: задача не имеет решения в двумерной системе координат.

Но есть же решение в трехмерной :-)

Ну ладно, шутка, шутка .

Вот например кто хочет пройти нормальный лабиринт - Кто хочет пройти лабиринт ?, а вот Лабиринт Минотавра. А что мы еще разоблачали : говорили например, что Существует ли женщина с тремя грудями ? и В Африке найдено племя плохих танцоров ?. А вот еще утверждают, что Бронтозавры не вымерли ? и Зомбоящик зомбирует ?

Следующая загадка

В предыдущей статье я предложил Вам решить задачку про семь мостов. Звучит она так: как пройти по всем мостам, не проходя при этом ни по одному из них дважды?

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

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

Как Эйлер пришёл к решению задач такого типа? Он заметил, что в этой конкретной задаче есть четыре "области": два берега реки и два острова, соединённые между собой мостами. Для упрощения понимания задачи он предложил "области" заменить точками, а мосты - линиями. Визуально задача стала выглядеть проще. Теперь она состояла в следующем: как, не отрываясь от бумаги, провести карандашом по всем линиям и точкам, не проходя по одной и той же линии два раза?

Эйлер заметил, что все точки соединены друг с другом нечётным количеством линий. Нарисовав ещё несколько подобных рисунков, только с разным количеством точек и соединявших их линий, он довольно быстро нашёл несколько правил для решения: 1) количество нечётных точек (то есть точек, которые соединяются с другими точками нечётным количеством линий), всегда будет чётное количество, т. е. 0, 2, 4, 6, и т. д.; 2) если все точки чётные (то есть соединяются друг с другом чётным количеством линий), а следовательно, нечётных точек - 0, то, чтобы соблюсти условие задачи, начните движение из любой точки и, пройдя все линии, Вы вернётесь в исходную точку; 3) если нечётных точек две, то начинать движение нужно в одной из них и закончить во второй; 4) если нечётных точек больше двух, то решения у данной конкретной задачи нет. Вот так всё просто оказалось! Следовательно, задача о семи мостах Кёнигсберга не имеет решения, так как нечётных точек четыре, что больше двух.

Надеюсь, Вам понравилась задача! В следующей статье я расскажу Вам о циклических числах. Поверьте мне, это очень интересно!

Следующая загадка

Итак, по легенде один из жителей Кенигсберга спросил у своего товарища, сможет ли он пройти во всем мостам, связывающим островки на реке Преголь и вернуться в ту же самую точку, побывав на каждом мосту ровно один раз ?

Решить на практике эту задачу никто из жителей не смог. Покорилась она лишь Эйлеру, в то время работавшему в Петербурге. Легендарный математик не только расставил все точки над i, но и разработал общий принцип решения таких задач.

Эйлер схематически изобразил структуру, которую образуют мосты и назвал её " графом" . Точки на нём он назвал "вершинами" , а соединяющие их линии - "ребрами" .

Ключевая догадка Эйлера состояла в том, чтобы подсчитать, сколько ребер выходит из каждой вершины . На нашем рисунке:

  • из 1-ой - выходит три ребра;
  • из 2-ой - пять ребер;
  • из 3-ой - три ребра;
  • из 4-ой - три ребра.
Все четыре вершины графа оказались "нечетными".

Немного поэкспериментировав, Эйлер вывел четыре основных правила для решения таких задач:

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

2. Если у графа все вершины четные, то его можно начертить одним росчерком пера, причем неважно, где начинать.

3. Если у графа две нечетные вершины, то его можно начертить одним росчерком пера, но начинать надо в одной из нечетных вершин, а закончить в другой.

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

Посчитал для Вас вершины. Теперь Вы знаете, что можно, а что нельзя начертить. Посчитал для Вас вершины. Теперь Вы знаете, что можно, а что нельзя начертить.

Я думаю, Вы уже догадались, что задача о мостах Кёнигсберга решений не имеет, ведь в ней целых четыре нечетных вершины! Однако в наших силах, вооружившись новыми знаниями, "дополнить" архитектурные изыски Калининграда таким образом, чтобы разрешить проблему:

Следующая загадка

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

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

На опорах Императорского моста в 2005 году был построен Юбилейный мост. На 2017 год в Калининграде восемь мостов.

____________________

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

В 1735 году математик Леонард Эйлер решил знаменитую загадку о семи мостах Кёнигсберга, положив начало новой области математики - теории графов. Изначально, в теории не углядяли никакого прикладного значения, и она оставалась "чисто математической". Однако, в 21 веке теория графов находит свое применение во многих областях науки. С помощью неё, например, решается задача рафсшифровки ДНК.

От мостов Кёнигсберга до сборки генома

Читайте также: