Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
Проблема семи мостов Кёнигсберга
Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах (нем. Königsberger Brückenproblem) - старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером.
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».
Решение задачи по Леонарду Эйлеру
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды
Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете).
Дальнейшая история мостов Кёнигсберга
В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути.
7 мостов города Калининграда(Кенингсберга) обусловили создание Леонардом Эйлером так называемой теории графов.
Граф – это определенное число узлов (вершин), которые соединены рёбрами. Два острова и берега на реке Прегель, где и стоял, были соединены 7 мостами. Известный философ и ученый И. Кант, прогуливаясь по мостам Кенигсберга, придумал задачу, которая известна всем в мире как задача " о 7 кенигсбергских мостах": можно ли пройти по всем данным мостам и при этом вернуться в исходную точку маршрута так, чтобы пройти по каждому мосту только один раз?
Многие пробовали решить эту задачу как практически, так и теоретически. Но ни у кого это не получалось. Потому считается, что в 17-м веке у жителей пошла особенная традиция: прогуливаясь по городу, пройти по всем мостам только по одному разу. Но, естественно, ни у кого это не получалось.
В 1736 году эта задача заинтересовала ученого Леонарда Эйлера, который был выдающимся и знаменитым математиком и членом Петербургской академии наук.Он смог найти правило, благодаря которому можно было решить эту загадку. В ходе своих суждений Эйлер сделал такие выводы: 1. количество нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётным. Не может существовать граф, который имел бы нечётное число нечётных вершин. 2. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. 3. Граф с более чем 2 нечётными вершинами невозможно начертить одним росчерком.
Отсюда следует вывод,что невозможно пройти по всем семи мостам, не проходя ни по одному из них два раза. Впоследствии эта теория графов стала основой проектирования коммуникационных и транспортных систем, стала широко использоваться в программировании,информатике, физике, химии и многих других науках и сферах.
Примечательно, что историки считают, что есть человек, который решил данную задачу, что он смог пройти через все мосты лишь единожды, правда теоретически….
А было это так. Кайзер (то есть император) Вильгельм был знаменит своей простотой мышления, прямотой и «недалёкостью». Как-то раз он чуть не стал жертвой шутки, которую с ним сыграли учёные умы- шутники показали кайзеру карту города Кёнигсберга и попросили его попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Но Кайзер только попросил лист и перо, при этом уточнив, что решит ее всего за 1,5 минуты. Ученые были поражены - Вильгельм написал: «Приказываю построить восьмой мост на острове Ломзе». Вот и все, задача решена... Так в Калининграде и появился новый восьмой мост через реку, названный в честь Кайзера. А задачу с восемью мостами может решить и ребёнок...
Муниципальное автономное образовательное учреждение
«Средняя общеобразовательная школа №6» г.Перми
История математики
Старая-старая задача о мостах Кенигсберга
Выполнил: Железнов Егор,
ученик 10 «а» класса
Руководитель: Орлова Е. В.,
учитель математики
2014, г. Пермь
Введение …………………………………………………………………………..3
История мостов Кенигсберга …………………………………………................4
Задача о семи мостах Кенигсберга ………………………………………….......8
Вычерчивание фигур одним росчерком ……………………………………….12
Заключение ………………………………………………………………………15
Список литературы...…………………………………………………………….16
Приложение 1 ……………………………………………………………………18
Приложение 2 ……………………………………………………………………22
Приложение 3 ……………………………………………………………………23
Приложение 4 ……………………………………………………………………26
Ведение
Кенигсберг – это историческое название Калининграда, центра самой западной области России, знаменитой своим мягким климатом, пляжами и изделиями из янтаря. Калининград обладает богатым культурным достоянием. Здесь в свое время жили и трудились великий философ И. Кант, сказочник Эрнст Теодор Амадей Гофман, физик Франц Нейман и многие другие, чьи имена вписаны в историю науки и творчества. С Кенигсбергом связана одна интересная задача, так называемая задача о мостах Кенигсберга.
Цель нашего исследования: изучить историю возникновения задачи о мостах Кенигберга, рассмотреть её решение, выяснить роль задачи в развитии математики.
Для достижения цели необходимо решить следующие задачи:
изучить литературу по данной теме;
систематизировать материал;
подобрать задачи в решении которых используется прием решения задачи о мостах Кентгсберга,;
составить библиографический список литературы.
История мостов Кенигсберга
Возникший в город Кёнигсберг (ныне ) состоял из трёх формально независимых городских поселений и ещё нескольких «слобод» и «посёлков». Расположены они были на островах и берегах реки (ныне Преголя), делящей город на четыре главные части: , , и . Для связи между городскими частями уже в стали строить . В связи с постоянной военной опасностью со стороны соседних и , а также по причине междоусобиц между Кёнигсбергскими городами (в - между городами даже произошла война, вызванная тем, что Кнайпхоф перешёл на сторону Польши, а Альтштадт и Лёбенихт остались верны ) в кёнигсбергские мосты имели оборонные качества. Перед каждым из мостов была построена оборонительная башня с закрывающимися подъёмными или двустворчатыми воротами из дуба и с железной кованой обивкой. Да и сами мосты приобретали характер оборонительных сооружений. Опоры некоторых мостов имели пятиугольную форму, типичную для бастионов. Внутри этих опор располагались казематы. Из опор можно было вести огонь через амбразуры.
Мосты были местом шествий, религиозных и праздничных процессий, а в годы так называемого «Первого русского времени» (-), когда во время Семилетней войны Кёнигсберг ненадолго вошёл в состав , по мостам проходили крестные ходы. Один раз такой крестный ход даже был посвящён православному празднику Водосвятия реки Прегель, вызвавшему неподдельный интерес у жителей Кёнигсберга.
К концу 19 века в Кёнигсберге было построено 7 основных мостов (Приложение 1).
Самый старый из семи мостов Лавочный мост (Krämerbrücke/ Крэмер-брюке). Он был построен в 1286 году. Само название моста говорит само за себя. Площадь, которая прилегала к нему, была местом оживлённой торговли. Он связывал два средневековых города Альтштадт и Кнайпхоф. Построен он был сразу же в камне. В 1900 году он был перестроен и сделан разводным. По мосту стали ходить трамваи. Во время войны он был сильно разрушен, но восстановлен, пока в 1972 году не был демонтирован.
Вторым по возрасту был Зелёный мост (Grüne Brücke/Грюне-брюке) . Он был построен в . Этот мост связал остров Кнайпхоф с южным берегом Прегеля. Он так же был каменным и трёхпролётным. В 1907 году мост был перестроен, средний пролёт стал разводным и по нему стали ходить трамваи. Во время войны этот мост сильно пострадал, был восстановлен, а в 1972 году - демонтирован. Название моста происходит от цвета краски, в который традиционно красили опоры и пролётное строение моста. В у Зелёного моста гонец раздавал прибывшие в Кёнигсберг письма. В ожидании корреспонденции здесь собирались деловые люди города. Здесь же в ожидании почты они обсуждали свои дела. Неудивительно, что именно в непосредственной близости от Зелёного моста в была построена кёнигсбергская торговая . В на другом берегу Прегеля, но также в непосредственной близости от Зелёного моста было построено новое здание торговой биржи, сохранившееся до сих пор (ныне Дворец культуры моряков). В 1972 году вместо Зелёного и Лавочного мостов был построен Эстакадный мост.
После Лавочного и Зелёного был построен Рабочий мост (Koettelbrucke/ Кёттель или Киттель-брюке), также соединявший Кнайпхоф и Форштадт. Иногда название также переводят как Потроховой мост. И тот, и другой вариант перевода не является идеальным, так как немецкое название происходит из и по-русски означает примерно «рабочий, вспомогательный, предназначенный для провоза мусора» и.т.п. Этот мост был построен в . Он соединил город Кнайпхоф с пригородом Форштадт. Мост был наполовину каменным, а пролёты - деревянные настилы. В 1621 году, во время сильного наводнения, мост сорвало и унесло в реку. Мост возвратили на место. В 1886 году его заменили новым, стальным, трёхпролётным, разводным. По нему тоже ходили трамваи. Мост был разрушен во время и позднее не восстанавливался.
Семь мостов Кенигсберга – Википедия (ru /wikipedia .ord )
Теория графов – сайт www .ref .by /refs
Приложение 1
Лавочный мост
Зеленый мост
Потроховый мост
Кузнечный мост
Деревянный мост
Высокий мост
Медовый мост. Вид сбоку на
бывший разводной пролёт.
Медовый мост. Остатки разводного механизма.
Кайзера мост
Приложение 2
Леонард Эйлер
Н
емецкий и русский математик, механик и физик. Родился 15 апреля 1707 г. в Базеле. Учился в Базельском университете (в 1720–1724 гг.), где его учителем был Иоганн Бернулли. В 1722 г. получил степень магистра искусств. В 1727 г. переехал в Санкт-Петербург, получив место адъюнкт-профессора в недавно основанной Академии наук и художеств. В 1730 г. стал профессором физики, в 1733 г. – профессором математики. За 14 лет своего первого пребывания в Петербурге Эйлер опубликовал более 50 работ. В 1741–1766 гг. работал в Берлинской академии наук под особым покровительством Фридриха II и написал множество сочинений, охватывающих по существу все разделы чистой и прикладной математики. В 1766 г. по приглашению Екатерины II Эйлер возвратился в Россию. Вскоре после прибытия в Санкт-Петербург полностью потерял зрение из-за катаракты, но благодаря великолепной памяти и способностям проводить вычисления в уме до конца жизни занимался научными исследованиями: за это время им было опубликовано около 400 работ, общее же их число превышает 850. Умер Эйлер в Санкт-Петербурге 18 сентября 1783 г.
Труды Эйлера свидетельствуют о необычайной разносторонности автора. Широко известен его трактат по небесной механике «Теория движения планет и комет». Автор книг по гидравлике, кораблестроению, артиллерии. Наибольшую известность принесли Эйлеру исследования в области чистой математики.
Приложение 3
Задачи
З
адача 1
(задача о мостах Ленинграда). В одном из залов Дома занимательной науки в Санкт-Петербурге посетители показывали схему мостов города (рис.). Требовалось обойти все 17 мостов, соединяющих острова и берега Невы, на которых расположен Санкт-Петербург. Обойти надо так, чтобы каждый мост был пройден один раз.
И перерезавши кварталы,
Всплывают вдруг из темноты
Санкт-Петербургские каналы,
Санкт-Петербургские мосты!
(Н. Агнивцев)
Д
окажите, что требуемый уникурсальный обход всех мостов Санкт-Петербурга того времени возможен, но не может быть замкнутым, т. е. оканчиваться
в
пункте, от которого начинался.
Задача 2. На озере находится семь островов, которые соединены между собой так, как показано на рисунке. На какой остров должен доставить путешественников катер, чтобы они могли пройти по каждому мосту и только один раз? Почему нельзя доставить путешественников на остров A? 17
З
адача 3.
(В поисках сокровищ)
.
На рис. изображен план подземелья, в одной из комнат которого скрыты богатства рыцаря. Чтобы безопасно проникнуть в эту комнату, надо, войти через определенные ворота в одну из крайних комнат подземелья, пройти последовательно через все 29 дверей, выключая сигнализацию тревоги. Проходить дважды через одни и те же двери нельзя. Определить номер комнаты в которой скрыты сокровища и ворота через которые нужно войти? 20
З
адача 4
. Павлик -заядлый велосипедист - изобразил на классной доске часть плана местности и поселка (рис.8), где он жил прошлым летом. По рассказу Павлика, недалеко от поселка, расположившегося по берегам реки Оя, есть маленькое глубокое озерцо, питающееся подземными источниками. От него и берет начало Оя, которая при входе поселок разделяется на две отдельные речушки, соединенные естественным каналом так, что образуется зеленый остро
вок
(на рисунке отмечен буквой
А)
с пляжем и спортплощадкой. Далек
о
за поселком обе речушки, сливаясь, образуют широкую реку. Павлик утверждает, что, возвращаясь на велосипеде со спортивной
площадки, находящейся на острове, домой (на рисунке буква
D
),
он проезжает по одному разу по всем восьми мостикам, показанным на плане, ни разу не прерывая движения. Наши знатоки теории таких головоломок отметили буквами
А, В, С,
D
участки поселка, разъединенные речкой (участки - это узлы сети, мосты - ветви), и установили, что уникурсальный маршрут, начинающийся в
А
(нечетном узле), возможен, но закончиться он должен непременно в В - во втором нечетном узле, остальные два узла
С
и
D
- четные. Но ведь и Павлик говорит правду: его маршрут из
А
в
D
действительно пролегал по всем восьми мостикам и был уникурсальным. В чем же здесь дело? Как вы полагаете?
З
адача 5
. Английский математик Л.Кэрролл (автор всемирно известных книг «Алиса в стране чудес», «Алиса в Зазеркалье» и др.) любил задавать своим маленьким друзьям головоломку на обход фигуры (рис.9)
единым росчерком пера и не проходя дважды ни одного участка контура. Пересечение линий допускалось. Такая задача решается просто.
Усложним ее дополнительным требованием: при каждом переходе через узел (считая узлами точки пересечения линий на рисунке) направление обхода должно изменяться на 90°. (Начиная обход с любого узла, придется сделать 23 поворота) 6 .
Задача 6 . (Муха в банке) Муха забралась в банку из-под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается. 22
З
адача 7
.
На рисунке изображена птица. Можно ли нарисовать ее одним росчерком?
З
адача 8
.
На
рис.10 представлен эскиз одного из портретов Эйлера. Художник воспроизвел его одним росчерком пера (только волосы нарисованы отдельно). Где на рисунке расположены начало и конец уникурсального контура? Повторите движение пера художника (волосы и пунктирные линии на рисунке не включаются
в
маршрут обхода)
6
.
Рис.10
З
адача 9 . Начертить одним росчерком следующие фигуры. (Такие фигуры называются уникурсальными (от латинского unus – один, cursus –путь)).
Приложение 4
Решение задач
1
.
3
. Для решения нужно построить граф, где вершины – номера комнат, а ребра – двери.
Нечетные вершины: 6, 18. Так как количество нечетных вершин = 2, то безопасно проникнуть в комнату с сокровищами можно.
Начать путь нужно через ворота В , а закончить в комнате № 18 .
5
.
Пример требуемого обхода дан на рисунке
6
. Ребра и вершины куба образуют граф, все 8 вершин которого имеют кратность 3 и, следовательно, требуемый условием обход невозможен.
7. Взяв за вершины графа точки пересечения линии, получим 7 вершин, только две из которых имеют нечетную степень. Поэтому в этом графе существует эйлеров путь, а значит, его (т.е. птицу) можно нарисовать одним росчерком. Начать путь нужно в одной нечетной вершине, а закончить в другой.
8. Начать обход надо с нечетного узла в уголке правого глаза и закончить в нечетном узле брови над левым глазом (пунктирные линии в сеть не входят). Все остальные узлы на рисунке четные.
9
.
Рассмотрев эту задачу, в 1736 году Эйлер доказал, что это невозможно, причем он рассмотрел более общую задачу: какие местности, разделенные рукавами рек и соединенные мостами, возможно обойти, побывав на каждом мосту ровно один раз, а какие невозможно.
кенигсбергских мостов">
Несколько модифицируем задачу. Каждую из рассматриваемых местностей, разделенных рекой, обозначим точкой, а соединяющие их мосты – отрезком линии (не обязательно прямой). Тогда вместо плана будем работать просто с некой фигурой, составленной из отрезков кривых и прямых. Такие фигуры в современной математике называются графами, отрезки – ребрами, а точки, которые соединяют ребра – вершинами. Тогда исходная задача эквивалентна следующей: можно ли начертить данный граф, не отрывая карандаша от бумаги, то есть таким образом, чтобы каждое его ребро пройти ровно один раз.
Такие графы, которые можно начертить, не отрывая карандаша от бумаги, называются уникурсальными (от латинского unus cursus – один путь), или эйлеровыми. Итак, задача ставится таким образом: при каких условиях граф уникурсален? Ясно, что уникурсальный граф не перестанет быть уникурсальным, если изменить длину или форму его ребер, а также изменить расположение вершин – лишь бы не менялось соединение вершин ребрами (в том смысле, что если две вершины соединены, они должны оставаться соединенными, а если разъединены – то разъединенными).
Если граф уникурсален, то и топологически эквивалентный ему граф тоже будет уникурсальным. Уникурсальность, таким образом, является топологическим свойством графа.
Во-первых, надо отличать связные графы от несвязных. Связными называются такие фигуры, что любые две точки можно соединить каким-нибудь путем, принадлежащим этой фигуре. Например, большая часть букв русского алфавита связны, но вот буква Ы – нет: невозможно перейти с ее левой половинки на правую по точкам, принадлежащим этой букве. Связность – это топологическое свойство: оно не меняется при преобразованиях фигуры без разрывов и склеек. Понятно, что если граф уникурсален, то он обязан быть связным.
Во-вторых, рассмотрим вершины графа. Будем называть индексом вершины число ребер, встречающихся в этой вершине. Теперь зададимся вопросом: чему могут равняться индексы вершин уникурсального графа.
Здесь может быть два случая: линия, вычерчивающая граф, может начинаться и заканчиваться в одной и той же точке (назовем ее «замкнутый путь»), а может в разных (назовем ее «незамкнутый путь»). Попробуйте сами нарисовать такие линии – с какими хотите самопересечениями – двойными, тройными и т. д. (для наглядности лучше, чтобы ребер было не больше 15).
Нетрудно видеть, что в замкнутом пути все вершины имеют четный индекс, а в незамкнутом – ровно две имеют нечетный (это начало и конец пути). Дело в том, что, если вершина не является начальной или конечной, то, придя в нее, надо затем из нее выйти – таким образом, сколько ребер входят в нее, столько же выходят из нее, а всего число входящих и исходящих ребер будет четным. Если начальная вершина совпадает с конечной, то ее индекс также четен: сколько ребер из нее вышло, столько же и вошло. А если начальная точка не совпадает с конечной, то их индексы нечетные: из начальной точки нужно один раз выйти, а затем, если в нее и вернемся, то выйти снова, если еще раз вернемся – опять выйти, и т. д.; а в конечную нужно придти, а если из нее потом и выходим, то опять нужно вернуться, и т. д.
Итак, чтобы граф был уникурсальным, необходимо, чтобы все его вершины имели четный индекс либо чтобы число вершин с нечетным индексом равнялось двум.
 |
