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