Прогулка по мостам
Река, огибающая остров, делится на два рукава, через которые переброшены 7 мостов. Можно ли совершить такую прогулку, чтобы за один раз перейти все эти мосты, не переходя ни через один мост два или более раз? Попробуйте прогуляться с помощью мышки, которая будет рисовать ваш путь. Для очистки пути перезагрузите страницу.
Да, забыл сказать. Ваш путь не должен начинаться внутри островка.
История семи мостов Кёнигсберга
Старинная карта Кёнигсберга. Буквами обозначены части города: А — Альтштадт, Б — Кнайпхоф, В — Ломзе, Г — Форштадт. Цифрами обозначены мосты (в порядке строительства): 1 — Лавочный, 2 — Зелёный, 3 — Рабочий, 4 — Кузнечный, 5 — Деревянный, 6 — Высокий, 7 — Медовый
Возникший в XIII веке город Кёнигсберг (ныне Калининград) состоял из трёх формально независимых городских поселений и ещё нескольких «слобод» и «посёлков». Расположены они были на островах и берегах реки Прегель (ныне Преголя), делящей город на четыре главные части: Альтштадт, Кнайпхоф, Лебенихт. Для связи между городскими частями уже в XIV веке стали строить мосты. В связи с постоянной военной опасностью со стороны соседних Польши и Литвы, а также по причине междоусобиц между Кёнигсбергскими городами (в 1454—1455 году между городами даже произошла война, вызванная тем, что Кнайпхоф перешёл на сторону Польши, а Альтштадт и Лёбенихт остались верны Тевтонскому ордену) в Средние века кёнигсбергские мосты имели оборонные качества. Перед каждым из мостов была построена оборонительная башня с закрывающимися подъёмными или двустворчатыми воротами из дуба и с железной кованой обивкой. Да и сами мосты приобретали характер оборонительных сооружений. Опоры некоторых мостов имели пятиугольную форму, типичную для бастионов. Внутри этих опор располагались казематы. Из опор можно было вести огонь через амбразуры.
Задача о мостах
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу, как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
Упрощённая схема мостов Кёнигсберга.
На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города - точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
- Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин.
- Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
- Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов
Граф кёнигсбергских мостов имел четыре нечётные вершины, следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.
Dmitry 18.02.2009
34 комментария
АНгел ТУпологии (0)
23.11.2012 20:40
1ая задача действительно легко решается, но только из-за неточности рисунка. Все, кто здесь кичится тем, что решил, 100% "прошли по воде", то есть для перемещения из одной части города в другую использовали не только мосты. Увы, этот путь по условию использовать нельзя…
Григорий (0)
25.03.2012 12:15
а мы в колледже ей пару Математики сорвали так и не решили
Оля (3)
18.03.2012 07:24
У меня получилось!
aleksandr (0)
10.09.2011 19:23
…D I POETOMU ,S LEGONCA RESHIL ETU ZADACHU.
Sofy (0)
04.07.2011 13:29
если нельзя начинать путь внутри а заканчивать можно то я прошла!либо я чот туплю)
МОСТОВОЙ (0)
26.03.2011 22:23
ПРОШОЛ МЛЯ
леонард эйлер (0)
18.03.2011 18:29
нам в 5 классе это по логике задавали
mmm (0)
12.02.2011 20:36
Я чото не понял у мну с мостами все ок
mmm (0)
12.02.2011 20:35
Я чото не понял у мну с мостами все ок
Футаме (0)
09.02.2011 20:43
Круть, я с первого взгляда доказала что это невозможно *_* P.s. учусь всего лишь в 10-ом классе..
хаха (2)
20.12.2010 15:10
Может где-то по воздуху прошел! Невозможно! Не спорь!
Гость (-1)
20.12.2010 15:06
Можно начинать хоть откуда и заканчивать где угодно! Но пытаться нужно пойти не по рисунку мостов, а по рисунку графа "Граф Кенигсбергских мостов"! Там вы не пройдете! Невозможно пройти!
Все лохи (0)
05.12.2010 12:36
нельзя пройти я останавливаюсь в середине моста и пипец,Мы всей семьёй решали на острове остаёмся)
Гость (-1)
20.12.2010 15:08
Все лохи: Всей семьей пытались доказать то, что доказано! Вы бы еще семьей попытались доказать, что Земля является плоскостью!
секретзьщ (0)
05.12.2010 06:36
на картинке где проводить линии это возможно
TypHukMeH 333 (0)
19.11.2010 23:46
Эти задания пройти нереально ни одно где бы вы не начинали путь -хоть в середине острова хоть с берегов. И для себя я это доказал сам, даже не зная что это уже доказано, правда не такими заумными фразами. Вы или дважды пройдете по одному мосту или один мост пропускаете, по другому невозможно. А кто пишет что возможно - скачайте картинку, откройте через пайнт, нарисуйте стрелочки как ходите, заливаете на хост какой либо и присылайте ссылку.
Nikmond (5)
25.07.2010 23:41
А у меня получилось.Я не перешёл ни один мост дважды и не начинал внутри островка!
Nikmond (5)
17.08.2010 16:32
Nikmond: Сначала нужно перейти 1 мост потом 2 потом 3 потом 4 потом 5 потом 6 потом 7.У кого тоже получилось?
Евгений Александрови (0)
21.05.2009 16:52
) Эта задача в принципе не решаема, и Эйлер это в свое время доказал! И в самой задаче условие пройти по всем мостам, не проходя не по одному дважды, и при этом прийти в начальную точку. И она не на острове должна находиться. Чтобы теоретически можно было это сделать, нужно достроить еще 2 моста.
Soleil (44)
16.05.2009 14:51
я вроде такого же задания решала. там три кирпичика нужно было перечеркнуть одним росчерком. и тоже не возможно сие проделать
Сергей (42)
29.04.2009 09:05
Всё, теперь понял соль вопроса. Начинать и заканчивать можно где угодно, только вот реку надо мысленно продолжить до краёв рисунка, так что огибать её ни справа ни слева нельзя. Автору незачёт, не разобрался в собственном вопросе, зачем про остров придумывать-то.
Сергей (42)
29.04.2009 08:54
Подозреваю, что в задании имеется в виду, что начать и закончить необходимо в одной точке, иначе задача решается действительно просто.
нюша (-1)
27.04.2009 17:22
прошла и закончила на острове))
Lightpower (0)
22.04.2009 13:34
Я прошёл легко, закончил на острове. В условии не сказано, чтобы линии пересекались, вот я и навертел там как хочу =)
vitek (1)
02.04.2009 01:04
я не смог пройти, думаю ето невозможно, но на реалной карте двух мостов не хватает, может они ранше были???
львенок (1)
17.03.2009 18:30
прошла, но прогулка заканчивается на острове :)
Андрей WOLF (0)
20.02.2009 10:05
Не проблема прошёл сразу. начал с права в низ, а закончил с правой в центр. точнее правила надо ставить. С наступающим 23 февраля.
b (1)
20.02.2009 08:20
Я ток скажу, возьмите катер!
R0mka (18)
19.02.2009 10:04
А какая разница где начинать на островке или на берегу, граф всервно остаетс графом с четырмя нечетными вершинами, и даже если начинать на острове все мосты нельзя пройти.
Димон (-30)
19.02.2009 09:23
Почему у меня (-1)????
Димон (-30)
19.02.2009 09:22
Когда я проходил, пометки не было"Да, забыл сказать. Ваш путь не должен начинаться внутри островка" если без пометки то можно, а если с ней то нельзя
Мефодий (36)
18.02.2009 23:58
Димон, ты ошибся. 1 задание решить невозможно. Прочитай внимательно выводы Эйлера, этот граф нельзя пройти 1 росчерком, потому что у него все 4 вершины - нечетные. Правда, я знаю что уже в наше время построили 8-ой мост слева от острова, и теперь задачу решить можно, начав путь на одном острове и закончив на другом.
Лялина (0)
18.02.2009 22:11
ах как приятно, что и мой родной край вспомнили..))
Димон (-30)
18.02.2009 17:19
а я первое задание сделал!:)