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