Информационные модели: графы, таблицы, схемы — теория для ЕГЭ

Коротко о главном

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

Главная идея: между объектами есть связи (родство, дороги, подчинённость), и эти связи нужно уметь считать и сопоставлять в разных представлениях.

Определения и формулы/правила

Понятие	Определение	Ключевое правило
Граф	Набор вершин (объектов) и ребёр (связей между ними)	Число ребёр равно числу связей, вершина — объект
Взвешенный граф	Граф, где каждому ребру приписано число (вес)	Вес — расстояние, стоимость, время и т.п.
Ориентированный граф	Граф со стрелками (связь имеет направление)	Из A в B ≠ из B в A
Матрица смежности	Таблица NxN, где на пересечении строки i и столбца j стоит вес ребра (или 0/1, если ребра нет)	Для неориентированного графа матрица симметрична относительно главной диагонали
Степень вершины	Количество ребёр, выходящих из вершины	Для неориентированного графа — просто число связей у объекта
Дерево	Связный граф без циклов, с выделенной вершиной-корнем	Число ребёр = число вершин − 1
Путь в графе	Последовательность вершин, соединённых ребрами	Длина пути = сумма весов ребёр на этом пути (если граф взвешенный)

Сумма степеней всех вершин графа равна удвоенному числу ребёр: $$\sum_{i=1}^{n} \deg(v_i) = 2E$$

Если граф задан таблицей (матрицей) весов, то отсутствие пути между объектами обычно обозначается прочерком, нулём или пустой клеткой — это нужно уточнять по условию задачи, единого стандарта нет.

Как применять

Пример 1. От таблицы к графу. Дана таблица связей городов А, Б, В, Г (весами обозначены расстояния, прочерк — нет дороги):

	А	Б	В	Г
А	—	5	—	3
Б	5	—	2	—
В	—	2	—	4
Г	3	—	4	—

Строим граф: А–Б (5), А–Г (3), Б–В (2), В–Г (4). Получился цикл из 4 вершин. Проверка: сумма степеней = 2+2+2+2=8, ребёр 4, значит $2E=8$ — совпадает.

Пример 2. Подсчёт степени вершины. В таблице выше у вершины А две связи (с Б и Г), значит степень А равна 2. Это соответствует числу непустых (не прочерк) клеток в строке А.

Пример 3. Поиск кратчайшего пути. Найти путь минимальной длины от А до В по графу из примера 1. Варианты: А–Б–В = 5+2 = 7; А–Г–В = 3+4 = 7. Оба пути равны — минимальная длина пути 7.

Типичные ошибки

• Путают ориентированный и неориентированный граф: считают, что связь А→Б автоматически означает Б→А, хотя в условии — стрелки.
• Забывают, что матрица смежности для неориентированного графа симметрична, и вносят рассогласованные данные при заполнении таблицы по графу или наоборот.
• Неверно считают степень вершины — учитывают саму вершину или путают с числом всех объектов в модели, а не с числом её связей.
• Ошибаются в переводе «прочерк = нет пути» и складывают несуществующие расстояния как 0, получая неверный кратчайший путь.
• При поиске кратчайшего пути забывают проверить все возможные маршруты, а не только очевидный первый.

Где встречается на экзамене

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