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