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.