Задание №9 ОГЭ по информатике 2023 года проверяет умение анализировать информацию, представленную в виде схем (графов). Это задание повышенного уровня сложности, на его выполнение отводится около 4 минут. Аналогичное, но более сложное задание (№13) присутствует в ЕГЭ.
Метод решения: динамическое программирование
Для нахождения количества путей в графе эффективно использовать метод динамического программирования. Суть метода заключается в последовательном получении частичных результатов для каждой вершины графа. В итоге определяется количество путей в финальную вершину.
Примеры заданий
Пример 1: Простой граф
Схема дорог, связывающих города A, B, C, D, E, F, G, представлена на рисунке (рисунок отсутствует в исходном тексте, необходимо добавить). Движение по дорогам возможно только в одном направлении (указано стрелками). Необходимо определить количество различных путей из города A в город G. Прямой подсчет путей неэффективен. Метод динамического программирования позволяет избежать ошибок:
- Город A: 1 путь (не ехать никуда).
- Город B: 1 путь (из A).
- Город E: 2 пути (из A и B).
- Город D: 1 путь (из A).
- Город F: 4 пути (из D и E: 1 + 3 = 4).
- Город G: 6 путей (из E и F: 2 + 4 = 6).
Количество различных путей из A в G равно 6.
Пример 2: Сложный граф
Граф содержит больше вершин (рисунок отсутствует). Задача — найти количество различных путей из города A в город M. Решение аналогично примеру 1: последовательно подсчитываем количество путей для каждой вершины, суммируя количество путей, ведущих в неё из предыдущих вершин. Ответ: 16.
Пример 3: Граф с условием прохождения через определенную вершину
Задача: найти количество путей из A в L, проходящих через город G. Перед решением удаляем дороги, не проходящие через G, затем применяем метод динамического программирования. Решение: 6.
Пример 4: Граф с условием непрохождения через определенную вершину
Задача: найти количество путей из A в J, не проходящих через город D. Удаляем город D и все связанные с ним дороги, применяем метод динамического программирования. Решение: 10.
Пример 5: Граф с двумя условиями
Задача: найти количество путей из A в H, проходящих через G и не проходящих через K. Сначала удаляем город K и связанные дороги, затем применяем метод динамического программирования. Решение: 7.
Пример 6: Сложный граф с двумя условиями
Задача: найти количество путей из A в M, проходящих через G и не проходящих через K. Сначала удаляем K и связанные дороги, затем применяем метод динамического программирования. Решение: 30.
Метод динамического программирования — эффективный инструмент для подсчета количества путей в графе. Важно последовательно подсчитывать количество путей для каждой вершины, учитывая условия задачи. На экзамене не следует перерисовывать граф во избежание ошибок.