Без темы
<<  Теория возникновения опухолей, разнавидности опухолей челюстно-лицевой области Теория Графов  >>
Теория Графов
Теория Графов
Теория Графов – применение в логистике
Теория Графов – применение в логистике
Цели работы:
Цели работы:
Каждый человек ежедневно на подсознательном уровне по нескольку раз
Каждый человек ежедневно на подсознательном уровне по нескольку раз
Линейная транспортная задача
Линейная транспортная задача
История:
История:
Термины и определения:
Термины и определения:
Теоремы
Теоремы
Теорема 3: доказана при решении задачи о “Кёнигсбергских мостах”
Теорема 3: доказана при решении задачи о “Кёнигсбергских мостах”
Задача: “О кругосветном путешествии”
Задача: “О кругосветном путешествии”
Линейная транспортная задача и Теория Графов
Линейная транспортная задача и Теория Графов
Типовая Линейная транспортная задача речного флота и Теория Графов
Типовая Линейная транспортная задача речного флота и Теория Графов

Презентация на тему: «Теория Графов». Автор: AZ. Файл: «Теория Графов.pptx». Размер zip-архива: 1094 КБ.

Теория Графов

содержание презентации «Теория Графов.pptx»
СлайдТекст
1 Теория Графов

Теория Графов

История. Применение в логистике. Линейная транспортная задача.

2 Теория Графов – применение в логистике

Теория Графов – применение в логистике

Для учащихся 2-3 курсов средних специальных учебных заведений по специальности: 180411 Эксплуатация внутренних водных путей. Учебные дисциплины: ЕН.01 Математика; ЕН.05 Элементы прикладной математики. Разработана в соответствии с требованиями: Федерального Государственного Образовательного Стандарта Среднего Профессионального Образования (ФГОС СПО). Учебными программами Федерального Агентства Морского и Речного Транспорта. Преподаватель математики - Жмудь Александр Аркадьевич, НКРУ им. С.И. Дежнева, г. Новосибирск. 2014-2015 гг.

Презентация к уроку

3 Цели работы:

Цели работы:

Общая: 1. Воспитание у обучающихся устойчивых стремлений к знаниям при изучении общеобразовательных дисциплин и математики в частности. Прикладная: 2. Показать курсантам НКРУ им. С.И. Дежнева значение прикладной математики для их будущей профессиональной деятельности. 3. Продемонстрировать курсантам высокую экономическую эффективность речных перевозок, и тем самым закрепить у них уважение к своим будущим специальностям.

4 Каждый человек ежедневно на подсознательном уровне по нескольку раз

Каждый человек ежедневно на подсознательном уровне по нескольку раз

решает основную задачу логистики: Дойти куда-то самым оптимальным путем.

Курсанты 1-го курса - не изучали теорию графов и на дорогу из общежития в библиотеку они тратят в десять раз больше времени, чем курсанты старших курсов.

5 Линейная транспортная задача

Линейная транспортная задача

Это оптимизация транспортных перевозок, в том числе морских и речных - является основной задачей логистики.

При наличии уже 3-4 транспортных средств решений может быть 100 и более, но не все могут оказаться рентабельными! В настоящее время для поиска оптимальных решений перевозок используют Теорию Графов.

6 История:

История:

В некоторых отраслях прикладной деятельности вместо понятия "граф" используется термин "сеть“: сетевой график; сеть железных дорог и т.п.

Логистика – как наука известна со времен Римской империи, где: “ Логист ” – это армейский снабженец. В настоящее время - основная задача логистики, это: Линейная транспортная задача нахождения способов и путей наиболее оптимальной и быстрой доставки грузов, товаров, пассажиров и т.п. к пунктам назначения.

Теория графов - 1736 год - Леонард Эйлер сформулировал первые теоремы новой теории, решая задачу "О кенигсбергских мостах”. Далее теория графов развивалась в виде составления "головоломных задач” для иллюстрации новых теорем. Реальное прикладное развитие теория графов получила в первой половине 20-го века в связи с возникновением массового крупносерийного производства, развитием технологий. - 1936 год - Денеш Кениг ввел в математику термин «граф». - В логистике Теория Графов стала применяться с середины 20-го века.

7 Термины и определения:

Термины и определения:

Рис. 1 – это “Изображение Графа”. А, В, С, D, E – вершины или узлы Графа. Лини AC, AB и др. – “ребра Графа”. Ребра CD и ED – “направленные”, остальные – “ненаправленные”. Из узла D никуда путей нет. Степень вершины = Количеству, связанных с ней ребер. Степени: p(А)= p(B) = p(D) =2; p(E) = p(C) = 3. Гамильтонов путь – наиболее оптимальный путь через все узлы (задача логистики). Гамильтонов путь может быть “замкнутым” или “незамкнутым” Рис. 2 – это “Граф решения” задачи поиска Гамильтонова пути из A в D. Эйлеров путь – это путь по всем узлам и всем ребрам так, чтобы по каждому ребру пройти только один раз. У графа рис.1 - Эйлерова пути нет. Полный Граф – если все его вершины соединены друг с другом.

8 Теоремы

Теоремы

Теорема 1. Сумма степеней вершин графа – четное и равна удвоенному числу ребер графа. Доказательство: Каждое ребро соединяет две вершины (например A и B), и будет дважды учтено при определении степеней узлов, поскольку: p(А)=p(B) =1 и p(А)+ p(B) =2 .

Теорема 2. Число узлов с нечетной степенью любого графа – четное. Доказательство: Из Теоремы 1 мы знаем, что сумма четных и нечетных степеней вершин - четная: ? pч + ? pн = 2R , а сумма четных чисел ? pч - всегда четная. Значит и ? pн- четная.

Теорема 3. У Графа с количеством вершин нечетной степени больше 2-х Эйлерова пути нет . Доказательство: выполнено Эйлером в 1736 г.

9 Теорема 3: доказана при решении задачи о “Кёнигсбергских мостах”

Теорема 3: доказана при решении задачи о “Кёнигсбергских мостах”

10 Задача: “О кругосветном путешествии”

Задача: “О кругосветном путешествии”

Задача: “Теорема 4 красок” – 1852 год.

Необходимо посетить каждый город в пределах определенной территории и возвратиться в пункт отправления, причем так, чтобы путь был как можно короче В логистике известна как “Задача коммивояжера”

Всякую расположенную на сфере карту можно раскрасить 4 красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. ДОКАЗАНА в 1997-2005 гг. На КОМПЬЮТЕРЕ – 100 страниц текста! Для простых карт достаточно и 3 цветов!

Большое количество красок требуется для карты, если имеется одна область, окруженная нечетным числом других, которые соприкасаются друг с другом, образуя цикл. Теорема о 5 красках имеет простое доказательство.

11 Линейная транспортная задача и Теория Графов

Линейная транспортная задача и Теория Графов

12 Типовая Линейная транспортная задача речного флота и Теория Графов

Типовая Линейная транспортная задача речного флота и Теория Графов

Пример расчета стоимости перевозки 1000 тонн груза: Новосибирск-Томск

«Теория Графов»
http://900igr.net/prezentacija/biologija/teorija-grafov-118137.html
cсылка на страницу
Урок

Биология

136 тем
Слайды