Задачи на графы для подготовки к ЕГЭ.
учебно-методический материал по информатике и икт (11 класс) по теме
Задачи сформированы с использованием материала с сайта Константина Полякова (kpolyakov.narod.ru).
Скачать:
Вложение | Размер |
---|---|
sadazi_graf.doc | 300.5 КБ |
Предварительный просмотр:
Задачи на графы для подготовки к ЕГЭ. Использовался сайт Константина Полякова (kpolyakov.narod.ru).
Пример задания 1:
Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
Аэропорт вылета Аэропорт прилета Время вылета Время прилета
СОСНОВО КРАСНЫЙ 06:20 08:35
КРАСНЫЙ ОКТЯБРЬ 10:25 12:35
ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
БЕРЕГ СОСНОВО 12:15 14:25
СОСНОВО ОКТЯБРЬ 12:45 16:35
КРАСНЫЙ СОСНОВО 13:15 15:40
ОКТЯБРЬ СОСНОВО 13:40 17:25
ОКТЯБРЬ БЕРЕГ 15:30 17:15
СОСНОВО БЕРЕГ 17:35 19:30
БЕРЕГ ОКТЯБРЬ 19:40 21:55
Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.
1) 15:40 2) 16:35 3)17:15 4) 17:25
Решение:
- сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25:
ОКТЯБРЬ СОСНОВО 13:40 17:25
- посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой
- можно лететь, через КРАСНЫЙ, но, как следует из расписания,
ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
…
КРАСНЫЙ СОСНОВО 13:15 15:40
путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ
- можно лететь через БЕРЕГ,
БЕРЕГ СОСНОВО 12:15 14:25
…
ОКТЯБРЬ БЕРЕГ 15:30 17:15
но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится
- поскольку даже перелеты с одной пересадкой не стыкуются по времени, проверять варианты с двумя пересадками в данной задаче бессмысленно (хотя в других задачах они теоретически могут дать правильное решение)
- таким образом, правильный ответ – 4 (прямой рейс).
Возможные ловушки и проблемы:
|
Решение (вариант 2, граф):
- для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
- из аэропорта ОКТЯБРЬ есть три рейса:
ОКТЯБРЬ СОСНОВО 13:40 17:25
ОКТЯБРЬ КРАСНЫЙ 11:45 13:30
ОКТЯБРЬ БЕРЕГ 15:30 17:15
- построим граф, около каждого пункта запишем время прибытия
- проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс «БЕРЕГ-СОСНОВО», вылетающий в 12:15
- таким образом, правильный ответ – 4 (прямой рейс).
Еще пример задания 2:
Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.
1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа
Решение:
- нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):
- разделив числитель на знаменатель, получим время движения по каждой дороге
- ехать из А в B можно
- напрямую, это займет 4 часа, или …
- через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге
(из В в С), всего 1 + 2,5 = 3,5 часа
- таким образом, правильный ответ – 3.
Возможные ловушки и проблемы:
|
Еще пример задания:
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.
1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Решение (вариант 2, с рисованием схемы):
- для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:
1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
- теперь по схемам определяем кратчайшие маршруты для каждой таблицы:
1: или , стоимость 7
2: или , стоимость 7
3: , стоимость 6
4: , стоимость 8
- условие «не больше 6» выполняется только для таблицы 3
- таким образом, правильный ответ – 3.
Возможные ловушки и проблемы:
|
Еще пример задания:
Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A | B | C | D | E | F | |
A | 2 | 4 | ||||
B | 2 | 1 | 7 | |||
C | 4 | 1 | 3 | 4 | ||
D | 3 | 3 | ||||
E | 7 | 4 | 3 | 2 | ||
F | 2 |
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1) 9 2) 10 3) 11 4) 12
Решение (вариант 1, использование схемы):
- построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):
- для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
- например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):
- новые маршруты из С – в D и E (длины путей соответственно 3 и 4):
- новый маршрут из D – в E (длина пути 3):
- новый маршрут из E – в F (длина пути 2):
- нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
- попробуем перечислить возможные маршруты из А в Е:
А – В – Е длина 9
А – В – С – Е длина 7
А – В – C – D – Е длина 9
А –C – Е длина 8
А –C – B – Е длина 12
А –C – D – Е длина 10
- из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
- таким образом, правильный ответ – 1.
Еще пример задания[1]:
Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:
Аэропорт вылета Аэропорт прилета Время вылета Время прилета
ВОСТОРГ ГОРКА 16:15 18:30
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
ОЗЕРНЫЙ ВОСТОРГ 14:10 16:20
ГОРКА ОЗЕРНЫЙ 17:05 19:20
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
ЗАРЯ ОЗЕРНЫЙ 16:20 18:25
ВОСТОРГ ЗАРЯ 14:00 16:15
ЗАРЯ ГОРКА 16:05 18:15
ГОРКА ЗАРЯ 14:10 16:25
ОЗЕРНЫЙ ГОРКА 18:35 19:50
Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.
1) 16:15 2) 18:15 3)18:30 4) 19:50
Решение («обратный ход»):
- сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30:
ВОСТОРГ ГОРКА 16:15 18:30
- посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА:
ЗАРЯ ГОРКА 16:05 18:15
ОЗЕРНЫЙ ГОРКА 18:35 19:50
- это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05
- смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05:
ОЗЕРНЫЙ ЗАРЯ 13:40 15:50
- дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40
ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20
- таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении
- поэтому оптимальный маршрут
- и правильный ответ – 2.
Возможные ловушки и проблемы:
|
A | B | C | D | |
A | 1 | 2 | ||
B | 2 | 3 | ||
C | 1 | 2 | 5 | |
D | 2 | 3 | 5 |
- В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.
1) | 2) | 3) | 4) |
- В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».
1) | 2) | 3) | 4) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
- Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A | B | C | D | E | F | |
A | 2 | 4 | 3 | 7 | ||
B | 5 | 3 | ||||
C | 2 | 2 | ||||
D | 4 | |||||
E | 3 | 5 | ||||
F | 7 | 3 | 2 |
Определите длину кратчайшего пути между пунктами B и D (при условии, что передвигаться можно только по построенным дорогам).
1) 8 2) 9 3) 10 4) 11
[1] Крылов С.С., Ушаков Д.М. ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь. — М.: Экзамен, 2010.
По теме: методические разработки, презентации и конспекты
Задачи Теории графов
Наряду с живым словом педагога важны различные средства обучения в образовательном процессе. Универсальным средством обучения и воспитания, которое одинаково ценно для учащихся разных возрастных групп...
Некоторые задачи из пособия Гордина "Задачи С 4" для подготовки к ЕГЭ по математике
Презентация к 1 факультативному занятию с учащимися 10 класса, для подготовки к ЕГЭ по математике по сборнику Р. К. Гордина "Задачи С4" 2011 год разработка МИОО....
Логические задачи и графы
Занятие для математического кружка в 5-6 классах "Логические задачи и графы"....
Методическая разработка урока по информатике "Решение задач с применением графа при подготовке к ЕГЭ" - 2014 г.
Урок выстроен по ФГОС на районный конкурс методических разработок уроков «Современный урок в условиях реализации ФГОС» номинация "Урок с позиции УУД"...
Буклет "Еще один увлекательный способ решения задач ( метод графов)"
Данный буклет представляет собой справочный материал по применению графов для решения задач....
Элективный курс «Решение задач методом графов» (в рамках предпрофильной подготовки обучающихся 9 класса)
Предлагаемый курс носит интегративный характер, так как в нем представлена естественная реализация межпредметных связей математики с информатикой. Его цель – подготовить учащихся к осознанному в...
Метод графов. Решение задач методом графов. (материалы для занятий математического кружка в 5 классе)
В статье предложена подборка задач, одним из способов решения которых является метод графов. Этот метод позволяет легко и красиво решать задачи типа "Кто есть кто?", весьма интересен и вызыв...