Егэ информатика пути в графе - Помощь в подготовке к экзаменам и поступлению

На уроке рассматривается решение 13 задания ЕГЭ по информатике

Содержание:

Объяснение заданий 13 ЕГЭ по информатике
- Графы. Поиск количества путей
Решение заданий 13 ЕГЭ по информатике

13-е задание: «Информационные модели»

Уровень сложности

— повышенный,

Требуется использование специализированного программного обеспечения

— нет,

Максимальный балл

— 1,

Примерное время выполнения

— 3 минуты.

Проверяемые элементы содержания: Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы)

До ЕГЭ 2021 года — это было задание № 15 и № _ ЕГЭ

Типичные ошибки и рекомендации по их предотвращению:

«Игнорирование указаний в условии задания, что путь должен включать (или не включать) заданные промежуточные вершины»

ФГБНУ «Федеральный институт педагогических измерений»

Графы. Поиск количества путей

Если в город R из города A можно добраться только из городов X, Y и Z, то количество различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть:

N_R = N_X + N_Y + N_Z

где N_R — это количество путей из вершины A в вершину R
Число путей не бесконечно, исключением является только граф, в котором есть циклы – замкнутые пути.
Часто задачи с графами целесообразней решать с конца.

Решение заданий 13 ЕГЭ по информатике

Плейлист видеоразборов задания на YouTube:

Задание демонстрационного варианта 2022 года ФИПИ

13_1:

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

Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?

✍ Решение:

Удалим ребра, которые проходят «мимо» вершины Г или до которых от пункта А можно дойти, минуя вершину Г:

1_1

Вершина В удалена, т.к. возможны только следующие траектории движения через этот пункт (которые НЕ проходят через пункт Г):
1. А — Б — В — И — М
2. А — Б — В — Е — И — М
3. А — Б — В — Е — М
4. А — Б — В — Е — К — М
Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К 
-----
 И = Е 
   Е = Г + Ж 
    Г = Б + А + Д = 1 + 1 + 1 = 3 
    Ж = Г = 3
 К = Е + Ж

Теперь возвращаемся, подставляя найденные значения: ↑
   Е = Г + Ж = 3 + 3 = 6 
    Ж = Г = 3
 И = Е = 6 (получили из последующих шагов)
 К = Е + Ж = 6 + 3 = 9       
М = И + Е + К = 6 + 6 + 9 = 21

Результат: 21

Видео ЕГЭ по информатике (аналитическое решение):

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

13_2:

Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?

✍ Решение:

Удалим ребра, которые проходят через вершину Г:

Теперь посчитаем результаты по оставшимся вершинам:

М = И + Е + К
-----
И = В + Е
  В = 1
  Е = В + Ж
     Ж = 1

Теперь возвращаемся, подставляя найденные значения: ↑
  Е = В + Ж = 1 + 1 = 2
И = В + Е = 1 + 2 = 3 
К = Е = 2 
М = И + Е + К = 3 + 2 + 2 = 7

Результат: 7

Подробное решение данного 13 задания в видеоуроке:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

13 задание. Демоверсия ЕГЭ 2018 информатика:

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

Сколько существует различных путей из города А в город М, проходящих через город Ж?

✍ Решение:

Результат: 20

Подробное решение 13 задания демоверсии ЕГЭ 2018 года смотрите на видео:

📹 YouTube здесь
📹 Видеорешение на RuTube здесь

13_4:

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

✍ Решение:

Источник

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

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

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

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

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

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

Пример:

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

Решение:

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

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

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

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

Ответ: 11

Благодарим за то, что пользуйтесь нашими статьями.
Информация на странице «Задача №15. Графы. Поиск количества путей.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в ВУЗ или колледж нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из разделов нашего сайта.

Публикация обновлена:
08.03.2023

Источник

ЕГЭ информатика 13 задание разбор, теория, как решать.

Поиск путей в графе, (П) — 1 балл

Е13.26 ненулевой длины, которые начинаются и заканчиваются в городе Е

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

Е13.25 из пункта А в пункт С, проходящих ровно через один из пунктов Ж и М

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

Е13.24 из города А в город Л, проходящих через город 3

На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, 3, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л, проходящих через город 3? Ответ: Апробация ЕГЭ по информатике 19 февраля 2022 – задание …

Е13.23 Сколько существует различных путей из пункта А в пункт С, проходящих через пункты Е и М

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

Е13.22 Сколько существует различных путей из города Г в город Т, не проходящих через Л?

Сколько существует различных путей из города Г в город Т, не проходящих через Л? На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М, Н. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответ: Тренировочный вариант №1 от 13.09.2021 «ЕГЭ 100БАЛЛОВ»

Е13.21 Какова длина самого короткого пути из города А в город М

Какова длина самого короткого пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответ: Источник: «03.05.2021 ЕГЭ 100БАЛЛОВ, …

Е13.20 Какова длина самого длинного пути из города А в город М

Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Ответы: Источник: «19.04.2021 ЕГЭ 100БАЛЛОВ, …

Е13.19 Какова длина самого длинного пути из города А в город Л?

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

Е13.18 проходящих через пункт Г или через пункт Е, но не через оба этих пункта

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

Е13.17 различных путей пункта А в пункт Н, проходящих через пункт Е

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

Источник

Сегодня разберём одно из самых лёгких заданий из ЕГЭ по информатике — задание 13. Вы с похожим типом задач могли встретится на экзамене в 9 классе по информатике.

