Задача о семи мостах

колледж»


Автор: Михайлова Мария Борисовна, преподаватель математики

к развитию, теория графов получила на рубеже ХIX и ХХ

столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Графы стали использоваться при построении схем электрических цепей и молекулярных схем. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия.
Именно это я и рассмотрела в своей работе.
Меня заинтересовала задача было интересно узнавать о графах.
В школьном курсе мне была не известна задача о семи мостах, как и графы, а в работе я изучила это понятие и задачу.
Цели моей работы:
Расширение и углубление знаний о графах.
Знакомство с историей задачи о «Семи мостах».

Леонарда Эйлера. Историю возникновения этой теории можно проследить по переписке

великого ученого.
Вот перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года:
«Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство... После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. …»

способностей, математической интуиции, умений анализировать и обобщать.
Приобретение навыков поисковой и

исследовательской деятельности.
Приобретение опыта создания презентаций.

человек дышит или как орёл парит над землёй

Доминик Араго

Леонард Эйлер (1707-1783) - математик, механик, физик и астроном. Он автор более 850 трудов по механике, теории движения Луны и планет, по географии, по теории кораблестроения, теории музыки и другим наукам.

времён и народов. Основоположник теории чисел и теории графов, один

из основоположников математической физики и комплексного анализа, создатель первых методов численного решения дифференциальных уравнений. Гений аналитических преобразований, отыскавший множество способов решения и упрощения самых разных задач дифференциального и интегрального исчисления. Открыватель потрясающих по красоте законов, связывающих между собой разные области математики. Книги Эйлера отличаются чрезвычайной ясностью и наглядностью, они ничуть не устарели и сегодня.

(сейчас этот город называется Калининград) стали «виновниками» создания Леонардом

Эйлером теории графов.
Граф – это определенное количество узлов (вершин), соединённых рёбрами. Изящная по своей конкретности задача семи мостов Кёнигсберга была сформулирована Эйлером в 1759 г. следующим образом: "как пройти по семи мостам, не проходя по одному дважды".

понятие «графа» как множества непересекающихся рёбер или связей, соединяющих пары

вершин.

Так выглядит этот граф, если наложить вершины и связи на карту центра города.

хотя термин “граф” впервые ввёл в 1736 году венгерский математик

Денеш Кёниг.
Графы – схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

Точки - вершины графа; линии, которые соединяют вершины - рёбра графа.

начертить одним росчерком. Движение надо начинать от любой нечётной вершины,

а заканчивать на другой нечётной вершине.

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

5 связей - они неправильные. Поэтому, непрерывной «дорожки Эйлера», которая

проходит через каждую вершину только единожды для этого числа не существует.

города на рисунке (графе) обозначаются вершинами, а мосты – ребрами,

соединяющими данные вершины. Граф 7 кёнигсбергских мостов имел 4 нечётные вершины (то есть все, его вершины были нечетные), следовательно, невозможно пройти по всем 7 мостам, не проходя ни по одному из них дважды.

может быть никакого реального применения и практической пользы. Но применение

нашлось, и еще какое. Теория графов, созданная Леонардом Эйлером, легла в основу проектирования коммуникационных и транспортных систем, она используется в программировании  и информатике, в физике, химии и многих других науках и областях.
Но самое интересное в том, что историки считают, что есть человек, который решил данную задачу, он смог пройти через все мосты только один раз, правда теоретически, но решение было…. А произошло это вот как...

прямотой и солдатской «недалёкостью». Однажды, находясь на светском рауте, он

чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на данном приёме. Они показали кайзеру карту города Кёнигсберга, и попросили его попробовать решить эту знаменитую задачку, которая по определению была просто не решаемой. К всеобщему удивлению, Кайзер попросил лист бумаги и перо, и при этом уточнил, что решит данную задачку всего за полторы минуты. Ошеломлённые ученные не могли поверить своим ушам, но чернила и бумагу быстро нашли для него. Кайзер положил листок на стол, взял перо, и написал: «Приказываю построить восьмой мост на острове Ломзе». И все задача решена…

Так в городе Кёнигсберг и появился новый 8 мост через реку, который так и назвали — мост Кайзера. А задачку с 8 мостами теперь может решить даже ребёнок.

правило фаз также может быть интерпретировано как задача теории графов);

компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.
В информатике и программировании (граф-схема алгоритма)
В коммуникационных и транспортных системах. В частности, для маршрутизации данных в Интернете.
В экономике.
В логистике.
В схемотехнике (топология межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф).