Задачи на определениевремени по расписанию
Путешественник пришел в 08:00 на автостанцию населенного пункта КАЛИНИНО и обнаружил следующее расписание автобусов. Определите самое ранее время, когда путешественник сможет оказаться в пункте РАКИТИНО согласно этому расписанию.
1) 12:25 2) 12:30
3) 12:35 4) 12:40
Решение:
Рассмотрим все возможные варианты маршрутов:
|
| 1) КАЛИНИНО → БУКОВОЕ →9:10 → 10:15 БУКОВОЕ → РАКИТИНО →11:40 → 12:40
| ||
| 2) КАЛИНИНО → РАКИТИНО →10:15 → 12:35
| ||
|
| 3) КАЛИНИНО → КАМЫШИ →10:20 → 11:15 КАМЫШИ → РАКИТИНО →11:25 → 12:30 Выбираем наименьшее время 12:30 Ответ: 2 | ||
Задача на нахождение стоимости проезда по таблицамперевозок.
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
Решение:1) для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:
Рис. 25
2) по схемам определяем кратчайшие маршруты для каждой таблицы:
|
|
|
1: A 
C 
BилиА С 
Е В, стоимость 7
2: A C Bили A 
E C B, стоимость 7
3: А Е В, стоимость 6
4: A D C E B, стоимость 8
3) условие «не больше 6» выполняется только для таблицы 3
8) таким образом, правильный ответ – 3.
Задача на нахождение минимального времени по данным расстояния и скорости.
Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. Длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.
1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа
Решение:
| 
|
| Рис. 26 | Рис. 27 |
1) нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе) (рис. 26)
2) разделив числитель на знаменатель, получим время движения по каждой дороге (рис. 27)
3) ехать из А в B можно напрямую, это займет 4 часа, иличерез пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге (из В в С), всего 1 + 2,5 = 3,5 часа
4) таким образом, правильный ответ – 3.
Выводы:
|
|
|
Знание теории графов дает возможность приобрести навыки сведения реальных ситуаций к графовым моделям, научиться строить простейшие алгоритмы. Какую бы область человеческой жизни мы ни затрагивали, в этой области обязательно находилась проблема или задача, решаемая с помощью графов. Метод графов прост и удобен, поэтому так распространен.
Графы – это замечательные математические объекты, с помощью, которых можно решать математические, логические задачи. Теория графов играет очень важную роль в жизни человека.
Заключение
В результате работы над проектом мы узнали, что Леонард Эйлер был основоположником теории графов, решил задачи с применением теории графов. Мы сделали вывод, что теория графов находит применение в различных областях современной математики и информатики. Не приходится сомневаться в полезности ознакомления нас, учащихся, с основными понятиями теории графов. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность. Многие доказательства также упрощаются, приобретают убедительность, если воспользоваться графами. В особенности это относится к таким областям математики, как математическая логика, комбинаторика.
|
|
|
Таким образом, изучение этой темы имеет большое общеобразовательное, общекультурное и общематематическое значение. В повседневной жизни все большее применение находят графические иллюстрации, геометрические представления и другие приемы и методы наглядности. С этой целью изучение элементов теории графов полезно во внеклассной работе, так как в программу по математике эта тема не включена.
Приложение 1
Использование графов в повседневной жизни:
· Строительство железных дорог, мостов, дорог.
· Построение географических карт.
· Блок – схемы алгоритмов. (рис. 33)
· Схемы движения городского транспорта. (рис. 34)
Рис. 33 Рис. 34
Самым впечатляющим примером графа в современном мире выступает Интернет. Его узлы - это адреса страничеки файлов, находящихся в сети, а ребра -гиперссылки, связывающие их вместе. Компьютеры, связанные вместе и образующиеВсемирную паутину, также можно рассматривать как граф.
Другая сложная система, появившаяся гораздо раньше Интернета - глобальная общемировая телефонная сеть - также является графом. Если мы будем рассматривать все телефонные аппараты (а вернее, номера, соответствующиеим) как узлы, а звонки, совершаемые с одного телефонного аппарата на другой, - как ребра, то получим сложную сеть, истинные размеры которой, наверное, не каждый сможет себе представить.
|
|
|
И глобальной телефонной сетью, и Интернетом очень сложно управлять,предсказать все возможные звонки и связи невозможно.Если вы делаете звонок из Москвы в Нью-Йорк, существует множествоспособов соединить вас с тем абонентом, звонят. Телефонные станции должны выбирать кратчайший (с точки зрения графа)путь, соединяющий эти две точки. То же самое и в Интернете: чтобы браузер на вашем компьютере мог загрузить страничку, физически находящуюся в Южно-Африканской Республике, данные должны пройти через некоторое количество серверов, то есть маршрут в Сети. Он будет автоматически выбираться серверами такимобразом, чтобы его длина была минимальной (опять-таки, с точки зренияграфа), а данные по возможности проходили через незагруженные сегментыСети. Из-за того, что нагрузка в разных участках Сети постоянно и случайным образом меняется, даже если вы загрузите с одного и того сайта страничку двараза подряд с интервалом в 1 секунду, она может прийти к вам двумя разными путями. Кроме того, что по Сети гуляют не странички в готовом виде, а пакеты с данными, и даже одна страничка может состоять из нескольких пакетов, значит, фрагменты одной страницы могут приходить в Интернете с одного компьютера на другойразными путями. Задача доставки пакетов данных из одного узла Сети (хоста)в другой называется задачей маршрутизации, и она отнюдь не является простой.
Предположим, путешественнику по автодорогам надо попасть из Петербурга в Берлин. Можно придумать несколько маршрутов, пролегающих по территории разных государств и различных по своей длине. Они будут удовлетворять разным условиям: проехать из одной точки в другую максимально быстро, побывать в какой-нибудь стране, или, наоборот, объехать ее, так как нам не удалось получить визу; останавливаться каждую ночь в каком-нибудь городском мотеле и т. д.
Задача нахождения оптимального пути между двумя географическими точками, удовлетворяющего определенным условиям, известна в теории графов как задача нахождения кратчайшего пути. В качестве узлов графа выступают перекрестки и развязки дорог, они совпадают с городами и другими населенными пунктами. Ребра - это дороги, соединяющие узлы.
Еще один интересный пример, связанный с графами, это задачасоставления календаря. Предположим, есть некая организация, в которой работают 500 человек.
Каждый из них встречается сосвоими коллегами в рамках различных мероприятий, каждый день, или раз в неделю, или раз в месяц. Составить общее расписание рабочихвстреч нам может помочь теория графов. Самый простой вариант - разбить рабочее время каждогосотрудника на определенные интервалы по 15 минут, и установитьмежду ними для каждого сотрудника ориентированные последовательныесвязи, в результате получатся вертикальные цепочки из узлов – интерваловрабочего времени. Если два сотрудника в определенное время встречаются,нужно установить горизонтальные связи между соответствующимиинтервалами времени - узлами. Сегодня эту утомительную работу выполняют компьютеры, однако совсем недавно расписания икалендари составлялись вручную.
Дата добавления: 2018-06-27; просмотров: 444; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!