Задание №3 ОГЭ. Соответствие между таблицей смежности и графом

Моделирование объектов и процессов относится к содержательным элементам, проверяемым в задании №3 экзаменационной работы за курс основной школы по информатике и ИКТ.

В задаче, относящейся к базовому уровню сложности, проверяются умения экзаменуемых создавать и использовать различные формы представления информации. Моделями, между которыми необходимо установить соответствие, являются таблица смежности и граф.

Для подготовки к ОГЭ по информтатике и ИКТ рассмотрим примеры задания №3, встречавшиеся в тренировочных и демонстрационных работах прошлых лет и разберем способы их решения.

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

Таблица смежности

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

  1. 4
  2. 5
  3. 6
  4. 7

Решение.

Рассмотрим таблицу из условия. Наличие числового значения на пересечении строки и столбца указывает на наличие между пунктами дороги. Отметим, что между некоторыми пунктами дороги отсутствуют. Для решения задачи построим граф (см. рис. 1) по данной таблице.

Граф

По построению видно, что кратчайший путь между пунктами A и Е – это путь ABCE.

Определим длину пути ABCE: 2 + 1 + 2 = 5.

Ответ. 2