Приложение теории графов Киселёв Андрей МОУ СОШ 1, 11а класс г. Кулебаки. - презентация

1 Приложение теории графов Киселёв Андрей МОУ СОШ 1, 11 а класс г. Кулебаки

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

3 Карта железных дорог

4 План улиц города

5 План водопроводной сети Если на ребрах (линиях) графа отметить стрелками направление движения воды, получится направленный или ориентированный граф (орграф).

6 Максимальное значение потока в сети улиц

7 Шахматный матч

8

9 Одностороннее движение

10 Граф на кодирование

11 Орграф автомата

12 Задача 1 Во время поездки к знакомым в г. Москву из Кулебак, мы проехали 1 ч на автобусе, 5 часов на поезде, 30 минут на легковом автомобиле (на такси). Скорость автобуса была 40 км/ч, скорость поезда вдвое больше скорости автобуса, а скорость легкового автомобиля на 10 км/ч больше, чем скорость поезда. Какой путь мы проделали от г. Кулебаки до г. Москва?

13 S А – υ П – υ Т – S П – S Т – S О = S А + S П + S Т. Ответ: 475 км

14 Задача 2 Слово «КУЛЕБАКИ» разделено на отдельные буквы, из них произвольным образом отбирается и выкладывается по порядку четыре буквы. Какова вероятность получения слова «БАКУ»?.

15 Задача 3 Над поверхностью воды выступает часть льдины. Объем надводной части равен 120 м. Каков объем всей льдины? 3 Решая систему, получаем ответ на вопрос задачи:

16 Задача 4 За короткий срок изготовить модель самолета МиГ-3. Перечень работ 0-1Выбор модели для изготовления 1-2Перевод деталей 2-3Вырезание деталей 3-4Изготовление рёбер жесткости 3-5Придание деталям нужной формы 4-5Изготовление каркаса (скелета) модели 5-9Склеивание обшивки самолета 2-7Изготовление пушек 7-9Приклеивание пушек 2-8Изготовление стоек шасси 8-9Крепеж шасси к самолету 2-6Изготовление кабины и фонаря самолета 6-9Приклеивание кабины и фонаря самолета 9-10Шпаклевка самолета 9-12Окончательная покраска самолета 11-12Нанесение опознавательных знаков

17 На ребрах графа указаны числа – продолжительность в часах соответствующей работы. Помеченные вершины от 0 до 12 – затраченные работы. Ответ: Наименьшее время изготовления модели 197,8 часа.

18 Задача 4 За короткий срок изготовить модель самолета МиГ-3. Перечень работ 0-1Выбор модели для изготовления 1-2Перевод деталей 2-3Вырезание деталей 3-4Изготовление рёбер жесткости 3-5Придание деталям нужной формы 4-5Изготовление каркаса (скелета) модели 5-9Склеивание обшивки самолета 2-7Изготовление пушек 7-9Приклеивание пушек 2-8Изготовление стоек шасси 8-9Крепеж шасси к самолету 2-6Изготовление кабины и фонаря самолета 6-9Приклеивание кабины и фонаря самолета 9-10Шпаклевка самолета 9-12Окончательная покраска самолета 11-12Нанесение опознавательных знаков

19

20 Вывод: Использование графов Ускоряет решение практических задач Упрощает расчеты Повышает производительность научной, инженерной и конструкторской мысли