Графы, деревья, таблицы как информационные модели: ЕГЭ по информатике

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

Что нужно знать

• Граф — совокупность вершин и соединяющих их рёбер; может быть ориентированным (орграф) или неориентированным, взвешенным или невзвешенным.
• Дерево — связный ациклический граф; число рёбер в дереве с n вершинами равно n−1; между любыми двумя вершинами существует единственный простой путь.
• Таблица — информационная модель, представляющая данные в виде строк и столбцов; используется для описания объектов и их свойств, а также связей между объектами.
• В ЕГЭ графы и таблицы часто применяются для моделирования дорог, сетей, родственных связей, турниров и других систем.
• Для решения задач на графы важно уметь строить граф по описанию, находить кратчайшие пути (алгоритм Дейкстры, метод перебора), определять степени вершин, выявлять циклы.
• Деревья используются при описании иерархических структур (файловая система, классификация), в задачах на подсчёт количества путей, определение высоты дерева.

Термины и понятия

• Граф: множество вершин и множество рёбер, соединяющих пары вершин.
• Ориентированный граф (орграф): граф, в котором рёбра имеют направление (дуги).
• Взвешенный граф: граф, каждому ребру которого сопоставлено числовое значение (вес).
• Дерево: связный граф без циклов.
• Корневое дерево: дерево с выделенной вершиной (корнем), в котором задано направление от корня к листьям.
• Степень вершины: число рёбер, инцидентных данной вершине (в орграфе различают полустепень захода и исхода).
• Путь в графе: последовательность вершин, где каждая пара соседних соединена ребром.
• Цикл: путь, начинающийся и заканчивающийся в одной и той же вершине, без повторения рёбер (простой цикл).

Частые ошибки

• Путаница между ориентированными и неориентированными графами при построении модели.
• Неверное определение кратчайшего пути из-за игнорирования весов рёбер или направления дуг.
• Ошибки при подсчёте количества путей: забывают учитывать направление или допускают циклы там, где их быть не должно.
• Неверное применение формулы для числа рёбер в дереве (n−1) для графов с циклами.

Как пройти тему

В курсе «Информатика» тема «Графы, деревья, таблицы как информационные модели» занимает 2 занятия по 40 минут: репетитор объясняет материал, задаёт вопросы как на экзамене, разбирает ваши ответы и в конце ставит оценку. Это обзор темы, полный разбор — в занятии. ИИ может ошибаться: проверяйте важное по учебнику. Занятия не заменяют живого репетитора и не гарантируют результат на экзамене.

Другие темы раздела

• Модели и моделирование. Виды моделей
• Формализация и математические модели
• Имитационное моделирование. Анализ моделей

← Предыдущая тема: Модели и моделирование. Виды моделей
Следующая тема: Формализация и математические модели

Все темы: ЕГЭ по информатике