Мосты Кенигсберга и математика

Слайд 1

Слайд 2

Цель исследования: Выяснить, насколько важна теория графов в жизни Задачи исследования: Узнать, что такое графы Найти области применения графов Научиться решать задачи с помощью графов Выяснить, решается ли задача 7 мостов Кёнигсберга

Слайд 3

Знаменитая задача

Слайд 4

История теории графов Леонард Эйлер Он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.

Слайд 5

Что такое граф граф – это совокупность вершин, соединённых ребрами.

Слайд 6

Выводы Леонарда Эйлера Число нечётных вершин графа всегда чётно. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком пера.

Слайд 7

Виды графов изоморфные графы Неориентированный граф Ориентированный граф (орграф) Смешанный граф взвешенный граф

Слайд 8

Где применяется теория графов

Слайд 9

Сложность расчётов Кол-во городов Всего вариантов для расчета Время расчета на компьютере 5 12 1 сек 6 60 5 сек 8 2520 3,5 минуты 10 181 440 4,5 часа 15 43,5 млрд . 12 лет 20 60 тыс. триллионов Больше, чем время жизни вселенной

Слайд 10

Мой опыт В Хабаровск приехал турист. Сегодня он решил посетить несколько достопримечательностей города: Городские пруды, площадь Ленина, Утёс, Речной вокзал и Цирк. Необходимо выбрать кратчайший маршрут обхода всех точек, начав движение от гостиницы Амур. № точки 1 2 3 4 5 6 1 - 6 1 1.8 1.35 2.3 2 6 - 7.1 7.5 8.9 8.1 3 1 7.1 - 2.8 0.66 3.25 4 1.8 7.5 2.8 - 1.8 0.5 5 1.35 8.9 0.66 1.8 - 2.1 6 2.3 8.1 3.25 0.5 2.1 -

Слайд 11

Результат Ответ: найденный маршрут (1,3)(3,5)(5,4)(4,6)(6,2)(2,1) его длина 18.06 км Но этот вариант не является самым оптимальным. Длина наикратчайшего маршрута составляет 17.76 км. Погрешность метода чуть больше 1.5%. Согласитесь ведь это отличный результат.

Слайд 12

Заключение теория графов очень важна не только в математике, но и в других сферах деятельности человека.