Задача о семи мостах Кенигсберга, Леонард Эйлер и теория графов
С давних времен жители Кенигсберга бились над загадкой: можно ли пройти по всем мостам, пройдя по каждому только один раз? Эту задачу решали и теоретически, на бумаге, и на практике, на прогулках - проходя по этим самым мостам. Никому не удавалось доказать, что это неосуществимо, но и совершить такую «загадочную» прогулку по мостам никто не мог.
В 1736 году известный математик, член Петербургской академии наук Леонард Эйлер взялся решить задачу о семи мостах. В том же году он написал об этом инженеру и математику Мариони. Эйлер писал, что нашел правило, по которому нетрудно вычислить, можно ли пройти по всем мостам и при этом ни по одному не пройти дважды. На семи мостах Кенигсберга сделать это невозможно. На схеме города (графе) ребра графа соответствуют мостам, а вершины графа (точки, в которых соединяются линии) - частям города.
Размышляя над задачей, Эйлер сделал следующие выводы:
вершины графа могут быть четными и нечетными одним росчерком пера можно начертить граф, все вершины которого четные, можно начать в любой вершине графа и закончить этой же вершиной число нечетных вершин (таких, к которым ведет нечетное число ребер) должно быть нечетным, граф с четным числом нечетных вершин, не существует невозможно начертить одним росчерком граф с более чем двумя нечетными вершинами. У графа кенигсбергских мостов четыре нечетных вершины, то есть все. Таким образом, пройти по всем мостам, ни по одному не проходя дважды, не представляется возможным.
Теория графов Леонарда Эйлера нашла применение не только в задачах на сообразительность. Ею пользуются при изучении коммуникационных и транспортных систем, например, для маршрутизации данных в Интернете
Нетрадиционное решение задачи о семи мостах Кенигсберга
Именно благодаря этой задаче о мостах на карте старого Кенигсберга появился еще один мост, с помощью которого соединялся остров Ломзе с южной стороной. Это произошло таким образом. Император (кайзер) Вильгельм был известен простотой мышления, быстрой реакцией и солдатской «недалекостью».
На одном из приемов, где присутствовал кайзер, приглашенные ученые умы вздумали сыграть с ним шутку: Вильгельму показали карту Кенигсберга, предложив разрешить задачу о мостах. Задача же заведомо была нерешаемой.
Вильгельм, к общему удивлению, потребовал перо и бумагу, заявив, что задача разрешима и он решит ее за считанные минуты. Бумагу и чернила нашли, хотя никто не мог поверить, что кайзер Вильгельм обладает решением этой задачи. На поданном листке бумаги кайзер написал: «приказываю построить восьмой мост на острове Ломзе». Новый мост назвали мостом Кайзера. Этот восьмой мост сделал задачу о мостах легкой забавой даже для ребенка. #КёнигсбергКалининград
Тунцеловы
:Юрий Чудновский
Задача о семи мостах Кенигсберга, Леонард Эйлер и теория графов
В 1736 году известный математик, член Петербургской академии наук Леонард Эйлер взялся решить задачу о семи мостах. В том же году он написал об этом инженеру и математику Мариони. Эйлер писал, что нашел правило, по которому нетрудно вычислить, можно ли пройти по всем мостам и при этом ни по одному не пройти дважды. На семи мостах Кенигсберга сделать это невозможно.
На схеме города (графе) ребра графа соответствуют мостам, а вершины графа (точки, в которых соединяются линии) - частям города.
вершины графа могут быть четными и нечетными
одним росчерком пера можно начертить граф, все вершины которого четные, можно начать в любой вершине графа и закончить этой же вершиной
число нечетных вершин (таких, к которым ведет нечетное число ребер) должно быть нечетным, граф с четным числом нечетных вершин, не существует
невозможно начертить одним росчерком граф с более чем двумя нечетными вершинами.
У графа кенигсбергских мостов четыре нечетных вершины, то есть все. Таким образом, пройти по всем мостам, ни по одному не проходя дважды, не представляется возможным.
Теория графов Леонарда Эйлера нашла применение не только в задачах на сообразительность. Ею пользуются при изучении коммуникационных и транспортных систем, например, для маршрутизации данных в Интернете
Нетрадиционное решение задачи о семи мостах Кенигсберга
Именно благодаря этой задаче о мостах на карте старого Кенигсберга появился еще один мост, с помощью которого соединялся остров Ломзе с южной стороной. Это произошло таким образом. Император (кайзер) Вильгельм был известен простотой мышления, быстрой реакцией и солдатской «недалекостью».
На одном из приемов, где присутствовал кайзер, приглашенные ученые умы вздумали сыграть с ним шутку: Вильгельму показали карту Кенигсберга, предложив разрешить задачу о мостах. Задача же заведомо была нерешаемой.
Вильгельм, к общему удивлению, потребовал перо и бумагу, заявив, что задача разрешима и он решит ее за считанные минуты. Бумагу и чернила нашли, хотя никто не мог поверить, что кайзер Вильгельм обладает решением этой задачи. На поданном листке бумаги кайзер написал: «приказываю построить восьмой мост на острове Ломзе». Новый мост назвали мостом Кайзера. Этот восьмой мост сделал задачу о мостах легкой забавой даже для ребенка.
#КёнигсбергКалининград