Из города в город ведут 2 дороги, а из города в город ведут 3 дороги (по каждой дороге можно ездить в обоих направлениях). Сколько существует маршрутов, состоящих не более чем из…
Из города в город ведут 2 дороги, а из города в город ведут 3 дороги (по каждой дороге можно ездить в обоих направлениях). Сколько существует маршрутов, состоящих не более чем из 4 дорог, начинающихся в городе и заканчивающихся в городе ? (В маршруте и города, и дороги могут повторяться несколько раз.)
Предположим три города: A, B, C. Между A и B имеется 2 дороги (двустоRdонние, параллельные), между B и C — 3 дороги (также двусторонние). Нужно посчитать число маршрутов не длиннее 4 дорог, начинающихся в A и заканчивающихся в C (разрешено повторять города и дороги).
Ключевые моменты
- Из A в C путь обязательно проходит через B.
- Возможны маршруты длиной 2 и 4 дороги (длины 1 и 3 недостижимы, чтобы попасть из A в C).
- Длина 2 дороги: A -> B -> C
- выбор дороги A-B: 2 варианта
- выбор дороги B-C: 3 варианта Итого: 2 * 3 = 6 маршрутов.
- Длина 4 дороги: A -> B -> ? -> ? -> C Разбираем по тому, что может быть на второй шаге.
Вариант 2a: второй шаг идёт к A (A-B-A-B-C)
- шаг 1: A -> B: 2 варианта
- шаг 2: B -> A: 2 варианта
- шаг 3: A -> B: 2 варианта
- шаг 4: B -> C: 3 варианта Всего: 2 * 2 * 2 * 3 = 24 маршрута.
Вариант 2b: второй шаг идёт к C (A-B-C-B-C)
- шаг 1: A -> B: 2 варианта
- шаг 2: B -> C: 3 варианта
- шаг 3: C -> B: 3 варианта
- шаг 4: B -> C: 3 варианта Всего: 2 * 3 * 3 * 3 = 54 маршрута.
Итого маршрутов длины 4: 24 + 54 = 78.
Сумма для длины 2 и 4: 6 + 78 = 84.
Дополнительная проверка (быстрый матричный метод): если задать матрицу смежности A = [[0, 2, 0], [2, 0, 3], [0, 3, 0]], то количество путей длиной 2 от A к C равно (A^2){AC} = 6, а длиной 4 — (A^4){AC} = 78. Сумма даёт 84, как и выше.
Ответ: 84 маршрута. Если хотите, можно обобщить на m параллельных дорог A–B и n параллельных дорог B–C: итог будет mn + (m^3 n + m n^3) = mn(1 + m^2 + n^2). Для m=2, n=3 это 84.
