Шешімі: Количество путей в графе
На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К и Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Шешім по шагам
3 қадамГраф ориентированный и не содержит циклов, поэтому вершины можно рассматривать слева направо, начиная с города А.
Для каждой вершины подсчитываем число путей из А: если в вершину ведут несколько стрелок, складываем числа путей до вершин, из которых они выходят.
После последовательного подсчёта для всех вершин складываем количества путей, приходящих в город Л. Общее число различных путей равно 24.
$$N_{Л}=24$$Где здесь ошибаются
Учитывают дороги без учёта направления стрелок.
Пропускают один из нұсқа пути через промежуточные вершины.
Считают количество дорог вместо количества различных путей.