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