А знаете ли вы, что семь мостов города Кенингсберга (сейчас этот город называется Калининград) стали «виновниками» создания Леонардом Эйлером теории графов (Граф – это определенное количество узлов (вершин), соединённых рёбрами). Но как, же это произошло?
Два острова и берега на реке Прегель, на которой стоял Кенингсберг, были соединены 7 мостами. Знаменитый философ и ученый Иммануил Кант, гуляя по мостам города Кенигсберга, поставил задачу, известную всем в мире как задача о 7 кенигсбергских мостах: можно ли пройти по всем данным мостам и при этом вернуться в исходную точку маршрута так, чтобы пройти по каждому мосту только 1 раз. Многие пытались решить данную задачу как практически, так и теоретически. Но никому это не удавалось, при этом и не удавалось доказать, что это невозможно даже теоретически. Поэтому, по историческим данным, считается, что в 17 веке у жителей сформировалось особая традиция: прогуливаясь по городу, пройти по всем мостам всего по 1 разу. Но, как известно, ни у кого это не получилось.
В1736 г. данная задачка заинтересовала ученого Леонарда Эйлера, выдающегося и знаменитого математика и члена Петербургской академии наук. Об этом он написал в письме своему другу – ученному, итальянскому инженеру и математику Мариони от 13 марта1736 г. Он нашел правило, используя которое можно было легко и просто получить ответ на данный интересующий всех вопрос. В случае с городом Кенингсберг и его мостами это оказалось невозможно.
В процессе своих рассуждений, Эйлер пришел к следующим теоретическим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем 2 нечётными вершинами невозможно начертить одним росчерком
Если рассматривать данное правило к 7 мостам Кенингсберга, то части города на рисунке (графе) обозначаются вершинами, а мосты – ребрами, соединяющими данные вершины. Граф 7 кёнигсбергских мостов имел 4 нечётные вершины (то есть все, его вершины были нечетные), следовательно, невозможно пройти по всем 7 мостам, не проходя ни по одному из них дважды.
Казалось бы, у такого необычного открытия не может быть никакого реального применения и практической пользы. Но применение нашлось, и еще какое. Теория графов, созданная Леонардом Эйлером, легла в основу проектирования коммуникационных и транспортных систем, она используется в программировании и информатике, в физике, химии и многих других науках и областях.
Но самое интересное в том, что историки считают, что есть человек, который решил данную задачу, он смог пройти через все мосты только один раз, правда теоретически, но решение было…. А произошло это вот как...
Кайзер (император) Вильгельм славился своей простотой мышления, прямотой и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на данном приёме. Они показали кайзеру карту города Кёнигсберга, и попросили его попробовать решить эту знаменитую задачку, которая по определению была просто не решаемой. К всеобщему удивлению, Кайзер попросил лист бумаги и перо, и при этом уточнил, что решит данную задачку всего за полторы минуты. Ошеломлённые ученные не могли поверить своим ушам, но чернила и бумагу быстро нашли для него. Кайзер положил листок на стол, взял перо, и написал: «Приказываю построить восьмой мост на острове Ломзе». И все задача решена…..
Так в городе Кёнигсберг и появился новый 8 мост через реку, который так и назвали - мост Кайзера. А задачку с 8 мостами теперь может решить даже ребёнок.
Кенигсберг- Город СЕМИ МОСТОВ (раньше так называли)
Старинная карта Кёнигсберга. Буквами обозначены части города: А — Альтштадт, Б — Кнайпхоф, В — Ломзе, Г — Форштадт. Цифрами обозначены мосты (в порядке строительства): 1 — Лавочный, 2 — Зелёный, 3 — Рабочий, 4 — Кузнечный, 5 — Деревянный, 6 — Высокий, 7 — Медовый
Лавочный мост
Самым старым из семи мостов был Лавочный мост (Krämerbrücke/Крэмер-брюке), соединявший самый главный из кёнигсбергских городов — Альтштадт с расположенным рядом кёнигсбергским замком и лежащий на острове город Кнайпхоф.
Зеленый мост
Вторым по возрасту был Зелёный мост (Grüne Brücke/Грюне-брюке).
Рабочий мост
После Лавочного и Зелёного был построен Рабочий мост (Кёттель или Киттель-брюке), также соединявший Кнайпхоф и Форштадт.
Кузнечный мост
В 1397 году был построен Кузнечный мост (Schmiedebrücke/Шмиде-брюке).
Деревянный мост
Старинный столбик из ограждения Деревянного моста. На столбике виден герб Кнайпхофа — поднятая из воды рука, держащая корону. На заднем плане — Кафедральный собор. Деревянный мост (Holzbrücke/Хольц-брюке) между Альтштадтом и Ломзе.
Высокий мост
Ещё одним сохранившимся до сих пор мостом Кёнигсберга является Высокий мост (Hohe Brücke/Хоэ-брюке).
Медовый мост
Самый молодой из семи мостов — Медовый мост (Honigbrücke/Хониг-брюке), соединяющий острова Ломзе и Кнайпхоф.
А знаете ли вы … , что Эйлер свою теорию Графов вывел думая о семи мостах Кенигсберга.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды?
Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
Вот такая картинка сейчас бродит по всему интернету. Зачастую это сопровождается таким текстом: "В израильской военной разведке есть специальное подразделение, в котором служат юноши и девушки, страдающие разными нарушениями аутического спектра. Аутисты занимаются в основном анализом карт и аэрофотоснимков, появляющихся на экранах компьютеров. В силу особенностей мышления они обращают внимание на мельчайшие подробности, учет которых при подготовке военных операций на местности позволяет не допустить возможных потерь личного состава. Таким образом аутисты-разведчики спасают жизни солдат."
Вы пробовали проходить этот лабиринт?
Давайте выясним подробнее этот вопрос..
еще при упоминании этого лабиринта уточняется, что "Аутист способен обрабатывать визуальную и текстовую информацию в несколько раз быстрее, чем человек, не страдающий заболеваниями аутического спектра. Эта их особенность оказалась незаменимой в хайтеке. В датской компании Specialisterne, специализирующейся на технологическом консультировании, 75 процентов работников - аутисты и люди, у которых диагностирован синдром Аспергера, также относящийся к аутическому спектру. От обычных работников они отличаются невероятным вниманием к деталям, сверхчеловеческой сосредоточенностью, способностью быстро обрабатывать огромные массивы информации. Эти умения особенно полезны для тестировщиков программ. Качество работы аутистов, занимающихся этой работой, в несколько раз выше, чем качество работы обычных людей. Аутисты могут проверить техническую документацию на 4000 страниц в 10 раз быстрее обычных людей и не пропустить ни одной ошибки."
Но оставим в стороне аутистови выясним в конце концов как можно пройти этот лабиринт! А вот как...
Задача нерешаема! У нас 3 комнаты с нечетным количеством дверей (аналогия с рисунками "не отрывая карандаша"). Что бы задача имела решение необходимо, что бы было не более 2 точек(в нашем случае комнат) с нечетным количеством линий (в нашем случае проходов)
Если построить граф этого лабиринта, то мы увидим, что это Эйлеров путь, так как у него 3 вершины с нечётным числом рёбер (дверей), а для выполнения условий теста их может быть только две.
Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem ) - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
- Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных вИнтернете).
В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построенЮбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути
Вот еще такой вариант решения предлагал xlazex
Посмотрим на картинку1:
окружим квадратами каждую отдельную часть, исключим "лишние" точки, т.е. те точки, использование которых повысило бы возможное количество путей, и исключение которых не повлияет на количество дверей, пройденных линией и замкнутость контура. За начало пути возьмем, к примеру, точку 2
.
Посмотрим на картинку2:
на ней я изобразил тот же контур, но так, чтобы были виднее связи начальной точки с последующими. На изображении явно видно, что часть контура, обведенная синим цветом не может быть единожды замкнута, т.е. даже если бы эта часть контура была единственна, то не существовало бы путей, по которым можно было бы построить замкнутую линию.
Итог: задача не имеет решения в двумерной системе координат.
Но есть же решение в трехмерной:-)
Ну ладно, шутка, шутка...
Нетрадиционные решения задачи
«Решение» Кайзера
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже и соединявший остров Ломзе с южной стороной. Своим появлением этот мост обязан самой задаче Эйлера-Канта. Произошло это при следующих обстоятельствах.
Император Вильгельм был известен своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали Кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, Кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли.
Кайзер положил листок на стол, взял перо и написал следующее: «Приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который назвали «мостом Кайзера». А задачу с восемью мостами теперь мог решить даже ребёнок.
См. также
Литература
Wikimedia Foundation . 2010 .
Расположение семи мостов, согласно
легендам, тоже было выбрано не случайно, а число семь давно
считалось мистическим.
Кстати, традиция - бросить с моста монетку, чтобы вернуться,
появилась в Кенигсберге с давних времен.
Оказавшись в старинном городе, я прогулялась по его мостам.
Императорский мост в начале 20 века
Невозможно обойти все мосты, пройдя по каждому только один раз.
Среди горожан была нерешимой задача - как пройти по всем мостам
Кнайпхофа, не пройдя по какому-либо из них дважды.
Задачу решил император Вильгельм. Однажды на балу зашел разговор о
неразрешимой загадке мостов. Император сказал, что легко решит эту
задачу и велел принести ему перо и бумагу. Вильгельм написал приказ
- построить восьмой мост, который был назван Императорским.
Карта мостов, соединяющих островок Кнайпхоф с берегами. Семь мостов
- мистическое число.
Кнайпхоф снискал славу "острова магов", говорили, что мосты в
туманные сумерки могут увести в иные миры. Остров расположен на
перекрестке этих миров. Недаром им заинтересовались колдуны
Гитлера.
До наших времен из семи мостов уцелело только три. Призраки горожан прошедших эпох появляются здесь и в наши дни, проходят важно, торопясь по своим делам. Может, спешат из одного "параллельного мира" в другой через остров?
У каждого моста своя история и легенды.
Лавочный мост
Самый старый мост Кенигсберга, построенный в конце 13 века. Тогда он соединял два поселения - Кнайпхоф на острове и Альтштадт (Королевский замок) на берегу. Первоначально назывался - мостом святого Георга. Поселения тогда не были единым городом и даже враждовали между собой. Мост стал нейтральной территорией, где велась торговля. Вдоль моста стояли палатки торговцев, так мост в народе прозвали Лавочным. Здесь также продавали крепкий алкогольный напиток «Прегельская вонь».
Мост за столетия обветшал, был разобран и перестроен в 1900 году в разводной мост. В войну сильно пострадал и был восстановлен советскими реставраторами. К сожалению, в семидесятые как "партия приказала" мост был снесен, а на его месте прошла эстакада.
Зеленый мост
Построен в начале 14 века. Поначалу мост был деревянным и назывался
"Мостом длинной улицы", которая проходила от замка до госпиталя
Святого Георга. Деревянный мост часто горел и строился заново. В 16
веке мост, построенный заново после пожара, выкрасили в зеленый
цвет, так он стал "Зеленым мостом". На этом мосту встречались
знатные купцы города для переговоров. Мост был "почтовым", сюда
гонцы привозили письма. Уважаемые горожане приходили за важной
почтой лично и заодно встречались с компаньонами.
В 17 веке рядом с мостом была построена биржа, нынешнее здание
которой - перестройка конца 19 века.
Мост был модернизирован в начале 20 века. Пережил войну, был отреставрирован. К сожалению, его постигла участь Лавочного моста, он был разрушен "по приказу партии" для строительства эстакады, которая проходит прямо на месте этих двух мостов.
Зеленый мост в начале 20 века
Здание биржи и Зеленый мост в начале 20 века
Эстакада, которая проходит на месте Лавочного и Зеленого моста
Вид с части эстакады (бывшего зеленого моста) на биржу
Потроховый (Рабочий) мост
Построен во второй половине 14 века, рядом (в 50 метрах) с зеленым мостом. Мост использовался для переправки грузов. В 17 веке на пасху 1621 года в Кенигсберге случилось страшное наводнение, затопившее остров Кнайпхоф. По воспоминаниям современников "корабли выбрасывало на городские валы, крысы плавали на всплывших гробах, а в соборе вода стояла по колено" . При наводнении мост был разрушен, спешно восстановлен. Перестроен капитально в конце 19 века. Войну мост не пережил.
Раньше в 50 метрах здесь был Рабочий мост
Кенигсбергский собор, когда-то рядом был мост
Кузнечный мост
Построен во второй половине 14 века, тоже поначалу был деревянным.
Название свое получил благодаря кузницам, располагавшимся рядом.
Был перестроен в конце 19 века с разводным механизмом. Рядом
располагалась башенка, в которой находился "пункт управления"
мостом.
Мост разрушен во время войны.
Деревянный мост
Построен в начале 15 века. На мосту находилась памятная доска с цитатами из "Прусской хроники". Перестроен в начале 20го, сохранился до наших дней. Сохранились даже столбики моста.
Мост дожил до наших дней
Высокий мост
Построен в начале 16 века. С ним связана легенда о самом "правдивом" бароне Мюнхгаузене и его потерянном сапоге. Однажды, перебрав местного знатного пива, барон забрел в район Высокого моста. Найти свой дом он не смог, поэтому остановился на ночь в ближайшей гостинице. Комнатка оказалась так мала, что барон, когда лег, не смог поместиться во весь рост. Он вытянул ноги в открытое окно. Не сняв сапоги, барон заснул. Утром Мюнхгаузен обнаружил, что один его сапог упал в воду реки.
Знаменитый находчивый барон Мюнхгаузен стал легендой
Кенигсберга
В начале 19 века мост был перестроен.
Высокий мост в наши дни уже не так красив, но сохранился
А в этой башенке механизм для разводки моста
Медовый мост
Построен во второй половине 16 века.
С названием моста связано несколько легенд. По одной версии мост
построил "медовый магнат" той эпохи, чтобы соединить Кнайпхоф с его
медовой лавкой на берегу Ломзе. Для этого он даже дал взятку мэру
Кнайпхофа бочками меда. По другой версии, магнат выкупил целый мост
за мед. Есть версия, что со строителями моста расплачивались медом.
Жители соседнего района - Альтштадт, которые недолюбливали
Кнайпхоф, прозвали его жителей - медовыми лизунами.
С мостом связаны романтические легенды: «Если свою любимую девушку три раза перенести на руках через Медовый мост, три раза покружить ее на каждом берегу и закончить цикл на берегу Кнайпхофа, так и не опустив ее с рук, то она будет любить Вас вечно»
Медовый мост в наши дни
Императорский мост
Этот мост был построен в 1905 году по приказу императора Вильгельма, который таким способом решил загадку "семи мостов". Мост был разрушен во время войны. В 2005 года на его опорах построили новый мост в честь юбилея города, который получил название Юбилейный.
Так мост выглядел в начале 20 века
Новый юбилейный мост
Вид на Юбилейный мост
