Приветствуем всех на канале "Информатика для всех"!
Рассмотрим решение задачи номер 9 из ОГЭ по информатике 2026 года.
Условие задачи:
На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G, H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город H?
Решение:
Рассмотрим схему дорог, связывающих различные города.
Для начала посчитаем, сколько есть маршрутов между самыми ближними городами, начиная с города А.
Из А в В - единственный маршрут.
Из А в С и из А в D - также всего по одному маршруту.
Затем рассмотрим город Е.
Из А в Е ведет уже два маршрута: через город В и через город С, то есть АВЕ и АСЕ.
Изобразим это графически:
Продвинемся дальше по схеме в город F.
Можем попасть в F через С, через D и через Е. Но при этом через С и D проходят по одной дороге, а через Е - две дороги (через АВЕ и АСЕ).
Общее количество дорог из А в F - это 4 (как 1+1+2).
В город G ведут маршруты через Е и F, причем 2 маршрута через С и 4 маршрута через F. Значит в сумме мы можем использовать 6 маршрутов для пути из А в G.
Остается рассмотреть заключительный город Н.
В него можно попасть через город F (а в F ведут 4 маршрута) и через город G (в него ведут 6 маршрутов).
Итого получается, что из А в Н мы можем попасть 4+6=10 маршрутами.
Ответ: 10
И немного теории графов
В методических материалах ФИПИ указано, что задача 9 раскрывает такие понятия как:
Граф. Вершина, ребро, путь. Ориентированные и неориентированные графы. Длина (вес) ребра. Весовая матрица графа. Длина пути между вершинами графа. Поиск оптимального пути в графе. Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе. Вычисление количества путей в направленном ациклическом графе.
Граф — это математическая структура, состоящая из множества вершин (или узлов) и множества рёбер (или дуг), которые соединяют пары вершин. Графы широко используются для моделирования различных систем и отношений в реальном мире, таких как социальные сети, транспортные системы, компьютерные сети и многое другое.
Основные понятия графа
- Вершина (узел): Основной элемент графа, который может представлять объект или точку.
- Ребро (дуга): Связь между двумя вершинами. В неориентированном графе ребро не имеет направления, в то время как в ориентированном графе (или диграфе) ребро имеет направление от одной вершины к другой.
- Степень вершины: Количество рёбер, инцидентных данной вершине. В ориентированном графе различают входящую и исходящую степень.
- Путь: Последовательность рёбер, соединяющих последовательные вершины.
- Цикл: Путь, который начинается и заканчивается в одной и той же вершине.
Ориентированный граф
Ориентированный граф (или диграф) — это граф, в котором каждое ребро имеет направление. Это означает, что если есть ребро от вершины A к вершине B, то оно обозначается как A→B и не подразумевает наличие ребра B→A.
Ориентированные графы являются мощными инструментами для моделирования и решения различных задач в математике и информатике. Понимание основных понятий и алгоритмов работы с графами позволяет эффективно решать задачи оптимизации, поиска и анализа данных.
Неориентированный граф — граф, в котором ребра не имеют направления. То есть, связь между вершинами двунаправленная: если есть ребро между вершинами A и B, то можно пройти из A в B и из B в A.
Длина (вес) ребра
Длина или вес ребра — числовое значение, которое ассоциируется с этим ребром. Обычно оно обозначает стоимость, время, расстояние или другой параметр, связанный с переходом по этому ребру.
Весовая матрица графа
Весовая матрица — квадратная матрица, где элемент в позиции (i, j) показывает вес ребра, соединяющего вершины i и j. В неориентированном графе матрица симметрична, а в ориентированном — может быть асимметричной. Если ребра между вершинами нет, в матрице обычно ставится специальное значение (например, бесконечность или 0, в зависимости от контекста).
Длина пути между вершинами графа
Длина пути — сумма весов всех ребер, входящих в этот путь. В случае неориентированного графа — сумма весов ребер по пути, в ориентированном — сумма весов по направленным ребрам, если путь существует.
Поиск оптимального пути в графе
Оптимальный путь — путь между двумя вершинами с минимальной (или максимальной, в зависимости от задачи) длиной или весом. Например, в задаче поиска кратчайшего пути ищется путь с минимальной суммарной длиной.
Начальная вершина (источник) и конечная вершина (сток) в ориентированном графе
- Источник — вершина, из которой начинаем путь.
- Сток — вершина, в которую стремимся попасть.
В ориентированном графе путь ищется с учетом направления дуг: от источника к стоку.
Вычисление количества путей в направленном ациклическом графе
Направленный ациклический граф (DAG) — граф без циклов.
Количество путей между двумя вершинами — число различных путей, соединяющих их. Например, чтобы найти число путей из вершины A в вершину B, можно:
- Обойти вершины в топологическом порядке.
- Для каждой вершины подсчитать количество путей из источника.
- Использовать рекуррентное соотношение: количество путей к вершине равно сумме количества путей к вершинам, из которых есть ребро в текущую вершину.
И еще решение задач ОГЭ:
Подборка решений всех задач ОГЭ по информатике (пополняется)