Часть 1. Задание 4.
Данное задание предполагаем понимание такой модели, как граф. Вам необходимо осуществлять поиск в графе, строить дерево на основе графа ("развёртывание" графа).
Вариант ОГЭ-2023. Демо.
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
Определите длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Решение.
Данная задача относится к задачам на графы.
Порядок решения:
1.Строим граф в черновике. Граф состоит из узлов (вершин) и ребер, рядом с которыми указывается вес ребра (в данном случае – протяженность дорог между пунктами).
2. Пишем цепочки дорог, проходящих через вершину С и определяем их длину.
На графе ребра, не участвующие в построении пути, сделаем пунктирными.
Составим все возможные пути, соединяющие вершину А с вершиной Е и проходящие через вершину С.
АBCDE = 1+2+3+2 = 8
ACDE = 4+3+2 = 9
Кратчайшим путем в графе, соединяющим две вершины будет 8.
Второй способ решения задачи
Берем за основу данные таблицы и строим дерево, которое начинается с вершины А, а конечной точкой является вершина Е.
Такое преобразование графа в дерево называется развертыванием графа.
Поясним построенное дерево.
Вершина А связана с вершинами В, С, D и Е.
Вершина В с вершинами С и D и т.д.
Связи и значение длин берем из таблицы.
После построения дерева, суммируем длины отрезков, которые проходят через вершину С.
Каким бы способом вы не решали поставленную задачу - результат должен быть одним и тем же.
В нашем случае в бланк ответов заносим число 8.
Задачи для самостоятельной работы.
Задача 1. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и E. Передвигаться можно только по дорогам, указанным в таблице.
Ответ
5
Задача 2. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, указанным в таблице.
Ответ
7
Задача 3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.
Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D. Передвигаться можно только по дорогам, указанным в таблице.
Ответ
10