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