Поиск количества путей в ориентированном графе (страница 3)

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт J ведут 40 различных путей.

Ответ: 40

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт D ведут 22 различных пути.

Ответ: 22

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт L ведут 104 различных пути.

Ответ: 104

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт K ведут 37 различных путей.

Ответ: 37

Решать будем динамикой.

Красным отмечено, сколько путей идёт в конкретную вершину по конкретной стрелке. Заметим, что если в город идёт более, чем одна дорога, значит количество путей в этот город будет равно сумме количеств путей, ведущих в города, из которых эти дороги начинаются. В этом и есть принцип динамического решения. Получается, если сложить все красные числа, нарисованные около конкретного города, как раз можно получить количество различных путей, ведущих в этот город.

Нужно понимать, что в город A можно попасть одним путём: собственно, никуда не уходить из города A.

Итого получается, что в пункт Q ведут 20 различных путей.

Ответ: 20

Посчитаем сколькими путями можно придти в каждый дом:

Ответ: 10

Введём обозначение: \(X = a\), где \(X\) — пункт (А, Б, ...), а \(a\) — количество путей, ведущих в этот пункт.
Из пункта А в пункт А можно попасть только одним способом. Следовательно, A \(=\) 1.
В пункт Г можно попасть только из пункта А. Следовательно, Г \(=\) А \(=\) 1.
В пункт В можно попасть из пунктов А и Г. Следовательно, В \(=\) А \(+\) Г \(=\) 2.
В пункт Б можно попасть из пунктов А и В. Следовательно, Б \(=\) А \(+\) В \(=\) 3.
В пункт Д можно попасть только из пункта Б. Следовательно, Д \(=\) Б \(=\) 3.
В пункт Ж можно попасть из пунктов В и Г. Следовательно, Ж \(=\) В \(+\) Г \(=\) 3.
В пункт Е можно попасть из пунктов Д, Б, В, Ж. Следовательно, Е \(=\) Д \(+\) Б \(+\) В \(+\) Ж \(=\) 11.
В пункт И можно попасть только из пункта Е. Следовательно, И \(=\) Е \(=\) 11.
В пункт К можно попасть только из пункта Е. Следовательно, К \(=\) Е \(=\) 11.
В пункт М можно попасть из пунктов И, Е, К. Следовательно, М \(=\) И \(+\) Е \(+\) К \(=\) 33.

Ответ: 33