Вариант 25 no1 на рисунке — схема дорог, связывающих города а, б, в, г, д, е, ж, з, и, к. по каждой дороге можно двигаться только в одном направлении, указанном стрелкой. сколько суще- ствует различных путей из города а в город к?
Отмечу,что в этой задаче мы имеем дело с ориентированным графом (графом, у которого ребра имеют направление). Т.е. ребра имеют вид стрелок. Две вершины, соединенные напрямую стрелкой, называются смежными. Вершина, из которой выходит стрелка, называется предком, а вершина, в которую входит стрелка – потомком.
Несложно понять, что количество путей, которыми можно попасть в некоторую вершину, равно сумме количеств путей предков этой вершины.
Каждой вершине, начиная с начальной (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
Очевидно, что мы могли посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитали индексы всех вершин.
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
Очевидно, что мы могли посчитать индекс только тех вершин, индексы предков которых уже посчитаны. Двигаясь последовательно, мы рассчитали индексы всех вершин.
Индекс вершины К и будет ответом задачи.