Нетрадиционные решения задачи
«Решение» Кайзера
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже и соединявший остров Ломзе с южной стороной. Своим появлением этот мост обязан самой задаче Эйлера-Канта. Произошло это при следующих обстоятельствах.
Император Вильгельм был известен своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали Кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, Кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли.
Кайзер положил листок на стол, взял перо и написал следующее: «Приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который назвали «мостом Кайзера». А задачу с восемью мостами теперь мог решить даже ребёнок.
См. также
Литература
Wikimedia Foundation . 2010 .
Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
Проблема семи мостов Кёнигсберга
Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem) - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».
Решение задачи по Леонарду Эйлеру
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды
Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете).
Дальнейшая история мостов Кёнигсберга
В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути.
Возникший в XIII веке город Кенигсберг формально состоял из трех независимых городских поселений, нескольких слобод и поселков. Они располагались на берегах и островах реки Прегель, делившей город на четыре основные части: Альтштадт и Лёбенихт, Кнайпхоф, Ломзе, Фортштадт. Для связи и торговли между городскими поселениями в XIV веке стали строить мосты.
В связи с постоянной военной опасностью со стороны Польши и Литвы, перед каждым из мостов была построена оборонительная или т.н. Присмотровая башня с закрывающимися подъемными или двустворчатыми воротами из дуба с железной кованой обивкой. Да и сами мосты приобретали характер оборонительных сооружений.
Мосты были местом шествий, религиозных и праздничных мероприятий и процессий, а в годы т.н. «Первого русского времени» (1758 - 1762 г.г.), когда Кенигсберг во время Семилетней войны вошел в состав Российской империи, по мостам проходили православные крестные ходы. Один раз такой крестный ход был посвящен православному празднику Водосвятия р.Прегель, что вызвало неподдельный интерес коренных жителей Кенигсберга.
К началу ХХ века все семь мостов были разводными, но в связи с ослаблением и упадком судоходства по р.Прегель сохранившиеся до наших дней 3 моста больше не разводятся.
Лавочный мост, Krämerbrücke
Самый старый из семи мостов Кенигсберга - Лавочный мост (Krämerbrücke), который соединял город Альтштадт (Королевский замок) и остров Кнайпхоф.
Построен в 1286 году, в 1900 году на месте старого деревянного моста возвели новый металлический мост. Название моста свидетельствует о том, что он сам и прилегающая к нему территория р.Преголи были сосредоточением торговли.
При въезде на мост была установлена статуя Ганса Загана - сына кнайпхофского сапожника. По легенде, во время битвы между войсками Тевтонского ордена и Литвинами близ Рудау (п.Мельниково, Зеленоградского района) Ганс подхватил из рук раненого рыцаря орденское знамя. Нацисты, пришедшие к власти в Германии в 1933 году по идейным и нравственным соображениям снесли памятник Загану, т.к. он был - еврей.
В 1972 году снесен в связи со строительством Эстакадного моста.
Лавочный мост. На заднем плане склады и район погрузки судов - Ластадие
Лавочный мост с портовыми складами-амбарами шпайхерами (Speicher) на правой набережной реки Прегель. Районы Лаак и Хундегатт. Слева - остров Кнайпхоф
Зеленый мост, GrüneBrücke
Второй по возрасту мост Кенигсберга - Зеленый мост . Построен в 1322 году. В 1582 году мост сгорел, построен заново к 1590 году и просуществовал в деревянном виде до 1907 года, когда был заменен на металлический мост.
Соединил через старый рукав р.Преголи остров Кнайпхоф и район Фортштадт для проезда от Королевского замка в пригород Понарт. Само название моста произошло от цвета краски, которой красили пролетные строения и опоры моста.
В XVII веке именно у Зеленого моста раздавались письма, прибывавшие в Кенигсберг. В ожидании почты у Зеленого моста собирались деловой люд города и в ожидании корреспонденции обсуждали свои дела. В 1623 году именно около Зеленого моста была построена Кенигсбергская торговая биржа.
В 1972 году зеленый мост, как и Лавочный мост, пал жертвой Эстакадного моста.
Зеленый мост. Вид с острова Кнайпхоф
Вид на Зеленый мост и Торговую биржу
Потроховый (Рабочий) мост, Koettel brücke
В 1377 году после Лавочного и Зеленого мостов выше по течению старого русла р.Прегель построен Потроховый или Рабочий мост, который также соединял остров Кнайпхоф и район Форштадт.
Оба варианта перевода не являются идеальными, т.к. немецкое название моста происходит из Саксонии и в русском варианте примерно означает «вспомогательный, рабочий, предназначенный для провоза мусора» мост. Скорее всего своим названием обязан располагавшейся поблизости скотобойне.
В 1886 году деревянный перестроен в железный.
Во время Второй мировой войны Потроховый мост был разрушен и более не восстанавливался.
Потроховый мост. Вид на Торговую биржу с острова Кнайпхоф
Потроховый мост. Вид с Зеленого моста
Кузнечный мост,Schmitderbrüke
В 1397 в Кенигсберге выше по течению нового русла р.Прегель возведен Кузнечный мост, который, как и Лавочный мост соединял город Альтштадт и остров Кнайпхоф.
Рядом с этим мостом на берегах реки Прегель традиционно размещались кузнецы.
К 1787 году мост сильно износился и обветшал и был заменён новым мостом, но тоже деревянным. В1896 году на месте старого деревянного моста возвели новый металлический мост.
Кузнечный мост разрушен во время Второй мировой войны и больше не восстанавливался.
Кузнечный мост с присмотровой башней
Кузнечный мост
Деревянный мост, Holzbrücke
В 1404 году между Альтштатом и островом Ломзе построен четверный мост, который получил название Деревянный.
На Деревянном мосту располагалась памятная доска с выдержками «Прусской хроники». Сам десятитомный труд Альбрехта Лухела Давида повествовал о древней языческой Пруссии и истории Тевтонского ордена до 1410 года.
В1904 году на месте старого Деревянного моста возвели новый металлический мост, но название моста осталось прежним. В таком виде Деревянный мост сохранился до сих пор.
Деревянный мост. Вид на остров Кнайпхоф
Высокий мост, Hohebrücke
Построили в Кенигсберге в 1520 году для соединения острова Ломзе и района Форштадт.
Подвергся реконструкции в 1882 году, его деревянные части были заменены металлическими. В этом же году рядом с Высоким мостом в районе Форштадт возвели мостовой домик. Это красивое, небольшое здание в стиле неоготики сохранилось до сих пор.
В 1937 году старый разобрали и рядом соорудили новый из металла с бетонными опорами. От старого Высокого моста сохранились бетонно-кирпичные опоры.
Высокий мост. Вид на остров Ломзе
Высокий мост. Вид с острова Ломзе на район Форштадт
Медовый мост, Honigbrücke
Самый «юный» из семи мостов Кенигсберга соединил остров Ломзе и остров Кнайпхоф.
Существует несколько версий о происхождении названия Медового моста . По одной из них, Безенроде - член Кнайпхофской ратуши оплатил строительство моста бочками мёда, по-другой - медом оплатили постройку торговой лавки возле моста. Но эти версии, вероятно, всего лишь городские легенды.
Скорее всего, название моста происходит от слова «хон», что означает - издевка (насмешка). Построив этот мост, жители острова Кнайпхоф получили кратчайший путь на остров Ломзе, в обход Высокого моста, который принадлежал Альтштадту. Таким образом, стал как бы насмешкой над главным из кёнигсбергских городов - Альтшадтом. За это альтштадцы прозвали кнайпхофцев - медовыми лизунами.
в 1882 году на месте старого Медового моста возведен новый мост из металла.
Медовый мост. Вид на остров Кнайпхоф и Кафедральный собор
Сохранился до наших дней и в основном используется как пешеходный мост, так как в настоящее время на острове Кнайпхоф расположен только Кафедральный собор - главная достопримечательность города Калининграда. В настоящее время молодожены вешают замки со своими именами и датой бракосочетания на перила Медового моста , а ключи от замков ломают и выбрасывают в реку Прегель.
Задача о семи мостах Кенигсберга, Леонард Эйлер и теория графов
С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.
В 1736 году известный математик, член Петербургской академии наук Леонард Эйлер взялся решить задачу о семи мостах. В том же году он написал об этом инженеру и математику Мариони. Эйлер писал, что нашел правило, по которому нетрудно вычислить, можно ли пройти по всем мостам и при этом ни по одному не пройти дважды. На семи мостах Кенигсберга сделать это невозможно.
На схеме города (графе) ребра графа соответствуют мостам, а вершины графа (точки, в которых соединяются линии) - частям города. Размышляя над задачей, Эйлер сделал следующие выводы:
вершины графа могут быть четными и нечетными- одним росчерком пера можно начертить граф, все вершины которого четные, можно начать в любой вершине графа и закончить этой же вершиной
- число нечетных вершин (таких, к которым ведет нечетное число ребер) должно быть нечетным, граф с четным числом нечетных вершин, не существует
- невозможно начертить одним росчерком граф с более чем двумя нечетными вершинами.
У графа кенигсбергских мостов четыре нечетных вершины, то есть все. Таким образом, пройти по всем мостам, ни по одному не проходя дважды, не представляется возможным.
НОВОСТИ ФОРУМА Рыцари теории эфира | 23.02.2020 - 19:17: -> - Карим_Хайдаров. 23.02.2020 - 19:14: |
Расположение семи мостов, согласно
легендам, тоже было выбрано не случайно, а число семь давно
считалось мистическим.
Кстати, традиция - бросить с моста монетку, чтобы вернуться,
появилась в Кенигсберге с давних времен.
Оказавшись в старинном городе, я прогулялась по его мостам.
Императорский мост в начале 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 века
Новый юбилейный мост
Вид на Юбилейный мост
Отцом теории графов (так же как и топологии) является Эйлер (1707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов. В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке 4.
Задача состояла в следующем : найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей.
Рисунок 4- Задача о кёнигсбергских мостах.
Исключительный вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность такого маршрута.
Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост – линией (ребром), соединяющей соответствующие точки. Получился граф. Утверждение о несуществовании положительного решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом данный граф.
Рисунок 5 – Граф.
Элементы графа. Способы задания графа. Подграфы.
Такая структура как граф в качестве (синонима используется также термин «сеть»), имеет самые различные применения в информатике.
Графом G называется система (V , U ) ,
где V ={ v } - множество элементов, называемых вершинами графа;
U =={ u } - .множество элементов, называемых ребрами графа.
Каждое ребро определяется либо парой вершин (v1,v2), либо двумя противоположными парами (v1,v2) и (v2,v1).
Если ребро из U представляется только одной парой (v1,v2), то оно называется ориентированным ребром , ведущим из v1 в v2. При этом v1 называется началом, а v2 -концом такого ребра.
Если ребро U представляется двумя парами (v1,v2) и (v2,v1), то U называется неориентированным ребром . Всякое неориентированное ребро между вершинами v1 и v2 ведет как из v1 в v 2, так и обратно. При этом вершины v1 и v2 являются как началами, так и концами этого ребра. Говорят, что ребро ведет как из v 1 в v 2, так и из v 2 в v 1.
Всякие две вершины, которые соединяются ребром, являются смежными.
По количеству элементов графы делятся на конечные и бесконечные.
Граф, все рёбра которого неориентированные, называется неориентированным графом.
Если рёбра графа определяются упорядоченными парами вершин, то такой граф называется ориентированным.
Р
исунок
6 – Ориентированный граф.
Существуют смешанные графы , состоящие как из ориентированных, так и из неориентированных рёбер.
Если две вершины соединены двумя или более рёбрами, то эти рёбра называют параллельными .
Если начало и конец ребра совпадают, то такое ребро называется петлёй .
Граф без петель и параллельных рёбер называется простым.
Если ребро определяется вершинами v1 и v2, то ребро инцидентно вершинам v1 и v2.
Вершина, не инцидентная ни одному ребру, называется изолированной .
Вершина, инцидентная ровно одному ребру, и само это ребро называются концевыми, или висячими.
Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или параллельными.
Две вершины неориентированного графа v1 и v2 называются смежными, если в графе существует ребро (v1,v2).
Две вершины ориентированного графа v1 и v2 называются смежными, если они различны и существует ребро, ведущее из вершины v1 в v2.
Рассмотрим некоторые понятия для ориентированного графа.
Рисунок 7 – Ориентированный граф.
Простой путь:
Элементарный путь:
Элементарный контур:
Контур:
Для неориентированных графов понятия «простой путь», «элементарный путь», «контур», «элементарный контур» заменяют, соответственно, понятия «цепь», «простая цепь», «цикл», «простой цикл». Граф называется связным , если для любых двух вершин существует путь (цепь), соединяющий эти вершины.
Неориентированный связный граф без циклов называется деревом .
Неориентированный несвязный граф без циклов - лесом .
Рисунок 8 – Связный граф.
Рисунок 9 –Лес.
Рисунок 10 – Дерево.