С разных сторон на холм поднимаются три тропинки и сходятся на вершине. Перечислите множество маршрутов, по которым можно подняться на холм и спуститься с него. Решите ту же задачу, если вверх и вниз надо идти по разным тропинкам.
Обозначим тропинки цифрами — 1, 2 и 3. Построим граф, где корнем будет нахождение в любой точке под горой. Подняться можно по любой из трех тропинок:
Поднявшись по любой из тропинок, мы можем спуститься используя опять же любую из них. Покажем на графе, добавив из каждой точки еще по 3 пути:
Все пути от вершин первого уровня к вершинам последнего уровня будут составлять множество маршрутов, по которым можно подняться на холм и спуститься с него:
1—1, 1—2, 1—3, 2—1, 2—2, 2—3, 3—1, 3—2, 3—3.
Если вверх и вниз нужно идти разными путями, то от каждой точки первоначального графа мы строим по 2 пути:
Таким образом, множество маршрутов, по которым можно подняться на холм и спуститься с него другим путем:
1—2, 1—3, 2—1, 2—3, 3—1, 3—2.
Пожауйста, оцените решение
