ок. Графы. Поиск количества путей
 Скачать 2.33 Mb.
|
Ещё пример задания:Р-04. (Досрочный ЕГЭ-2020) На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Какова длина самого длинного пути из города А в город М? Длиной пути считать количество дорог, составляющих этот путь.  Решение: воспользуемся методом динамического программирования; индексом вершины назовем наибольшую длину пути из вершины А в эту вершину поступим почти так же, как и в рассмотренных ранее (ниже) задачах на вычисление количества маршрутов, но при определении индекса очередной вершины 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. Ещё пример задания:Р-03. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город В?  Решение: для того, чтобы оставить только маршруты, проходящие через вершину В, нужно представить граф в таком виде, «собрав его в пучок» около вершины В:  проведём сечение графа через вершину В:  обратим внимание на такой факт: если мы перешли через линию сечения из левой части в правую по ребру ГЕ или через вершину Ж, мы уже никак не попадём в вершину В (нет рёбер с «обратным направлением», поэтому эти маршруты запрещены; для более сложных случаев, когда такие рёбра с «обратным направлением» есть, нужно перерисовать граф (или провести сечение иначе) так, чтобы все вершины, ИЗ которых можно попасть в В, оказались слева от линии сечения в данном случае выбрасывается вершина Ж, все связанные с ней рёбра, и ребро ГЕ:  дальше используем стандартный метод (см. разбор следующей задачи) покажем только окончательный результат:  Ответ: 16. Ещё пример задания:Р-02. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?   Решение: будем обозначать через NX количество различных путей из города А в город X для города А есть только один маршрут – никуда не двигаться, поэтому NA = 1 для любого города X количество маршрутов NX можно вычислить как Nx = Ny + … + Nz где сумма взята по всем вершинам, из которых есть прямой путь в вершину X; например, NЛ = NИ + NЖ + NК около каждого города будем записывать количество маршрутов из А в этот город начнем считать количество путей с начала маршрута – с города А:  теперь находим те вершины, в которые можно попасть напрямую из уже рассмотренных вершин (пока – только из А), это Б и Г, для них тоже количество путей равно 1:  теперь можно определить количество путей для В и Е; в В можно приехать только из А, Б и Г, а в Е – только из Г: NВ = NА + NБ + NГ = 1 + 1 + 1 = 3 NЕ = NГ = 1  теперь можно определить количество путей для Д, Ж и К; в Д можно приехать только из Б и В, в Ж – из В и Е, а в Е – только из Г: NД = NБ + NВ = 1 + 3 = 4 NЖ = NВ + NЕ = 3 + 1 = 4 NК = NЕ = 1  теперь можно определить количество путей для И, куда можно приехать только из Д (NИ = NД) и, наконец, для Л: NЛ = NД + NИ + NЖ + NК = 13  Ответ: 13. |