Часть 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. Передвигаться можно только по дорогам, указанным в таблице.

Задача 2. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.

Определите длину кратчайшего пути между пунктами A и D. Передвигаться можно только по дорогам, указанным в таблице.

Задача 3. Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых приведена в таблице.

Определите длину кратчайшего пути между пунктами A и E, проходящего через пункт D. Передвигаться можно только по дорогам, указанным в таблице.