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.
Пытаются двигаться по дороге в направлении, противоположном стрелке.