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