4-е задание ОГЭ информатика

4-е задание: «Формальные описания реальных объектов и процессов»
Уровень сложности — базовый,
Максимальный балл — 1,
Примерное время выполнения — 3 минуты.

Инструкция к тесту

Графы

Иногда очень трудно структурировать информацию описанными структурами из-за сложных «взаимоотношений» между объектами. Тогда можно использовать графы:

Граф – это набор вершин и связей между ними, называющихся рёбрами:

Граф

Граф, отображающий дороги между поселками

 

Матрица и список смежности

матрица и список смежностей

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

Связный граф

Связный граф


Дерево – это связный граф без циклов (замкнутых участков).

Дерево - связный граф без циклов

Дерево — связный граф без циклов

 

Взвешенные графы и весовая матрица

У взвешенных графов указан «вес ребра»:
взвешенный граф

Из взвешенных графов получается весовая матрица, обратное преобразование тоже возможно.

Весовая матрица

Весовая матрица

 

ПОИСК КРАТЧАЙШЕГО ПУТИ (ПЕРЕБОР)

кратчайший путь

Определение кратчайшего пути между пунктами A и D

  • В заданиях ОГЭ этой темы чаще всего используются две информационные модели — таблицы и схемы.
  • Информация в таблице строится по следующим правилам: на пересечении строки и столбца находится информация, характеризующая комбинацию этой строки и столбца.
  • На схеме информация строится по следующему правилу: если между объектами схемы имеется связь, то она отображается линией, соединяющей названия этих объектов на схеме.
Количество вопросов в тесте: 10
 
Источник: https://labs-org.ru/oge-4/