Четвёртое задание из ОГЭ по информатике называется «Формальные описания реальных объектов и процессов» и представляет собой задачу о нахождении кратчайшего пути между населёнными пунктами. Для этого дана таблица, по которой необходимо построить граф и найти требуемый путь. Для его решения нужно уметь анализировать простейшие таблицы и графы. За решение 4 задания на экзамене вы получите 1 балл. Примерное время выполнения этого задания — 3 минуты.

Для решения 4 задания ОГЭ по информатике нужно знать следующее:

1) Графы - это набор вершин и связей между ними, которые называются рёбрами. Взвешенные графы имеют веса вершин и рёбер, а ориентированные - направление рёбер.

2) Путь в графе - это последовательность вершин, где каждая следующая вершина связана с предыдущей.

3) Дерево - это граф без циклов, где между любыми двумя вершинами существует единственный путь. Корень дерева - это главная вершина.

4) Весовая матрица - это таблица, где строки и столбцы соответствуют вершинам графа, а элементы матрицы - весам рёбер.

Алгоритм решения задания:

1. Построить граф, отображающий схему дорог между населёнными пунктами. Для этого расположите перечисленные вершины по кругу и соедините их дорогами, указанными в таблице.
2. Выделить вершины, которые обозначены в условии задачи.
3. Обратить внимание на вес графа и стараться проехать по самым коротким дорогам.

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

Для полного понимания темы, лучше ознакомиться с ней в учебнике по информатике за 9 класс.

1) На схеме нарисованы дороги между четырьмя населенными пунктами A, B, C, D и указаны протяженности данных дорог. Определите, какие два пункта наиболее удалены друг от друга (при условии, что передвигаться можно только по указанным на схеме дорогам). В ответе укажите кратчайшее расстояние между этими пунктами.

РЕШЕНИЕ

Два пункта считаются наиболее удаленными друг от друга, если длина кратчайшего пути между этими пунктами больше, чем длина кратчайшего пути между любыми другими двумя пунктами.

Найдем длины кратчайших путей между каждой парой пунктов:

В—С: 6 км.

В—D: 4 км.

С—D: 8 км.

А—В: 9 км.

А—С: 7 км.

А—D: прямого пути нет, рассмотрим разные маршруты:

A—B—D: длина маршрута 13 км.

A—C—D: длина маршрута 15 км.

A—B—C—D: длина маршрута 23 км.

A—C—B—D: длина маршрута 17 км.

Следовательно, кратчайший маршрут из А в D составляет 13 км.

Таким образом, наиболее удалены друг от друга пункты А и D, и кратчайшее расстояние между ними составляет 13 км.

Ответ: 13

2) Между населенными пунктами А, В, С, D, Е построены дороги, протяженность которых (в километрах) приведена в таблице:

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

РЕШЕНИЕ

Найдем все варианты маршрутов из A в E и выберем самый короткий.

Из пункта A можно попасть в пункт B.

Из пункта B можно попасть в пункты C, D, E.

Из пункта C можно попасть в пункт E.

Из пункта D можно попасть в пункт E.

A—B: длина маршрута 1 км.

A—B—C—E: длина маршрута 6 км.

A—B—D—E: длина маршрута 7 км.

A—B—E: длина маршрута 8 км.

Самый короткий путь: A—B—C—E. Длина маршрута 6 км.

Ответ: 6

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

Определите длину кратчайшего пути между пунктами A и B (при условии, что передвигаться можно только по построенным дорогам).

РЕШЕНИЕ

Найдем все варианты маршрутов из A в B и выберем самый короткий.

A—C—D—B: длина маршрута 13 км.

A—C—E—B: длина маршрута 12 км.

A—D—C—E—B: длина маршрута 15 км.

A—D—B: длина маршрута 14 км.

Самый короткий путь: A—C—E—B. Длина маршрута 12 км.

Ответ: 12