Памятка к 4 заданию (ОГЭ информатика)

Графы, деревья и таблицы

Графы — это набор вершин и связей между ними, которые называются ребрами.

Взвешенные графы имеют веса вершин и ребер.

Ориентированные графы имеют направление ребер.

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

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

Корень дерева — это главная вершина.

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

ОГЭ: Информатика

4 задание (3 минуты)

А нализ простейших моделей объектов

1 тип заданий:

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

Записываются все варианты маршрутов из A в F.

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

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

• A—C—D—E—F: длина маршрута 10 км.

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

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

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

Ответ: 9.

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

Решение (используется дерево или взвешенный граф):

• по данной таблице строиться дерево или граф;

• по созданному дереву или графу выполняется поиск всех интересующих вариантов;

• выбрать нужный вариант.

Решение:

1 способ: 2 способ:

Строим дерево Строим граф

2 тип заданий с усложнением: (демоверсия 2024)

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

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

Решение (используется дерево или

взвешенный граф):

• по данной таблице строиться дерево или граф;

• по созданному дереву или графу выполняется поиск всех интересующих вариантов;

• выбрать нужный вариант.

Решение:

1 способ: 2 способ:

Строим дерево Строим граф

Записываются все варианты маршрутов из A в E, проходящие через С.

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

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

Самый короткий путь: A—B—C—D—E.

Длина маршрута 8 км.

Ответ: 8.

Типичная ошибка! Просчитываются не все варианты.