Презентация. Исследовательская работа по математике Применение графов при оптимизации доставки продуктов

ИССЛЕДОВАТЕЛЬСКАЯ РАБОТА ПО МАТЕМАТИКЕ«ПРИМЕНЕНИЕ ГРАФОВ ПРИ ОПТИМИЗАЦИИ ДОСТАВКИ ПРОДУКТОВ» Выполнил ученик 9-а классаСергей Олегович ОгневРуководитель работы учитель математикиНаталья Сергеевна Лебедева с. Веселоярск, 2015 Задачи:1) Познакомиться с математическим понятием «графы»2) Дать несколько научных определений и выбрать самое подходящее из них3) Рассказать об истории появления графов и их дальнейшем развитии4) Привести примеры задач, решаемые с помощью графов5) Доказать актуализацию графов в наше время на конкретном примере Цель: рассчитать оптимальный путь доставки продуктов в с. Веселоярск Понятие графа Родоначальником теории графов принято считать математика Леонарда Эйлера (1707-1783). Историю возникновения этой теории можно проследить по переписке великого ученого. Нам предоставлен перевод латинского текста, который взят из письма Эйлера к итальянскому математику и инженеру Маринони, отправленного из Петербурга 13 марта 1736 года: История возникновения "Некогда мне была предложена задача об острове, расположенном в городе Кенигсберге (Калининград) и окруженном рекой, через которую перекинуто семь мостов. Спрашивается, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. И тут же мне было сообщено, что никто еще до сих пор не мог это проделать, но никто и не доказал, что это невозможно. Вопрос этот, хотя и банальный, показался мне, однако, достойным внимания тем, что для его решения недостаточны ни геометрия, ни алгебра, ни комбинаторное искусство. После долгих размышлений я нашел легкое правило, основанное на вполне убедительном доказательстве, с помощью которого можно во всех задачах такого рода тотчас же определить, может ли быть совершен такой обход через какое угодно число и как угодно расположенных мостов или не может. Кенигсбергские же мосты расположены так, что их можно представить на следующем рисунке, на котором О обозначает остров, а К1, К2 и К3 – части континента, отделенные друг от друга рукавами реки. Семь мостов обозначены буквами a, b, c, d, e, f, g ". Эйлер поступил следующим образом: он «сжал» сушу в точки, а мосты «вытянул» в линии. В результате получилась фигура, изображенная на рисунке. Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог. Кенигсбергские мосты 1.Если все вершины графа четные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф. При этом движение можно начать с любой вершины и окончить в той же вершине.2.Граф с двумя нечетными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечетной вершины, а заканчивать на другой нечетной вершине.3.Граф с более чем двумя нечетными вершинами невозможно начертить одним росчерком. 4.Число нечетных вершин графа всегда четное.5.Если в графе имеются нечетные вершины, то наименьшее число росчерков, которыми можно нарисовать граф будет равно половине числа нечетных вершин этого графа. Свойства графа (правила Эйлера) 1)Граф называется неориентированным связным тогда, когда из любой вершины доступна любая другая вершина. Виды графов 2 )Граф называется ориентированным или орграфом, если он связный, но есть строгая последовательность. Виды графов 3) Граф называется смешанным, если он имеет как направленные, так и ненаправленные ребра. Виды графов 4) Граф называется изоморфным, если он обладает таким свойством,что какая-либо вершина с определенным числом ребер в одном графе имеет тождественную вершину в другом. Виды графов 5) Граф называется взвешенным тогда, когда каждому ребру графа поставлено в соответствие некоторое значение, называемое весом ребра. (В разных задачах в качестве веса могут выступать различные виды измерений). Виды графов Решение задач с помощью графов Задача расчета оптимального пути доставки продуктов в с. Веселоярск Карта села Граф доставки В результате выполнения исследовательской работы был построен граф оптимального пути доставки продуктов в с. Веселоярск.1. Я познакомился с понятием графа и его научным определением.2. Изучил историю появления графов и их развитие.3. Рассмотрел задачи, решаемые с помощью графов.4. Доказал актуальность графов в наше время на примере доставки продуктов в с. Веселоярск. Заключение 1)Уилсон Р. «Ведение в теорию графов», М, 1977г2)Фарков А.В. «Математические олимпиады в школе», М, 20043)Вагнер Ш,, «Управление поставщиками», М.,20024)ru.wikipedia.org5)works.tarefer.ru6)kvodo.ru7)www.studentlibrary.ru Список используемой литературы