Задание №13 из демоверсии ЕГЭ по информатике 2022 года заключается в определении количества путей в ориентированном графе, проходящих через заданную вершину. Невнимательность может привести к потере балла.
Условие задачи
На рисунке представлена схема дорог, связывающих города A, B, C, D, E, F, G, H, I, K, L, M. Движение по каждой дороге возможно только в одном направлении, указанном стрелкой. Необходимо определить количество различных путей из города A в город M, проходящих через город B.
Метод решения: Динамическое программирование
Наиболее эффективный способ решения – динамическое программирование. Этот метод сводит сложную задачу к решению более простых задач того же типа. В данном случае, мы последовательно определяем количество путей для каждой вершины графа до достижения города M.
Учёт условия прохождения через город B
Пути должны проходить через город B. Это означает, что некоторые дороги исключаются из рассмотрения. Например, дороги из D в любую другую вершину и из G в E не проходят через B и исключаются. Аналогично, дороги, исходящие из B (B → G и B → J), также не учитываются. После удаления лишних дорог можно приступать к расчёту.
Расчёт количества путей
Начнём с города A. В городе A один путь.
- Город B: Из A в B ведёт один путь.
- Город G: В G ведут два пути: из A и из B (1 + 1 = 2).
- Город J: В J ведёт один путь из B.
- Город C: В C ведёт один путь из B.
- Город F: В F ведут пути из B и C (1 + 1 = 2).
- Город H: В H ведёт один путь из F.
- Город I: В I ведут пути из F и H (2 + 1 = 3).
- Город K: В K ведёт один путь из I.
- Город L: В L ведут пути из I и K (3 + 1 = 4).
- Город M: В M ведут пути из K и L (1 + 4 = 5).
Таким образом, количество путей из города A в город M, проходящих через город B, равно 5.
Задача решается методом динамического программирования, пошагово вычисляя количество путей для каждой вершины. Важно учитывать условие прохождения через определённый город. Правильный учёт условия и последовательный подсчёт путей позволяют получить верный ответ.