Шешімі: Количество путей в графе
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Шешім по шагам
4 қадамПосчитаем пути, начинающиеся переходом из А в В. Из В можно попасть в К напрямую, через Д или через И: всего 3 пути.
$$1+1+1=3$$Посчитаем пути, начинающиеся переходом из А в Г. Из Г можно попасть в К напрямую, через И или через Е: всего 3 пути.
$$1+1+1=3$$Посчитаем пути, начинающиеся переходом из А в Б. Из Б следует перейти в Г, после чего возможны те же 3 продолжения: напрямую в К, через И или через Е.
$$3$$Складываем количество путей по трём направлениям из А.
$$3+3+3=9$$Где здесь ошибаются
Не учитывать путь через город Б и затем через Г.
Посчитать только пути, проходящие через промежуточные города, и пропустить прямые дороги в К.
Двигаться по дороге против направления стрелки.