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