Вся теория графов для ЕГЭ

Граф — это набор объектов и связей между ними. На ЕГЭ объектами обычно являются города, а связями — дороги.

Вершины — объекты графа; рёбра — связи между ними.

Неориентированный граф

Ориентированный граф

Неориентированный граф используют, когда связь работает в обе стороны.

Ориентированный граф содержит стрелки, которые показывают направление движения.

Степень вершины — количество рёбер, которые из неё выходят.

2. Взвешенный граф

Если на рёбрах стоят числа, это веса: длина дороги, стоимость или время в пути.

Числа рядом с рёбрами — веса дорог

3. Путь, маршрут и цикл

Путь — последовательность вершин, где каждая соседняя пара соединена ребром.

Цикл — замкнутый путь: начальная и конечная вершины совпадают.

Длина пути в обычном графе равна количеству рёбер, а во взвешенном — сумме их весов.

Красным выделен путь из вершины a в вершину h

4. Как граф записывают в таблицу

Строки и столбцы соответствуют вершинам. На пересечении двух городов записывают длину дороги, а если прямой дороги нет — ставят 0 или оставляют клетку пустой.

Пример таблицы расстояний

Для неориентированного графа таблица симметрична: если A–B = 4, то B–A = 4.

5. Как сопоставить граф и таблицу на ЕГЭ

1. Посчитай степени. Количество дорог у вершины равно количеству заполненных клеток в её строке.

2. Начни с уникальных вершин. Сначала найди вершины с редкой степенью: например, единственную вершину степени 4.

3. Сравни соседей. Проверь, с какими уже найденными вершинами соединён каждый кандидат.

4. Проверь все рёбра. После расстановки букв пройдись по графу ещё раз.

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

— Смотреть на расположение вершин вместо линий.  — Складывать номера вершин вместо весов.  — Определять вершины только по степени и не проверять соседей.