Решить задачу надо не посчитав количество, а по формуле. Теорема графов, если не ошибаюсь. Объясните пожалуйста, Как найти.

Решить задачу надо не посчитав количество, а по формуле. Теорема графов, если не ошибаюсь. Объясните пожалуйста, Как найти.
Гость
Ответ(ы) на вопрос:
Гость
Не думаю, что есть какие-то формулы. В любом случае придется считать. Идея решения большинства таких задача следующая: Как можно попасть в город H? Можно прийти в него из городов D, F, G или E. Соответственно, количество путей из A в H - это количество путей из A в D + из A в F + из A в G + из A в E. Аналогично для остальных городов. Будем считать, что существует один путь из A в A. В город B можно попасть только напрямую из A - 1 путь. В C тоже можно попасть только напрямую из A - 1 путь. В E можно попасть только из C. В C существует 1 путь -> в E тоже 1 путь. В F можно попасть из A,B,C,E -> количество путей в F = 1 + 1 + 1 + 1 = 4 В D можно попасть из B или F - 1 + 4 = 5 В G можно попасть только из E - 1 Наконец, количество путей в H = 5 + 4 + 1 + 1 = 11 Ответ: 11
Не нашли ответ?
Ответить на вопрос
Похожие вопросы