Задачи на графы егэ информатика

Пройти тестирование по 10 заданиям
Пройти тестирование по всем заданиям
Вернуться к каталогу заданий

Версия для печати и копирования в MS Word

Пройти тестирование по этим заданиям

Использование теории графов для решения заданий ЕГЭ

1. Между населенными пунктами A,B,C,D,E,Fпостроены дороги, протяженность которых приведена в таблице(отсутствие числа означает, что прямой дороги нет). Определить длину кратчайшего пути между пунктами 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,B,C,D,E,F. Элементы данной матрицы показывают, какие населенные пункты связаны дорогами и какова их длина. Для более наглядного представления изобразим данные таблицы в виде графа. Для этого в произвольном порядке изображаем вершины, затем соединяем их ребрами и указываем вес каждого ребра. Нам надо указать длину кратчайшего пути из пункта А в пункт F.  Нарисуем этот путь с конца.

Сначала изобразим конечный пункт F. В этот пункт можно попасть только из пункта Е. Соединяем пункты Е и F  дугой и указываем вес этой дуги. Он равен двум, то есть расстоянию между пунктами  Е и F. Соответственно по графу можно увидеть, что в пункт Е можно попасть  из пунктов B, C и D. В пункт В можно попасть из А. В пункт С – из В и А. В  пункт D – из С. В пункт В попадаем из А. В пункт С – из В и А. И в пункт В из А.

Данную схему можно рассматривать как ориентированный взвешенный граф, который наглядно показывает, что есть 5 путей из пункта А в пункт F. Подсчитываем длину каждого пути 
1 путь: 2+7+2=11;
2 путь: 2+1+4+2=9;
3 путь: 4+4+2=10;
4 путь2+1+3+3+2=11;
5 путь: 4+3+3+2=12. 
Так как нам надо определить длину кратчайшего пути, то выбираем второй путь, длина которого равна 9. Данный ответ находится под цифрой 1. Поэтому в ответе надо поставить крестик в клеточке, соответствующей первому ответу.

2. У исполнителя Утроитель две команды, которым присвоены номера
1. Прибавь 1;
2. Умножь на 3.
Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд.
Решение:
Для решения данного задания используем метод от обратного, то есть будем преобразовывать число 22 в 1. Соответственно команды исполнителя заменим командами антагонистами, то есть команду «Прибавь 1» заменим командой «Вычти 1», а «Умножь на 3» заменим командой «Раздели на 3». Ход выполнения команд можно изобразить в виде  дерева, каждая вершина которого имеет две ветки, соответствующие командам 1 и 2. Корнем этого дерева является число 22. Это дерево будет иметь 5 ярусов, так как программа должна содержать не более 5 команд. Но здесь нужно учесть один момент. Если число  делится на 3, то вершина будет иметь 2 потомка, а если нет, то одного (то есть делить на 3 мы не можем, а можем только вычитать 1). Получаем следующее дерево.

  

 Инвертируем теперь команды и преобразуем число 1 в 22.
    1+1*3+1*3+1=22.
   Учитывая номера команд, записываем программу решения данной задачи в виде  последовательности соответствующих команд. Ответ: 12121

 
Решение: (1 способ)
Условие данного задания представлено в виде ориентированного графа, вершинами которого являются названия городов, а дороги, соединяющие эти города, являются дугами графа. Для того, чтобы решить данную задачу, построим еще один ориентированный граф, но с  учетом того, по каким дорогам можно будет попасть в пункт Л.

 По графу легко подсчитать количество дорог, ведущих из города А в город Л.
 

3.У Исполнителя Кузнечик 2 команды:
1. Прибавь 3;
2. Вычти 2.
Сколько различных чисел можно получить из числа 1 с помощью программы, которая содержит ровно 5 команд. 
Решение:
Оформим решение данной задачи в виде дерева, вершинами которого будут являться числа, соответствующие промежуточным значениям. Данное дерево будет иметь корень, равный 1 и 5 ярусов, так как у нас должно быть ровно 5 команд.

 

 4. У исполнителя Устроитель две команды, которым присвоены номера:
1. Прибавь 1;
2. Умножь на 3.
Программа для Устроителя – это последовательность команд. 
Сколько есть программ, которые преобразуют 1 в число 29?

  При решении данной задачи следует учитывать, что если число больше 9, то умножать на 3 мы не можем, так как получится число, большее 29, следовательно, вершины с числами большими 9 будут иметь только одну ветвь, соответствующую команде +1.

  
 

   

5.Даны три кучи камней, содержащих соответственно 2, 3, 4 камня. За один ход разрешается или удвоить количество камней в какой-нибудь куче, или добавить по 2 камня в каждую из всех трех куч. Выигрывает тот, после чьего хода в какой-нибудь куче становится больше или равно 15 камней или во всех трех кучах суммарно становится больше либо равно 25 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок? 
Решение:    В разумной партии каждый игрок должен стараться следовать общему правилу – всегда оставлять противнику проигрышную позицию. В ходе решения задач можно заметить, что в одной партии в Камешки только один из игроков может следовать этому правилу – тот, кто первым может занять выигрышную позицию (имеет выигрышную стратегию). Если он будет ей следовать, а, значит, делать только разумные ходы и оставлять противнику только проигрышные позиции, то выиграет при любой игре противника. Если начальная позиция выигрышная, то выигрышную стратегию имеет Первый, если проигрышная – Второй.  
Изобразим решение данной задачи в виде графа.

Ответ:  при правильной стратегии игры выигрывает первый игрок. При этом первый его ход должен быть 2, 3, 4                 4, 5, 6.

Литература: 
ФИПИ (открытый банк данных)
Материалы демонстрационных вариантов ЕГЭ по информатике  2016, 2015 года
Материалы диагностической работы 2015 года.

Автор — Лада Борисовна Есакова.

Подсчет путей в ориентированном графе. ЗАДАЧА № 15.

В этой задаче требуется подсчитать количество путей, ведущих из одной вершины графа в другую. Обычно задачу решают преобразованием графа в дерево. Однако, при сложной структуре графа такое решение становится очень трудоемким. Велика вероятность ошибки.

Рассмотрим простой и эффективный способ решения.

В этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

Пример:

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A).

У вершины Д предками являются А и Б, значит индекс вершины Д равен 1+1=2.

Очевидно, что мы можем посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Например, мы не можем посчитать индекс Г, пока не посчитан индекс В. Двигаясь последовательно, мы рассчитаем индексы всех вершин.

Индекс вершины Ж и будет ответом задачи.

Ответ: 11

Задачи на графы для подготовки к ЕГЭ. Использовался сайт Константина Полякова (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 (прямой рейс).

Решение (вариант 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.

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

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда  из А в 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.

	A	B	C	D
A			1	2
B			2	3
C	1	2		5
D	2	3	5

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

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.