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