Посчитайте индексы его вершин и убедитесь, что он никак не может быть уникурсальным. Вот поэтому-то у вас ничего не получалось, когда вы хотели обойти все мосты...
Возникает вопрос: а если в связном графе нет вершин с нечетным индексом либо таких вершин ровно две, то обязательно ли граф уникурсален? Можно строго доказать, что да! Таким образом, уникурсальность однозначно связана с числом вершин с нечетным индексом.
Упражнение: постройте на схеме кенигсбергских мостов еще один мост – там, где захотите – чтобы полученные мосты можно было бы обойти, побывав на каждом ровно по разу; реально проделайте такой путь.
Теперь еще один интересный факт: оказывается, любую систему местностей, соединенных мостами, можно обойти, если необходимо побывать на каждом мосту ровно два раза! Попробуйте это доказать самостоятельно.
| НОВОСТИ ФОРУМА Рыцари теории эфира | 01.10.2019 - 05:20: -> - Карим_Хайдаров. 30.09.2019 - 12:51: |
Нетрадиционные решения задачи
«Решение» Кайзера
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже и соединявший остров Ломзе с южной стороной. Своим появлением этот мост обязан самой задаче Эйлера-Канта. Произошло это при следующих обстоятельствах.
Император Вильгельм был известен своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали Кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, Кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли.
Кайзер положил листок на стол, взял перо и написал следующее: «Приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который назвали «мостом Кайзера». А задачу с восемью мостами теперь мог решить даже ребёнок.
См. также
Литература
Wikimedia Foundation . 2010 .