Что нужно знать:
Решение:
Nx = Ny + … + Nz
где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например,
NЛ = NИ + NЖ + NК
NВ = NА + NБ + NГ = 1 + 1 + 1 = 3
NЕ = NГ = 1
NД = NБ + NВ = 1 + 3 = 4
NЖ = NВ + NЕ = 3 + 1 = 4
NК = NЕ = 1
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