Уровень сложности — повышенный,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей, ведущих из города А в город М и проходящих через город Г?
Типовые задачи для тренировки
Ответ: 21
- Удалим ребра, которые проходят «мимо» вершины Г или до которых от пункта А можно дойти, минуя вершину Г:
- Вершина В удалена, т.к. возможны только следующие траектории движения через этот пункт (которые НЕ проходят через пункт Г):
- 1. А — Б — В — И — М
- 2. А — Б — В — Е — И — М
- 3. А — Б — В — Е — М
- 4. А — Б — В — Е — К — М
- Теперь посчитаем результаты по оставшимся вершинам:
М = И + Е + К
-----
И = Е
Е = Г + Ж
Г = Б + А + Д = 1 + 1 + 1 = 3
Ж = Г = 3
К = Е + Ж
Теперь возвращаемся, подставляя найденные значения: ↑
Е = Г + Ж = 3 + 3 = 6
Ж = Г = 3
И = Е = 6 (получили из последующих шагов)
К = Е + Ж = 6 + 3 = 9
М = И + Е + К = 6 + 6 + 9 = 21
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей, ведущих из города А в город М и не проходящих через город Г?
Ответ: 7
- Удалим ребра, которые проходят через вершину Г:
- Теперь посчитаем результаты по оставшимся вершинам:
М = И + Е + К
-----
И = В + Е
В = 1
Е = В + Ж
Ж = 1
Теперь возвращаемся, подставляя найденные значения: ↑
Е = В + Ж = 1 + 1 = 2
И = В + Е = 1 + 2 = 3
К = Е = 2
М = И + Е + К = 3 + 2 + 2 = 7
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город Ж?
Ответ: 20
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М?
Длиной пути считать количество дорог, составляющих этот путь.
Ответ: 9
