Количество путей

В ЕГЭ и ГИА введена совсем новая задача, в которой требуется определить количество различных путей из одной вершины в другую.

Рассмотрим задачу B9 из демонстрационного варианта ЕГЭ

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

Если говорить на языке теории графов, в этой задаче используется ориентированный граф (или кратко орграф) — по каждому ребру можно двигаться только в одном направлении, указанном стрелкой (аналогия из жизни — дорога с односторонним движением). Отметим, что если предположить, что движение возможно в обоих направлениях, количество путей будет бесконечно (можно сколько угодно ездить туда и обратно между соседними городами).

Тогда возникает вопрос — а для любого ли ориентированного графа количество путей из одной вершины в другую конечно? Простой пример показывает, что это не так:

Действительно, здесь есть циклы АБГ и БГВ, в которых можно “крутиться” бесконечно долго. Таким образом, для разрешимости задачи необходимо,

чтобы в графе не было циклов.

Теперь займемся решением. Число вершин в таких задачах достаточно велико (здесь — 9), поэтому матрица смежности размером 9 х 9 при ручном решении нам вряд ли поможет.

Способ 1. Перебор всех возможных путей “методом наблюдения”.

Попробуем найти все возможные пути, глядя на схему. Сначала рассмотрим пути, начинающиеся с отрезка AБ. Чтобы не запутаться, будем начинать с верхней части графа, постепенно “спускаясь” ниже и ниже: