ЕГЭ, вопрос 15: П. Расчет числа путей между точками графа

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

Кодификатор 1.3.1/1.2.1. Уровень сложности П, 1 балл.

Время выполнения – 3 минуты.

Спецификация не отражает сути задания и не позволяет создать вопросы из других тем, похожие по сложности.

В заданиях приведено больше вершин, чем в ОГЭ. В имеющихся на странице заданиях ответ колеблется в диапазоне 8–120.

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

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

Задания

Дополнительные задания приведены здесь.

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

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

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

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

  5. R2018 (15). На рисунке представлена схема дорог. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К, проходящих через город Г и НЕ проходящих через город З?

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

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

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

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

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

  12. Демо K-2012 (B4). На рисунке — схема дорог, связывающих населённые пункты А, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из A в H?

  13. Демо 2011. Не вводилось.
  14. Демо 2010. Не вводилось.
  15. Демо 2009. Не вводилось.
  16. (т2-2012/1).
  17. (т2-2012/2).
  18. (д2-2013/1).

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

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

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

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

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

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

  25. ш115 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  26. ш125 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  27. ш114 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  28. ш124 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  29. ш113 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  30. ш123 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  31. ш112 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  32. ш122 (15). На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
    Сколько существует различных путей из города А в город Т?

  33. ш111 (15).
  34. ш121 (15).

Copyright © 1993–2020 Мацкявичюс Д.А. Все права защищены.
Никакая часть сайта не может быть воспроизведена никаким способом без письменного разрешения правообладателя и явной ссылки на данный ресурс.