На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?
13, вроде бы
1) АБДИК
2) АБДЖК
3) АБВДИК
4) АБВДЖК
5) АБВЖК
6) АВЖК
7) АВДЖК
8) АВДИК
9) АГЕК
10) АГВЖК
11) АГВДЖК
12) АГВДИК
13) АГЕЖК
Будем решать задачу от обратного: будем последовательно у каждой вершины указывать, сколько из этой вершины существует путей в М. При этом мы будем пользоваться следующей логикой:
Допустим, у нас есть вершины А, Б, В и Г. И нам надо посчитать количество путей из А в Г. При этом из А есть дороги только в Б и В. При этом из Б в Г существует 5 маршрутов, а из В в Г — 7. Тогда количество маршрутов из А в Г равно количеству маршрутов из Б в Г плюс количество маршрутов из В в Г: 5+7=12.
Воспользуемся этим правилом:
Из К в М, очевидно, ведёт одна дорога. Равно как и из Л в М. Значит, из И в М будут вести две дороги: 1+1=2.
Из Ж есть путь только в И, поэтому кол-во маршрутов из Ж в М также равно 2. Следовательно, количество маршрутов из З в М равно 4, так как из З можно попасть в Ж (2 маршрута) или в И (2 маршрута): 2+2=4. Аналогично из Е: количество маршрутов равно также 4.
Теперь посчитаем количество маршрутов из точки В (Б и Г мы не можем посчитать из-за незнания маршуртов в точке В, а точку Д — из-за незнания точки Г).
Из точки В можно попасть в Е (4 маршрута), или в Ж (2 маршрута) или в З (4 маршрута), то есть 4+2+4=10 всего.
Значит, из Б будет 4 (точка Е) + 10 (точка В) = 14 маршрутов.
Из точки Г — 4 (точка З) + 10 (точка В) = 14 маршрутов.
Значит, из точки Д будет 14 (точка Г) + 4 (точка З) = 18 маршрутов.
Значит, из точки А будет 14 (Б) + 10 (В) + 14 (Г) + 18 (Д) = 56 маршрутов.
Ответ: 56 маршрутов.