📚 Теория: Задание 4 ОГЭ — Анализ простейшей модели объектов
🗺️ Что такое граф?
Граф — это математическая модель, состоящая из
множества вершин (точек) и множества
рёбер (линий, соединяющих вершины).
В заданиях ОГЭ графы используются для моделирования дорожных сетей,
где:
Вершины — населённые пункты (A, B, C, D, E...)
Рёбра — дороги между пунктами с указанием
протяжённости
Пример графа
📊 Матрица расстояний
Информация о графе может быть представлена в виде
матрицы расстояний (таблицы), где:
Строки и столбцы соответствуют вершинам графа
На пересечении строки и столбца указано расстояние между
соответствующими пунктами
Пустая ячейка или прочерк означает отсутствие прямой дороги
Пример матрицы
A
B
C
D
E
A
-
2
3
-
-
B
2
-
4
5
-
C
3
4
-
1
-
D
-
5
1
-
6
E
-
-
-
6
-
Жёлтым выделены дороги из пункта A: до B (2 км) и до C (3 км).
🔍 Типы задач задания 4 ОГЭ
📍 Кратчайший путь между двумя пунктами
Найти минимальное расстояние от пункта X до пункта Y.
📍 Путь через определённый пункт
Найти кратчайший путь от X до Y, который обязательно проходит
через пункт Z.
📝 Алгоритм решения
Метод перебора путей
Для небольших графов (5-6 вершин) удобно использовать метод перебора
всех возможных путей:
Выпишите все возможные маршруты из начального пункта в конечный
Для каждого маршрута посчитайте суммарное расстояние
Выберите маршрут с минимальным расстоянием
⚠️ Важно!
При переборе путей не забывайте, что можно двигаться только по
дорогам, указанным в таблице. Если ячейка пуста — дороги нет!
Метод Дейкстры (для более сложных графов)
Алгоритм пошагового нахождения кратчайшего пути:
Отметьте начальную вершину расстоянием 0, остальные — ∞
Выберите непосещённую вершину с минимальным расстоянием
Для каждой соседней вершины пересчитайте расстояние через текущую
Если новое расстояние меньше — обновите его
Повторяйте шаги 2-4, пока не достигнете целевой вершины
Метод построения дерева путей
Этот метод наглядно показывает все возможные маршруты в виде дерева.
Он особенно удобен для задач ОГЭ с небольшим количеством вершин.
Начните с начального пункта — это корень дерева
От корня проведите ветви ко всем пунктам, куда можно попасть
напрямую
На каждой ветви подпишите расстояние
От каждого нового пункта проведите ветви дальше, не возвращаясь к
уже посещённым
Продолжайте, пока не достигнете конечного пункта
Сложите расстояния вдоль каждой ветви от корня до конечного пункта
Выберите путь с минимальной суммой
Пример дерева путей
Для поиска пути из A в E строим дерево всех возможных маршрутов:
Все возможные пути из A в E:
A → C → E = 3 + 2 = 5 км ←
кратчайший!
A → B → C → E = 2 + 3 + 2 = 7 км
A → B → C → D → E = 2 + 3 + 1 + 6 = 12 км
A → B → D → E = 2 + 5 + 6 = 13 км
A → C → D → E = 3 + 1 + 6 = 10 км
Ответ: Кратчайший путь
A → C → E = 5 км
Под каждой вершиной указано накопленное расстояние от начального
пункта A. Зелёным цветом выделен кратчайший путь.
✏️ Примеры решения задач
Пример 1: Кратчайший путь между двумя пунктами
Условие: Между населёнными пунктами A, B, C, D, E
построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и D.
A
B
C
D
E
A
-
2
5
-
-
B
2
-
3
-
-
C
5
3
-
4
2
D
-
-
4
-
1
E
-
-
2
1
-
Решение:
Шаг 1: Выпишем все возможные пути из A в D:
Путь 1: A → B → C → D
Расстояние: 2 + 3 + 4 = 9
Путь 2: A → B → C → E → D
Расстояние: 2 + 3 + 2 + 1 = 8
Путь 3: A → C → D
Расстояние: 5 + 4 = 9
Путь 4: A → C → E → D
Расстояние: 5 + 2 + 1 = 8 ← минимальный!
Ответ: 8
Пример 2: Путь через определённый пункт
Условие: Между населёнными пунктами A, B, C, D, E
построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и E, проходящего
через пункт C.
A
B
C
D
E
A
-
1
-
-
-
B
1
-
2
-
7
C
-
2
-
3
4
D
-
-
3
-
2
E
-
7
4
2
-
Решение:
Шаг 1: Разобьём задачу на две части:
1) Найти кратчайший путь из A в C
2) Найти кратчайший путь из C в E
Шаг 2: Пути из A в C:
• A → B → C = 1 + 2 = 3 ✓
Шаг 3: Пути из C в E:
• C → E = 4
• C → D → E = 3 + 2 = 5
Кратчайший: C → E = 4
Шаг 4: Объединяем пути:
A → B → C → E = 1 + 2 + 4 = 7
Ответ: 7
Пример 3: Граф с 6 вершинами
Условие: Между населёнными пунктами A, B, C, D, E,
F построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и F, проходящего
через пункт C.
A
B
C
D
E
F
A
-
3
-
-
-
-
B
3
-
1
-
4
-
C
-
1
-
2
5
-
D
-
-
2
-
1
3
E
-
4
5
1
-
2
F
-
-
-
3
2
-
Решение:
Шаг 1: Найти кратчайший путь из A в C:
• A → B → C = 3 + 1 = 4
Шаг 2: Найти кратчайший путь из C в F:
• C → D → F = 2 + 3 = 5
• C → D → E → F = 2 + 1 + 2 = 5
• C → E → F = 5 + 2 = 7
Кратчайший: C → D → F = 5
Шаг 3: Объединяем:
A → B → C → D → F = 3 + 1 + 2 + 3 = 9
Ответ: 9
⚠️ Частые ошибки
Пропуск путей — не все возможные маршруты
рассмотрены
Неправильное чтение таблицы — путаница между
строками и столбцами
Игнорирование условия — путь должен проходить через
указанный пункт