ВАРИАНТ 25
No1
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой
дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько суще-
ствует различных путей из города А в город К?​

Ответ:

32

Пояснение:

дополнительно смотреть изображение

Отмечу,что в этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.

Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.

решение:

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков.

тогда для вершины Б=А=1

Г=А=1

В=А+Б+Г=1+1+1=3

Д=Б+В=1+3=4

Е=В+Г=3+1=4

Ж=В+Д=3+4=7

З=Е+В+Ж=4+3+7=14

И=Ж+Д=7+4=11

К=И+Ж+З=11+7+14=32

Очевидно, что мы могли посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитали индексы всех вершин.

Индекс вершины К и будет ответом задачи.