Основы теории графов, задача о Кёнигсбергских мостах
Первые задачи теории графов связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задача о перевозках, задача о кругосветном путешествии). Одним из первых результатов в теории графов явился критерий существования обхода графа без повторений, полученный Леонардом Эйлером, при решении задачи о Кенигсбергских мостах.
Скачать:
| Вложение | Размер |
|---|---|
 Основы теории графов, задача о Кёнигсбергских мостах | 1.57 МБ |
Предварительный просмотр:
Подписи к слайдам:
Содержание Решение задачи по Л.Эейлеру 4 Леонард Эйлер 1 Теория графов 2 Проблема семи мостов Кенигсберга 3 Дальнейшая история Кенигсберга 5 В современном мире… 6 6
Выдающийся математик и механик, внёсший фундаментальный вклад в развитие этих наук (а также физики, астрономии и ряда прикладных наук). Л.Эйлер — автор более чем 850 работ ( включая два десятка фундаментальных монографий) по математическому анализу, дифференциальной геометрии , теории чисел, приближённым вычислениям, небесной механике, математической физике, оптике, баллистике , кораблестроению , теории музыки и другим областям Он глубоко изучал медицину, химию, ботанику, воздухоплавание, теорию музыки, множество европейских и древних языков. Почти полжизни провёл в России, где внёс существенный вклад в становление российской науки. В 1726 году он был приглашён работать в Санкт-Петербург, куда переехал годом позже. С 1726 по 1741, а также с 1766 года был академиком Петербургской академии наук (будучи сначала адъюнктом, а с 1731 года — профессором); в 1741—1766 годах работал в Берлине (оставаясь одновременно почётным членом Петербургской академии ). Уже через год пребывания в России он хорошо знал русский язык и часть своих сочинений (особенно учебники) публиковал на русском. Леонард Эйлер
Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической. Первые задачи теории графов связаны с решением математических развлекательных задач и головоломок (задача о Кенигсбергских мостах, задача о расстановке ферзей на шахматной доске, задача о перевозках, задача о кругосветном путешествии). Одним из первых результатов в теории графов явился критерий существования обхода графа без повторений, полученный Леонардом Эйлером, при решении задачи о Кенигсбергских мостах. Наглядное представление о графе можно получить, если представить себе некоторое множество точек плоскости Х, называемых вершинами, и множество направленных или ненаправленных отрезков М, соединяющих все или некоторые из вершин и называемых дугами. Математически граф определяется как пара множеств (Х, Г). Теория графов
Проблема семи мостов Кенигсберг а или Задача о Кенигсбергских мостах (нем. Königsberger Brückenproblem ) — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кенигсберга , не проходя ни по одному из них дважды. Впервые была решена в 1736 году немецким и русским математиком Леонардом Эйлером. Издавна среди жителей Кенигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя ), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя». Проблема семи мостов Кенигсберга
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель . В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин . Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком . Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете). Решение задачи по Л.Элейру
Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины ( то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
В 1905 году был построен Императорский мост, который был впоследствии разрушен в ходе бомбардировки во время Второй мировой войны. Существует легенда о том, что этот мост был построен по приказу самого кайзера, который не смог решить задачу мостов Кёнигсберга и стал жертвой шутки, которую сыграли с ним учёные умы, присутствовавшие на светском приёме (если добавить восьмой мост, то задача становится разрешимой). На опорах Императорского моста в 2005 году был построен Юбилейный мост. На данный момент в Калининграде семь мостов, и граф, построенный на основе островов и мостов Калининграда, по-прежнему не имеет эйлерова пути. Дальнейшая история мостов Кенигсберга
В середине 19 в. появились работы, в которых при решении практических задач были получены результаты, относящиеся к теории графов (составление полной системы уравнений для токов и напряжений в электрической схеме ). В 20 в. задачи, связанные с графами, начали возникать не только в физике, химии, электротехнике биологии, экономике, социологии и т.д., но и в алгебре, теории вероятностей, теории чисел (наряду с термином «граф» употреблялись и другие термины, например, карта, комплекс, диаграмма, сеть, лабиринт ). В современном мире...
Использованные источники: 1.Основы теории графов, задача о Кенигсбергских мостах (Л. Эйлер ) - сайт http://www.decoder.ru/ 2. Задача о семи Кёнигсбергских мостах – сайт https :// ru.wikipedia.org/wiki