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