ЕГЭ, вопрос 13: П. Расчет числа путей между точками графа
Проверяемые элементы содержания по спецификации (2021): Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы).
Кодификатор 1.3.1/1.2.1. Уровень сложности П, 1 балл.
Время выполнения — 3 минуты.
Спецификация не отражает сути задания и не позволяет создать вопросы из других тем, похожие по сложности.
В заданиях приведено больше вершин, чем в ОГЭ. В имеющихся на странице заданиях ответ колеблется в диапазоне 8–120.
Общая сложность заключается в отсутствии периодичности в разветвлении графа. Вспомним, что если граф делится из всех вершин на равное количество ветвей (n), то количество листьев (читай путей) составит nq, где q — число уровней ветвления.
В экзаменационном же задании обычно приводится более сложная структура: ветвлений неравное количество, да и направления бывают реализованы довольно сложно.
Задания
Дополнительные задания приведены здесь.
- Демо 2021 ().
- Демо 2020 (15). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
- Демо 2019 (15). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Л?
- Демо 2018 (15). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
- D2018 (15). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
- R2018 (15). На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город К, проходящих через город Г и НЕ проходящих через город З?
- Демо 2017 (15). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город В?
- Демо 2016 (15). На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М?
- Демо 2015 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
- Демо 2014 (B9). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Л?
- Демо 2013 (B9). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. Сколько существует различных путей из города А в город Л?
- Демо 2012 (B9). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
- Демо K-2012 (B4). На рисунке — схема дорог, связывающих населённые пункты А, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении,
указанном стрелкой. Сколько существует различных путей из A в H?
- Демо 2011. Не вводилось.
- Демо 2010. Не вводилось.
- Демо 2009. Не вводилось.
- (т2-2012/1).
- (т2-2012/2).
- (д2-2013/1).
- с114 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- с124 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- с113 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- с123 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- с112 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- с122 (15). На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш115 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш125 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш114 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш124 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш113 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш123 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш112 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш122 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Т?
- ш111 (15).
- ш121 (15).
- Демо 2010. Не вводилось.