|
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном
стрелкой. Сколько существует различных путей из города А в город К? задан 21 Май '12 18:36 
Хабиб Муртаз... |
|
Например, с помощью матриц. Задаем матрицу смежности из 0 и 1 (назовем ее S). Там, где есть вектор из i-ой вершины в j-ую, ставим в клеточке нс номерами (i, j) 1, где нет - 0. Возведем эту матрицу в квадрат. Значения в клетках дадут число путей из i в j длиной 2 ребра. Умножим еще на матрицу S, получим в клеточках число путей длиной 3 и т.д. В Вашей задаче имеем $%S^6 = 0$%, а путей из А в К - 13. Из них 4 длиной 3, 7 длиной 4 и 2 длиной 5. отвечен 21 Май '12 22:03 
DocentI |
|
Уже есть красивый ответ с картинками. У меня ответ простой и без картинок. Пусть есть некоторая f(n), которая возвращает количество путей попасть сюда из А. Очевидно, что f(n)= f(a1) + .. +f(ak), где ai -- какая-то вершина, из которой можно попасть в n за один переход. По этой формуле можно разложить n в какую-то одну вершину(долго и мучительно, если без оптимизации, но оптимизируется легко). При этом разложения будет состоять из конечного числа элементов тогда и только тогда, когда нет цикла. Т.е. если на каком-то из возможных путей буудет цикл, то общее количество путей бесконечно. Всё. отвечен 6 Дек '12 21:45 
Aleksey Lob... |
@Хабиб Муртазалиев, Если вы получили исчерпывающий ответ, отметьте его как принятый.