Теория:
Характеристика задания
1. Тип ответа: числовой.
2. Структура содержания задания: дана таблица, по которой необходимо построить граф и найти требуемый путь.
3. Уровень сложности: базовый.
4. Примерное время выполнения: \(3\) минуты.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: нет.
7. Задание проверяет умение анализировать простейшие модели объектов (таблицы, графы).
2. Структура содержания задания: дана таблица, по которой необходимо построить граф и найти требуемый путь.
3. Уровень сложности: базовый.
4. Примерное время выполнения: \(3\) минуты.
5. Количество баллов: \(1\).
6. Требуется специальное программное обеспечение: нет.
7. Задание проверяет умение анализировать простейшие модели объектов (таблицы, графы).
Пример задания из демоверсии ОГЭ-\(2024\)
\( \)
Между населёнными пунктами A, B, C, D, E построены дороги, протяжённость которых (в километрах) приведена в таблице.
A | B | C | D | E | |
A | \(1\) | \(4\) | \(3\) | \(7\) | |
B | \(1\) | \(2\) | \(5\) | ||
C | \(4\) | \(2\) | \(3\) | ||
D | \(3\) | \(5\) | \(3\) | \(2\) | |
E | \(2\) |
Определи длину кратчайшего пути между пунктами A и Е, проходящего через пункт С. Передвигаться можно только по дорогам, протяжённость которых указана в таблице. Каждый пункт можно посетить только один раз.
Обрати внимание!
Алгоритм правильного решения:
• Внимательно смотрим минимальное или максимальное расстояние мы ищем.
• Отметим для себя существует ли пункт через который мы должны проехать обязательно, или тот, в который заезжать запрещено.
• Важно не ограничиваться рассмотрением только прямого пути из А в В, нужно рассмотреть все пути!
• Важно правильно нарисовать схему!
• Внимательно смотрим минимальное или максимальное расстояние мы ищем.
• Отметим для себя существует ли пункт через который мы должны проехать обязательно, или тот, в который заезжать запрещено.
• Важно не ограничиваться рассмотрением только прямого пути из А в В, нужно рассмотреть все пути!
• Важно правильно нарисовать схему!
Решение
1) Построим граф отображающий схему дорог между населенными пунктами, для этого расположим перечисленные вершины по кругу и соединим их дорогами указанными в таблице:
Рис. \(1\). Схема дорог
2) Выделим вершины которые обозначены в условии задачи:
Рис. \(2\). Пункты обязательного прохождения
3) Стараемся как можно «быстрее» доехать из А в С, для этого обращаем внимание на вес графа и стараемся проехать по самым коротким дорогам. Видим, что кратчайший путь из А в С лежит через В и его длина A – B – C \(=\) \(1 + 2\) \(=\) \(3\).
Рис. \(3\). Кратчайший путь из А в С
4) Аналогично видим, что кратчайший путь из С в Е лежит через D и его длина C – D – E \(=\) \(3 + 2\) \(=\) \(5\).
Рис. \(4\). Кратчайший путь из С в Е
5) Итак, минимальная длина пути из А в Е через С равна \(3 + 5\) \(=\) \(8\).
Рис. \(5\). Из А в Е через С
Правильный ответ: \(8\).
Обрати внимание!
• Построение схемы по таблице повышает наглядность задачи.
• Наглядность схемы зависит от того, как удачно ты выберешь расположение её вершин; один из вариантов – сначала расставить все вершины по окружности и нарисовать все связи.
• Постарайся не пропустить решение с минимальным вариантом.
• Наглядность схемы зависит от того, как удачно ты выберешь расположение её вершин; один из вариантов – сначала расставить все вершины по окружности и нарисовать все связи.
• Постарайся не пропустить решение с минимальным вариантом.
Рассмотрим ещё один пример.
Найди самый короткий путь из вершины А в вершину Е (в ответе напиши только число).
Рис. \(6\). Таблица
Рассмотрим решение этой задачи без построения графа:
1) Отметим вершины, которые нас интересуют по условию задачи:
Рис. \(7\). Нужные вершины
2) Постараемся избегать самые длинные пути:
2) Постараемся избегать самые длинные пути:
Рис. \(8\). Самые длинные пути
3) Отметим для себя самые выгодные пути, будем на них ориентироваться:
Рис. \(9\). Выгодные пути
4) Из вершины А у нас осталась одна дорога в В (АВ \(=\) \(3\)) , из В минимальная дорога идёт в Г (ВГ \(=\) \(7\) ) и далее из Г в Д (ГД \(=\) \(6\) ), АВГД \(=\) \(16 \)
Не забудем проверить, что дорога А-В-Б-Д длиннее, чем А-В-Г-Д и нам не подходит: АВБД \(=\) \(19\).
Рис. \(10\). Подбор дорог
Ну и, наконец, из Д попадаем в Е (ДЕ \(=\) \(2\)).
Рис. \(11\). Подбор дорог \(2\)
Итак мы получили дорогу: А-В-Г-Д-Е \(=\) \(3 + 7 + 6 + 2\) \(=\) \(18\).
Ответ: \(18\).