Приложение теории графов Киселёв Андрей МОУ СОШ 1, 11 а класс г. Кулебаки
Приложение теории графов Графом называется всякая система линий, (прямолинейных отрезков) соединяющих между собой точки некоторой заданной системы точек. Эти точки называются вершинами графа, а отрезки – рёбрами графа.
Карта железных дорог
План улиц города
План водопроводной сети Если на ребрах (линиях) графа отметить стрелками направление движения воды, получится направленный или ориентированный граф (орграф).
Максимальное значение потока в сети улиц
Шахматный матч
Одностороннее движение
Граф на кодирование
Орграф автомата
Задача 1 Во время поездки к знакомым в г. Москву из Кулебак, мы проехали 1 ч на автобусе, 5 часов на поезде, 30 минут на легковом автомобиле (на такси). Скорость автобуса была 40 км/ч, скорость поезда вдвое больше скорости автобуса, а скорость легкового автомобиля на 10 км/ч больше, чем скорость поезда. Какой путь мы проделали от г. Кулебаки до г. Москва?
S А – υ П – υ Т – S П – S Т – S О = S А + S П + S Т. Ответ: 475 км
Задача 2 Слово «КУЛЕБАКИ» разделено на отдельные буквы, из них произвольным образом отбирается и выкладывается по порядку четыре буквы. Какова вероятность получения слова «БАКУ»?.
Задача 3 Над поверхностью воды выступает часть льдины. Объем надводной части равен 120 м. Каков объем всей льдины? 3 Решая систему, получаем ответ на вопрос задачи:
Задача 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Нанесение опознавательных знаков
На ребрах графа указаны числа – продолжительность в часах соответствующей работы. Помеченные вершины от 0 до 12 – затраченные работы. Ответ: Наименьшее время изготовления модели 197,8 часа.
Задача 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Нанесение опознавательных знаков
Вывод: Использование графов Ускоряет решение практических задач Упрощает расчеты Повышает производительность научной, инженерной и конструкторской мысли