Задачи на графы для подготовки к ЕГЭ.
учебно-методический материал по информатике и икт (11 класс) по теме

Семикова Юлия Ивановна
Опубликовано 13.05.2014 - 8:15 - Семикова Юлия Ивановна

Задачи сформированы с использованием материала с сайта Константина Полякова (kpolyakov.narod.ru).

Скачать:

ВложениеРазмер
Microsoft Office document icon sadazi_graf.doc300.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

Решение:

  1. сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25:

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

  1. посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой
  2. можно лететь, через КРАСНЫЙ, но, как следует из расписания,

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        …

        КРАСНЫЙ         СОСНОВО         13:15         15:40

путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ

  1. можно лететь через БЕРЕГ,

        БЕРЕГ         СОСНОВО         12:15         14:25

        …

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится

  1. поскольку даже перелеты с одной пересадкой не стыкуются по времени, проверять варианты с двумя пересадками в данной задаче бессмысленно (хотя в других задачах они теоретически могут дать правильное решение)
  2. таким образом, правильный ответ – 4 (прямой рейс).

Возможные ловушки и проблемы:

  • можно не заметить, что путешественник не успеет на пересадку в КРАСНОМ (неверный ответ 15:40)
  • можно перепутать аэропорты вылета и прилета (неверный ответ 16:35)

Решение (вариант 2, граф):

  1. для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ
  2. из аэропорта ОКТЯБРЬ есть три рейса:

        ОКТЯБРЬ         СОСНОВО         13:40         17:25

        ОКТЯБРЬ         КРАСНЫЙ         11:45         13:30

        ОКТЯБРЬ         БЕРЕГ         15:30         17:15

  1. построим граф, около каждого пункта запишем время прибытия

  1. проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс  «БЕРЕГ-СОСНОВО», вылетающий в 12:15
  2. таким образом, правильный ответ – 4 (прямой рейс).

Еще пример задания 2:

Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.

1) 1 час        2) 1,5 часа         3)3,5 часа         4) 4 часа

Решение:

  1. нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):

  1. разделив числитель на знаменатель, получим время движения по каждой дороге

  1. ехать из А в B можно
  • напрямую, это займет 4 часа, или …
  • через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге
    (из В в С), всего 1 + 2,5 =     3,5 часа
  1. таким образом, правильный ответ – 3.

Возможные ловушки и проблемы:

  • можно не заметить, что требуется найти минимальное время поездки именно в В, а не в С (неверный ответ 1 час)
  • можно ограничиться рассмотрением только прямого пути из А в В и таким образом получить неверный ответ 4 часа
  • можно неправильно нарисовать схему

Еще пример задания:

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда  из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими  соседними станциями.

1)

2)

3)

4)

A

B

C

D

Е

A

3

1

B

4

2

C

3

4

2

D

1

Е

2

2

A

B

C

D

Е

A

3

1

1

B

4

C

3

4

2

D

1

Е

1

2

A

B

C

D

Е

A

3

1

4

B

4

2

C

3

4

2

D

1

Е

4

2

2

A

B

C

D

Е

A

1

B

4

1

C

4

4

2

D

1

4

Е

1

2

Решение (вариант 2, с рисованием схемы):

  1. для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:

1)

2)

3)

4)

A

B

C

D

Е

A

3

1

B

4

2

C

3

4

2

D

1

Е

2

2

A

B

C

D

Е

A

3

1

1

B

4

C

3

4

2

D

1

Е

1

2

A

B

C

D

Е

A

3

1

4

B

4

2

C

3

4

2

D

1

Е

4

2

2

A

B

C

D

Е

A

1

B

4

1

C

4

4

2

D

1

4

Е

1

2

              

  1. теперь по схемам определяем кратчайшие маршруты для каждой таблицы:

1:   или , стоимость 7

2:   или , стоимость 7

3:  , стоимость 6

4:  , стоимость 8

  1. условие «не больше 6» выполняется только для таблицы 3
  2. таким образом, правильный ответ – 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, использование схемы):

  1. построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

  1. для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее
  2. например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):

  1. новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

  1. новый маршрут из D – в E (длина пути 3):

  1. новый маршрут из E – в F (длина пути 2):

  1. нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E
  2. попробуем перечислить возможные маршруты из А в Е:

А – В – Е        длина 9

А – В – С – Е         длина 7

А – В – C – D – Е         длина 9

А –C – Е         длина 8

А –C – B – Е         длина 12

А –C – D – Е         длина 10

  1. из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9
  2. таким образом, правильный ответ – 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

Решение («обратный ход»):

  1. сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30:

        ВОСТОРГ         ГОРКА         16:15         18:30

  1. посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА:

        ЗАРЯ        ГОРКА        16:05         18:15

        ОЗЕРНЫЙ         ГОРКА         18:35         19:50

  1. это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05
  2. смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05:

        ОЗЕРНЫЙ         ЗАРЯ         13:40         15:50

  1. дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40

        ВОСТОРГ        ОЗЕРНЫЙ         11:15         13:20

  1. таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении
  2. поэтому оптимальный маршрут

  1. и правильный ответ – 2.

Возможные ловушки и проблемы:

  • «напрашивается» ошибочный ответ 18:30 (прямой рейс)
  • при решении задачи «прямым ходом», с начального пункта, легко пропустить вариант с двумя пересадками

A

B

C

D

A

1

2

B

2

3

C

1

2

5

D

2

3

5

  1. В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.        

                        

1)

2)

3)

4)

  1. В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».

1)

2)

3)

4)

A

B

C

D

A

2

2

B

2

4

3

C

4

4

D

2

3

4

A

B

C

D

A

2

1

1

B

2

4

C

1

4

1

D

1

1

A

B

C

D

A

1

3

6

B

1

2

4

C

3

2

D

6

4

A

B

C

D

A

3

2

1

B

3

2

C

2

2

4

D

1

4

  1. Между населёнными пунктами 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 классе)

В статье предложена подборка задач, одним из способов решения которых является метод графов. Этот метод позволяет легко и красиво решать задачи типа "Кто есть кто?", весьма интересен и вызыв...