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

задан 21 Май '12 18:36

изменен 21 Май '12 22:11

DocentI's gravatar image


9.8k937

@Хабиб Муртазалиев, Если вы получили исчерпывающий ответ, отметьте его как принятый.

(28 Май '12 21:14) Angry Bird
10|600 символов нужно символов осталось
6

Например, с помощью матриц. Задаем матрицу смежности из 0 и 1 (назовем ее S). Там, где есть вектор из i-ой вершины в j-ую, ставим в клеточке нс номерами (i, j) 1, где нет - 0.

Возведем эту матрицу в квадрат. Значения в клетках дадут число путей из i в j длиной 2 ребра. Умножим еще на матрицу S, получим в клеточках число путей длиной 3 и т.д.
Видимо, на некотором шаге матрица станет нулевой. Сумма всех ненулевых матриц $%S + S^2+ ... + S^n$% даст число путей между каждой парой вершин.

В Вашей задаче имеем $%S^6 = 0$%, а путей из А в К - 13. Из них 4 длиной 3, 7 длиной 4 и 2 длиной 5.
Вот вычисления в Excel
alt text

ссылка

отвечен 21 Май '12 22:03

изменен 21 Май '12 22:27

10|600 символов нужно символов осталось
0

Уже есть красивый ответ с картинками. У меня ответ простой и без картинок.

Пусть есть некоторая f(n), которая возвращает количество путей попасть сюда из А. Очевидно, что f(n)= f(a1) + .. +f(ak), где ai -- какая-то вершина, из которой можно попасть в n за один переход. По этой формуле можно разложить n в какую-то одну вершину(долго и мучительно, если без оптимизации, но оптимизируется легко). При этом разложения будет состоять из конечного числа элементов тогда и только тогда, когда нет цикла. Т.е. если на каком-то из возможных путей буудет цикл, то общее количество путей бесконечно. Всё.

ссылка

отвечен 6 Дек '12 21:45

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×271

задан
21 Май '12 18:36

показан
1703 раза

обновлен
6 Дек '12 21:45

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru