Шешімі: Количество путей в графе
На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?
Шешім по шагам
5 қадамВ город A ведёт один начальный путь: считаем количество путей из A в каждую вершину.
$$N_A=1$$В город D можно попасть непосредственно из A или по маршруту $A\to C\to D$.
$$N_D=N_A+N_C=1+1=2$$В город F ведут дороги из E и D. До E существуют 2 пути: напрямую из A и через B. Поэтому:
$$N_F=N_E+N_D=2+2=4$$В город G можно попасть только из D, поэтому количество путей в G равно 2.
$$N_G=N_D=2$$В город H ведут дороги из F и G. Складываем количество путей по этим двум направлениям.
$$N_H=N_F+N_G=4+2=6$$Где здесь ошибаются
Не учитывать путь $A\to C\to D$.
Считать дороги как неориентированные и разрешать движение против стрелок.
Не складывать пути, приходящие в H из F и G.