9
Шешімі: Пути в ориентированном графе
ОГЭ · Информатика · Тапсырма 9 · Графы и пути
КүрделіФИПИB9A72DҚысқа жауап≈ 4 минутТалдау 5 қадамЖауап сверен с ключом
Условие
На рисунке — схема дорог, связывающих города A, B, C, D, E, G, H, F. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?
Дальше ответЕгер әлі шешіп жатсаңыз – кеңестерден бастаңыз: олар жауапқа жетелейді, бірақ оны ашпайды.
К подсказкамШешім по шагам
5 қадам1
Начинаем с вершины A: количество путей в A равно 1. Тогда в B и G попадает по одному пути, а в E напрямую из A попадает один путь.
$$N_A=1,\quad N_B=1,\quad N_G=1$$2
В вершину E ведут дороги из A, B и G, поэтому количество путей в E равно трём.
$$N_E=N_A+N_B+N_G=1+1+1=3$$3
В вершину C ведут дороги из B и E, а в H — из G и E.
$$N_C=N_B+N_E=1+3=4,\quad N_H=N_G+N_E=1+3=4$$4
В вершину F ведут дороги из E и H, поэтому количество путей в F равно семи.
$$N_F=N_E+N_H=3+4=7$$В вершину D ведут дороги из C, E и F. Складываем количество путей из A в эти вершины.
$$N_D=N_C+N_E+N_F=4+3+7=14$$Жауап
14
14
так ответ выглядит в бланкеГде здесь ошибаются
Не учитывают путь A → E → D.
Считают дороги, а не различные пути.
При сложении забывают один из входов в вершину D.