Приступим к практическим тренировкам решения 13 задания ЕГЭ по информатике 2022.

Задача (Стандартная)

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

Решение:

Нужно подсчитать количество путей от начальной точки А до конечной точки К.

Будем использовать специальную технику для решения 13 задания из ЕГЭ по информатике 2022

Техника:

Ставим 1 (единицу) возле начальной точки A. Далее, просматриваем ближайшие точки и анализируем, сколько входит стрелок в эти точки. В точку Б «перетекает» 1 из точки А. В точку Г тоже входит одна стрелка из точки А. Значит, тоже в эту точку «перетекает» 1 из А.

В точку В входят две стрелки. Значит, в точку В «втекает» сумма двух точек, из которых выходят эти стрелки! Получается 1 + 1 = 2.

И продолжаем в том же духе.

Число в конечной точке показывает правильный ответ!

Ответ: 17

Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)

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

Решение:

Отличие этой задачи от предыдущей заключается в том, что пути, которые будем засчитывать, обязательно должны проходить через пункт Ж. Чтобы выполнить это условие, зачеркнём стрелку из пункта Е в пункт И. Так же зачеркнём стрелку из пункта З в пункт И. По этим стрелкам ходить нельзя, т.к. если мы по ним пойдём, не будет пройден пункт Ж.

Основная техника же решения будет такой же, как и в прошлой задаче.

Ответ: 51

Продолжаем отработку 13 задания ЕГЭ по информатике 2022

Задача (Избегаемая вершина)

На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П

Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?

Решение:

Такая же задача, как и предыдущие две, только здесь, при построении путей, мы не должны проходить через точку E.

Зачеркнём те дороги, которые поведут наши пути через пункт E.

Далее, применим старый метод, который использовали ранее.

Получается ответ 27.

Ответ: 27

Рассмотрим задачу, которая была на реальном экзамене по информатике в этом году.

Задача (ЕГЭ по информатике, 2020, Москва)

На рисунке — схема дорог, связывающих города А, Б, В, Г, Е, Ж, К, Л, М. По каждой дороге можно двигаться в одном направлении, указанном стрелкой. Какая наибольшая длина пути из А в М ?

Решение:

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

Возле начальной точки ставим число 0.

Смотрим сколько входит в узел стрелок. Выбираем стрелку, которая идёт из узла с наибольшим числом. При переходе по стрелочке добавляем 1.

Число, которое получится возле конечной точки и будет ответом. В этой задачке стрелок получилось 7, это и будет ответ.

Ответ: 7

Источник

1. Вспоминай формулы по каждой теме

2. Решай новые задачи каждый день

3. Вдумчиво разбирай решения

Простейшие задачи на графы

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

Заметим, что количество путей в город Е является суммой путей в города Ж, Г и Д. Количество путей в город Ж — сумма путей в города Г и Б. Таким образом получаем:

Г = Б + В

Д = Г + В

Ж = Б + Г

Е = Ж + Г + Д

Заметим, что в пункты Б и В можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.

Ответ: 8

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

Заметим, что количество путей в город Ж является суммой путей в города Д, Г и Е. Количество путей в город Г — сумма путей в город В, Б и Е. Таким образом получаем:

Г = Б + В + Е

Д = В + Г

Ж = Д + Г + Е

Заметим, что в пункты Б, В и Е можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.

Ответ: 8

Между населёнными пунктами А, В, С, D, Е построены дороги, протяжённость которых (в километрах) приведена в таблице:

Определите длину кратчайшего пути между пунктами А и E. Передвигаться можно только по дорогам, протяжённость которых указана в таблице.

Найдём все варианты маршрутов из A в E и выберем самый короткий.

Из пункта A можно попасть в пункты B, D.

Из пункта B можно попасть в пункты C, D.

Из пункта C можно попасть в пункты D, E.

A—B—C—E: длина маршрута 7 км.

A—D—B—C—E: длина маршрута 9 км.

A—D—C—E: длина маршрута 6 км.

Самый короткий путь: A—D—C—E. Длина маршрута 6 км.

Ответ: 6

Геральт спешит выручить Цири из плена Кагыра. В таблице указана протяжённость дорог между пунктами, через которые он может пройти. Укажите длину самого короткого участка кратчайшего пути от Геральта до Цири (от точки И до точки М). Передвигаться можно только по дорогам, указанным в таблице:

Найдём все варианты маршрутов из И в М и выберем самый короткий.

Из пункта И можно попасть в пункты А, Б, Г, М.

Из пункта Г можно попасть в пункты И, М.

Из пункта В можно попасть в пункты А, Б.

Из пункта Б можно попасть в пункты В, И, М.

И—А—В—Б—М: длина маршрута 7 км.

И—Б—М: длина маршрута 4 км.

И—Г—М: длина маршрута 7 км.

И—М: длина маршрута 8 км.

Самый короткий путь: И—Б—М. Длина маршрута 4 км. Самый короткий участок этого пути равен 1 км.

Ответ: 1

На схеме нарисованы дороги между четырьмя населёнными пунктами A, B, C, D и указаны протяжённости данных дорог.

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

Заметим, что наиболее удалены друг от друга пункты A и D. Найдём все варианты маршрутов из A в D и выберем самый короткий.

A—B—D: длина маршрута 13 км.

A—C—D: длина маршрута 15 км.

A—B—C—D: длина маршрута 23 км.

A—C—B—D: длина маршрута 17 км.

Заметим, что кратчайшее расстояние между пунктами A и D равняется 13.

Ответ: 13

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