Кенигсберг- Город СЕМИ МОСТОВ (раньше так называли)
Старинная карта Кёнигсберга. Буквами обозначены части города: А — Альтштадт, Б — Кнайпхоф, В — Ломзе, Г — Форштадт. Цифрами обозначены мосты (в порядке строительства): 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 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
Отцом теории графов (так же как и топологии) является Эйлер (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 – Дерево.
Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.
кенигсбергских мостов">
Несколько модифицируем задачу. Каждую из рассматриваемых местностей, разделенных рекой, обозначим точкой, а соединяющие их мосты – отрезком линии (не обязательно прямой). Тогда вместо плана будем работать просто с некой фигурой, составленной из отрезков кривых и прямых. Такие фигуры в современной математике называются графами, отрезки – ребрами, а точки, которые соединяют ребра – вершинами. Тогда исходная задача эквивалентна следующей: можно ли начертить данный граф, не отрывая карандаша от бумаги, то есть таким образом, чтобы каждое его ребро пройти ровно один раз.
Такие графы, которые можно начертить, не отрывая карандаша от бумаги, называются уникурсальными (от латинского unus cursus – один путь), или эйлеровыми. Итак, задача ставится таким образом: при каких условиях граф уникурсален? Ясно, что уникурсальный граф не перестанет быть уникурсальным, если изменить длину или форму его ребер, а также изменить расположение вершин – лишь бы не менялось соединение вершин ребрами (в том смысле, что если две вершины соединены, они должны оставаться соединенными, а если разъединены – то разъединенными).
Если граф уникурсален, то и топологически эквивалентный ему граф тоже будет уникурсальным. Уникурсальность, таким образом, является топологическим свойством графа.
Во-первых, надо отличать связные графы от несвязных. Связными называются такие фигуры, что любые две точки можно соединить каким-нибудь путем, принадлежащим этой фигуре. Например, большая часть букв русского алфавита связны, но вот буква Ы – нет: невозможно перейти с ее левой половинки на правую по точкам, принадлежащим этой букве. Связность – это топологическое свойство: оно не меняется при преобразованиях фигуры без разрывов и склеек. Понятно, что если граф уникурсален, то он обязан быть связным.
Во-вторых, рассмотрим вершины графа. Будем называть индексом вершины число ребер, встречающихся в этой вершине. Теперь зададимся вопросом: чему могут равняться индексы вершин уникурсального графа.
Здесь может быть два случая: линия, вычерчивающая граф, может начинаться и заканчиваться в одной и той же точке (назовем ее «замкнутый путь»), а может в разных (назовем ее «незамкнутый путь»). Попробуйте сами нарисовать такие линии – с какими хотите самопересечениями – двойными, тройными и т. д. (для наглядности лучше, чтобы ребер было не больше 15).
Нетрудно видеть, что в замкнутом пути все вершины имеют четный индекс, а в незамкнутом – ровно две имеют нечетный (это начало и конец пути). Дело в том, что, если вершина не является начальной или конечной, то, придя в нее, надо затем из нее выйти – таким образом, сколько ребер входят в нее, столько же выходят из нее, а всего число входящих и исходящих ребер будет четным. Если начальная вершина совпадает с конечной, то ее индекс также четен: сколько ребер из нее вышло, столько же и вошло. А если начальная точка не совпадает с конечной, то их индексы нечетные: из начальной точки нужно один раз выйти, а затем, если в нее и вернемся, то выйти снова, если еще раз вернемся – опять выйти, и т. д.; а в конечную нужно придти, а если из нее потом и выходим, то опять нужно вернуться, и т. д.
Итак, чтобы граф был уникурсальным, необходимо, чтобы все его вершины имели четный индекс либо чтобы число вершин с нечетным индексом равнялось двум.
 |
Посчитайте индексы его вершин и убедитесь, что он никак не может быть уникурсальным. Вот поэтому-то у вас ничего не получалось, когда вы хотели обойти все мосты...
Возникает вопрос: а если в связном графе нет вершин с нечетным индексом либо таких вершин ровно две, то обязательно ли граф уникурсален? Можно строго доказать, что да! Таким образом, уникурсальность однозначно связана с числом вершин с нечетным индексом.
Упражнение: постройте на схеме кенигсбергских мостов еще один мост – там, где захотите – чтобы полученные мосты можно было бы обойти, побывав на каждом ровно по разу; реально проделайте такой путь.
Теперь еще один интересный факт: оказывается, любую систему местностей, соединенных мостами, можно обойти, если необходимо побывать на каждом мосту ровно два раза! Попробуйте это доказать самостоятельно.
| НОВОСТИ ФОРУМА Рыцари теории эфира | 01.10.2019 - 05:20: -> - Карим_Хайдаров. 30.09.2019 - 12:51: |
Когда я был маленьким (лет 8, наверное), я подошёл к отцу и спросил: «А почему Калининград называют городом семи мостов?». В ответ он мне поведал интереснейшую историю, разложил всё по полочкам. Это было захватывающе и очень познавательно. Естественно, я эту историю уже не помню в том первозданном виде, но постараюсь рассказать её максимально увлекательно.
Как известно, город Кенигсберг, основанный в 1255 году, состоял из трёх независимых городских поселений. Располагались они на островах и берегах реки Прегель (ныне – Преголя), делящей город на четыре части:
- Альтштадт;
- Кнайпхоф;
- Ломзе;
- Форштадт.
Для связи между городскими частями в XIV веке стали строить мосты. В связи с постоянной военной опасностью со стороны соседних Польши и Литвы, кёнигсбергские мосты стали иметь вторую функцию – оборонительную. Перед каждым из мостов была построена оборонительная башня с закрывающимися подъёмными или двустворчатыми воротами из дуба и с железной кованой обивкой. Опоры некоторых мостов имели пятиугольную форму, типичную для бастионов. Внутри этих опор располагались казематы, из которых можно было вести огонь через амбразуры.
Все семь мостов Кенигсберга были разводными. В связи с упадком судоходства по Преголе мосты перестали разводить. Исключением стал только Высокий мост, разводящийся периодически для профилактики механизма и проводки мачтовых судов.
Существовала традиция: гость города, чтобы впоследствии вернуться в Кёнигсберг, должен был бросить в Прегель с одного из мостов монету.
Вот Вам интересный факт , связанный с традицией: во время очистки русла Преголи земснарядом в девяностых годах XX века коллекционеры-нумизматы буквально дрались за право постоять с ситом у «кишки», из которой выливался донный ил.
А вот и второй факт: «Задача о семи кёнигсбергских мостах». Знаменитый философ и ученый Иммануил Кант, гуляя по мостам города Кенигсберга, поставил задачу: можно ли пройти по всем данным мостам и при этом вернуться в исходную точку маршрута так, чтобы пройти по каждому мосту только 1 раз. Многие пытались решить данную задачу как практически, так и теоретически. Но никому это не удавалось, при этом и не удавалось доказать, что это невозможно даже теоретически.
В 1736 году данная задача заинтересовала ученого Леонарда Эйлера, выдающегося и знаменитого математика и члена Петербургской академии наук. Об этом он написал в письме своему другу – учёному, итальянскому инженеру и математику Мариони от 13 марта 1736 года. Он нашел правило, используя которое можно было легко и просто получить ответ на данный интересующий всех вопрос. В случае с городом Кёнигсбергом и его мостами это оказалось невозможно. Но ему удалось создать теорию графов (математики поймут), которая используется до сих пор.
Вы тоже можете попробовать решить эту задачу. Вот схема мостов города:
Давайте разберёмся, что же это за семь мостов.
Krämerbrücke (Лавочный мост).
Считается самым старым из семи мостов. Его построили в 1286 году с целью соединить город Альтштадт и Кнайпхоф, и на его въезде была установлена статуя Ганса Загана, сына кнайпховского сапожника. Легенда гласила: во время битвы между войсками Тевтонского ордена и Литвы Ганс подхватил падающее орденское знамя из рук раненого рыцаря.
Название своё мост получил из – за того, что прилегающие берега Прегеля, да и он сам были местом торговли.
В 1900 году его перестроили, а в 1972 году был снесён по причине строительства Эстакадного моста.
Grünebrücke (Зелёный мост).
Зелёный мост был построен в 1322 году и соединял Кнайпхоф и Форштадт. Своё название получил от цвета краски, в который традиционно красили опоры и пролётное строение моста.
В XVII веке у Зелёного моста гонец раздавал прибывшие в Кёнигсберг письма. В ожидании корреспонденции здесь собирались деловые люди города, которые в ожидании почты обсуждали свои насущные дела. По легенде, именно по этой причине в 1623 году вблизи Зелёного моста было построено первое здание Кёнигсбергской торговой биржи.
В 1875 году на другой стороне моста было построено новое здание торговой биржи, сохранившееся до сих пор. Ныне это здание – Дворец культуры моряков.
В 1907 году мост был перестроен, а в 1972 его постигла та же участь, что и Лавочный мост: они были заменены на Эстакадный мост.
Köttelbrücke (Рабочий мост).
Рабочий мост возвели в 1337 году. Соединял Кнайпхоф и Форштадт. Иногда его название переводят как «Потроховый», которое связано со скотобойней, находившейся неподалёку. Откуда переправляли потроха вплавь по Прегелю через данный мост.
Изначально мост был разводным и состоял из трёх пролётов. В 1621 году его смыло наводнением и был отстроен заново уже без подъёмного механизма.
Во времена развития Форштадта в 1886 году Рабочий мост перестроили в камне и металле. Ему вернули разводную функцию.
Мост сгорел во время Великой Отечественной войны и был снесён вместе с опорами-быками в 70 – х годах ХХ века.
Schmiedebrücke (Кузнечный мост).
Кузнечный мост был построен в 1397 году был. Соединял Альтштадт и Кнайпхоф.
Рядом с этим мостом на берегах Прегеля традиционно размещались кузнецы, видимо от этого и получил своё название.
После строительства мост принял на себя часть нагрузки с располагавшегося параллельно, чуть ниже по течению, Лавочного моста. Изначально был снабжён двумя каменными опорами, укрытыми пролётами из досок, которые сильно износились к 1787 году и были заменены. В 1896 году Кузнечный мост пережил реконструкцию и получил декоративные опоры, стальные пролёты и стал разводным. На стороне Альтштадта была построена башня смотрителя, в которой располагалась установка для подъёма мостовых пролётов с помощью давления воды городского водопровода, и осуществлялось управление разводным механизмом.
Во времена Великой Отечественной войны был разрушен и после войны не восстанавливался.
Holzbrücke (Деревянный мост).
Деревянный мост был построен в 1404 году и соединял Альтштадт и Ломзе.
На нём находилась памятная доска с выдержками из «Прусской хроники» Альбрехта Лухела Давида. Этот десятитомный труд повествовал о языческой Пруссии и истории Тевтонского ордена.
Деревянный мост был реконструирован в 1904 году и в таком виде существует до сих пор.
Hohebrücke (Высокий мост).
Высокий мост был возведён в 1520 году, соединяя между собой Ломзе и Форштадт. В 1882 году его перестроили, добавив к нему «Домик смотрителя мостов» (помещение для разводки механизмов развода моста). Это здание в стиле неоготики сохранилось до сих пор.
Высокий мост был снесён в 1938 году.
В нескольких десятках метров от сохранившихся каменных опор старого Высокого моста возвели новый Высокий мост, который стоит и сейчас. Имеет разводную среднюю часть для проводки мачтовых судов.
Honigbrücke (Медовый мост).
Самый молодой из семи мостов, соединяет Ломзе и Кнайпхоф. Существует разные версии о происхождении названия:
- Член Кнайпховской ратуши Безенроде оплатил постройку моста бочками мёда.
- Тот же Безенроде оплатил бочками мёда строительство торговой лавки на заречной территории.
- Название происходит от слова «Hon», что значит – насмешка или издёвка. Построив этот мост, жители Кнайпхофа получили прямой доступ к городу Ломзе, в обход Высокого моста, который принадлежал Альтштадту. Таким образом, Медовый мост стал насмешкой над главным из кёнигсбергских мостов.
Сейчас имеет пешеходный характер и ведёт на остров Канта к Кафедральному собору и парку скульптур. Проезд для частного автотранспорта туда запрещён.
А знаете ли вы, что семь мостов города Кенингсберга (сейчас этот город называется Калининград) стали «виновниками» создания Леонардом Эйлером теории графов (Граф – это определенное количество узлов (вершин), соединённых рёбрами). Но как, же это произошло?
Два острова и берега на реке Прегель, на которой стоял Кенингсберг, были соединены 7 мостами. Знаменитый философ и ученый Иммануил Кант, гуляя по мостам города Кенигсберга, поставил задачу, известную всем в мире как задача о 7 кенигсбергских мостах: можно ли пройти по всем данным мостам и при этом вернуться в исходную точку маршрута так, чтобы пройти по каждому мосту только 1 раз. Многие пытались решить данную задачу как практически, так и теоретически. Но никому это не удавалось, при этом и не удавалось доказать, что это невозможно даже теоретически. Поэтому, по историческим данным, считается, что в 17 веке у жителей сформировалось особая традиция: прогуливаясь по городу, пройти по всем мостам всего по 1 разу. Но, как известно, ни у кого это не получилось.
В1736 г. данная задачка заинтересовала ученого Леонарда Эйлера, выдающегося и знаменитого математика и члена Петербургской академии наук. Об этом он написал в письме своему другу – ученному, итальянскому инженеру и математику Мариони от 13 марта1736 г. Он нашел правило, используя которое можно было легко и просто получить ответ на данный интересующий всех вопрос. В случае с городом Кенингсберг и его мостами это оказалось невозможно.
В процессе своих рассуждений, Эйлер пришел к следующим теоретическим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем 2 нечётными вершинами невозможно начертить одним росчерком
Если рассматривать данное правило к 7 мостам Кенингсберга, то части города на рисунке (графе) обозначаются вершинами, а мосты – ребрами, соединяющими данные вершины. Граф 7 кёнигсбергских мостов имел 4 нечётные вершины (то есть все, его вершины были нечетные), следовательно, невозможно пройти по всем 7 мостам, не проходя ни по одному из них дважды.
Казалось бы, у такого необычного открытия не может быть никакого реального применения и практической пользы. Но применение нашлось, и еще какое. Теория графов, созданная Леонардом Эйлером, легла в основу проектирования коммуникационных и транспортных систем, она используется в программировании и информатике, в физике, химии и многих других науках и областях.
Но самое интересное в том, что историки считают, что есть человек, который решил данную задачу, он смог пройти через все мосты только один раз, правда теоретически, но решение было…. А произошло это вот как...
Кайзер (император) Вильгельм славился своей простотой мышления, прямотой и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на данном приёме. Они показали кайзеру карту города Кёнигсберга, и попросили его попробовать решить эту знаменитую задачку, которая по определению была просто не решаемой. К всеобщему удивлению, Кайзер попросил лист бумаги и перо, и при этом уточнил, что решит данную задачку всего за полторы минуты. Ошеломлённые ученные не могли поверить своим ушам, но чернила и бумагу быстро нашли для него. Кайзер положил листок на стол, взял перо, и написал: «Приказываю построить восьмой мост на острове Ломзе». И все задача решена…..
Так в городе Кёнигсберг и появился новый 8 мост через реку, который так и назвали - мост Кайзера. А задачку с 8 мостами теперь может решить даже ребёнок.