Question

Помоги срочно...!!!! на рисунке схема дорог связывающих города а,б,в,г,д,е,ж,и,к,л. сколько-нибудь существует путей из города А в город Л?

Answer 1

Ответ: 25 путей существует из города А в город Л

Каждой вершине, начиная с начальной (A), поставим в соответствие индекс, равный количеству путей, которыми можно попасть в эту вершину. Для вершины A (начало пути) индекс всегда равен 1 (в начало пути можно попасть единственным образом – никуда не двигаясь). Теперь сформулируем правило: индекс вершины равен сумме индексов его предков. Исходя из этого индекс Б равен 1 (предок у Б один – вершина A). У вершины В предками являются А, Б и Г, значит индекс вершины В равен 1+1+1=3. И т.д.