9
Шешімі: Количество путей в графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИB137FDҚысқа жауап≈ 4 минутТалдау 4 қадамЖауап сверен с ключом
Условие
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешімін қадамдап көрсету
4 қадам1
Из города А непосредственно можно попасть в города Б, В и Г. Число путей до них: в Б — 1, в Г — 1, в В — 2 (напрямую из А и через Г).
$$N_{Б}=1,\quad N_{Г}=1,\quad N_{В}=1+N_{Г}=2$$2
В город Д можно попасть только из Б, поэтому число путей до Д равно 1.
$$N_{Д}=N_{Б}=1$$3
В город Е можно попасть из Г напрямую или из В, поэтому число путей до Е равно 3.
$$N_{Е}=N_{Г}+N_{В}=1+2=3$$В город К ведут дороги из Б, Д, В и Е. Складываем количество путей до этих вершин.
$$N_{К}=N_{Б}+N_{Д}+N_{В}+N_{Е}=1+1+2+3=7$$Жауап
7
7
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывать пути, проходящие через промежуточные города.
Считать дорогу между городами путём, не проверяя все возможные продолжения.
Повторно считать один и тот же путь.