Задание 13
если в город R можно приехать только из городов X, Y, и Z, то число различных путей из города A в город R равно сумме числа различных путей проезда из A в X, из A в Y и из A в Z, то есть
где обозначает число путей из вершины A в некоторую вершину Q
Пример 1
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город В?
нас интересуют пути, проходящие через город В, поэтому на первом этапе отсекаем все ребра, которые позволяют на пути от А к М обойти город В; это рёбра БЕ, ГЗ и ДЗ;
получается, что вершину Е тоже можно убрать, потому что в неё не ведёт ни одна стрелка;
начальную вершину помечаем единицей (1 путь из А в А, никуда не ехать):
в вершины Б и Д можно ехать только из А, поэтому помечаем их тоже единицами; в вершину Г можно приехать из А (метка 1) и из Д, поэтому метка вершины Г – 2:
в вершину В можно приехать из Б (метка 1), А (метка 1) и Г (метка 2), так что метка вершины В равна 1 + 1 + 2 = 4:
в вершину З можно ехать только из В, поэтому её метка тоже равна 4; для вершины Ж складываем метки В и З (4 + 4 = 8), а для И – складываем метки Ж и З (8 + 4 = 12)
для вершин К и М получаем по 12 путей, а для М - 24
Ответ: 24.
Пример 2
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Какова длина самого длинного пути из города А в город М? Длиной пути считать количество до-рог, составляющих этот путь.
воспользуемся методом динамического программирования; индексом вершины назовем наибольшую длину пути из вершины А в эту вершину
поступим почти так же, как и в рассмотренных ранее (ниже) задачах на вычисление количества маршрутов, но при определении индекса очередной вершины X вместо суммы индексов предыдущих вершин (как это было в задачах на количество путей) будем брать наибольшее шее из значений индексов предыдущих вершин + 1
у вершины А индекс 0, у тех вершин (Б и Д), в которые можно приехать только из А, индекс 0 + 1 = 1:
далее, у вершины З – индекс 1 + 1 = 2, у вершины Г: 1+max(0, 1) = 2, а у вершины В: 1+max(0, 1, 2) = 3
у вершины Е индекс 1+max(1,3) = 4, у вершины Ж – 1+max(1,2,3,4) = 5
индекс вершины И: 1+max(2, 4, 5) = 6
остается также поставить индексы остальных вершин
Ответ: 9.
Пример 3
На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город Л?
для того, чтобы оставить только маршруты, проходящие через вершину В, нужно представить граф в таком виде, «собрав его в пучок» около вершины В:
проведём сечение графа через вершину В:
обратим внимание на такой факт: если мы перешли через линию сечения из левой части в правую по ребру ГЕ или через вершину Ж, мы уже никак не попадём в вершину В (нет рёбер с «обратным направлением», поэтому эти маршруты запрещены; для более сложных случаев, когда такие рёбра с «обратным направлением» есть, нужно перерисовать граф (или провести сечение иначе) так, чтобы все вершины, ИЗ которых можно попасть в В, оказались слева от линии сечения
В данном случае выбрасывается вершина Ж, все связанные с ней рёбра, и ребро ГЕ:
дальше используем стандартный метод (см. разбор следующей задачи)
покажем только окончательный результат:
Ответ: 16.
Пример 4
Города A, B, C и D связаны дорогами. Известно, что существуют дороги между городами A и С, C и B (две дороги), A и B, C и D (две дороги), B и D.
Сколькими различными способами можно проехать из города А в город D, не заезжая дважды в один город?
нарисуем граф, в котором множественные дороги из одного города в другой будем обозначать одной дугой и подписывать около неё количество дорог:
выпишем все маршруты, по которым можно ехать из A в D так, чтобы дважды не проезжать один и тот же город:
теперь рассмотрим маршрут A -> B -> D; на всех участках только одна дорога, поэтому есть только один такой маршрут
для маршрута A -> С -> D: на первом участке только одна дорога, на втором – две, общее число маршрутов равно произведению этих чисел:
аналогично находит количество различных путей по другим маршрутам
всего получается .
Ответ: 9.