9
Решение: Количество путей в графе
ОГЭ · Информатика · Задание 9 · Графы и пути
ПовышеннаяФИПИ4178A6Короткий ответ≈ 3 минутыРазбор в 6 шаговОтвет сверен с ключом
Условие
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?
Дальше ответЕсли ещё решаете — начните с подсказок: они ведут к ответу, но не выдают его.
К подсказкамРешение по шагам
6 шагов1
Из города A выходят дороги в города B, E, F и G.
$$N_A = 1$$2
Через B существует один путь к C, а затем к D: A–B–C–D.
3
Через E существуют два пути к D: A–E–D и A–E–C–D.
4
Через F существуют три пути к D: A–F–D, A–F–H–D и A–F–G–H–D.
5
Через G существует один путь к D: A–G–H–D.
Складываем количества путей по четырём направлениям из A.
$$1 + 2 + 3 + 1 = 7$$Ответ
7
7
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывают пути, проходящие через промежуточные города G и H.
Считают путь A–E–C–D отдельно от пути A–E–D.
Пытаются двигаться по дороге в направлении, противоположном стрелке.