Что нужно знать:
- если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть
где
обозначает число путей из вершины A в некоторую вершину R
- число путей конечно, если в графе нет циклов – замкнутых путей
Пример 1
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
Решение:
- будем обозначать через NX количество различных путей из города А в город X
2. для города А есть только один маршрут – никуда не двигаться, поэтому N(A) = 1
3. для любого города X количество маршрутов NX можно вычислить как
N(x) = N(y) + … + N(z)
где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например,
N(Л) = N(И) + N(Ж) + N(К)
4. около каждого города будем записывать количество маршрутов из А в этот город
5. начнем считать количество путей с начала маршрута – с города А:
6. теперь находим те вершины, в которые можно попасть напрямую из уже рассмотренных вершин (пока – только из А), это Б и Г, для них тоже количество путей равно 1:
7. теперь можно определить количество путей для В и Е; в В можно приехать только из А, Б и Г, а в Е – только из Г:
N(В) = N(А) + N(Б) + N(Г) = 1 + 1 + 1 = 3
N(Е) = N(Г) = 1
8. теперь можно определить количество путей для Д, Ж и К; в Д можно приехать только из Б и В, в Ж – из В и Е, а в Е – только из Г:
N(Д) = N(Б) + N(В) = 1 + 3 = 4
N(Ж) = N(В) + N(Е) = 3 + 1 = 4
N(К) = N(Е) = 1
9. теперь можно определить количество путей для И, куда можно приехать только из Д (N(И) = N(Д)) и, наконец, для Л:
N(Л) = N(Д) + N(И) + N(Ж) + N(К) = 13
Ответ: 13
Пример 2
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
Решение:
1) Начнем считать количество путей с начала маршрута – с города А:
A = 1
2) В города Б и Д идут дороги только из А. Поэтому Б = 1, Д = 1
3) В город В идут дороги из Б и А. Складываем, получаем В=А+Б=1+1=2
4) В город Г идут дороги из А, В и Д. Складываем, получаем
Г = А + В + Д = 1 + 2 + 1 = 4
5) В город Е идет дорога из Б: Е = Б = 1
6) В город Ж идут дороги из Г и Д:
Ж = Г + Д = 4 + 1 = 5
7) В город К идут четыре дороги из Е, В, Г, Ж:
К = Е + В + Г + Ж = 1 + 2 + 4 + 5 = 12
Ответ: 12