Графы

10 заданий

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

Граф с пятью вершинами и шестью рёбрами; степень вершины \(B\) равна 3, вершины \(E\) — 1

Сумма степеней всех вершин равна удвоенному числу рёбер (каждое ребро посчитано дважды): на рисунке \(2 + 3 + 3 + 3 + 1 = 12 = 2\cdot 6\). Отсюда следует, что число вершин нечётной степени всегда чётно.

Пример. В компании из 7 человек каждый знаком ровно с тремя другими. Может ли так быть?
Решение. Сумма степеней \(7\cdot 3 = 21\) — нечётное число, а она должна быть чётной. Нет, не может.

Кратчайший путь на схеме дорог находят перебором маршрутов: сложите длины рёбер вдоль каждого пути и выберите наименьшую сумму.

Из истории. Теория графов началась с задачи о семи мостах Кёнигсберга: можно ли обойти все мосты, пройдя по каждому ровно один раз? Леонард Эйлер в 1736 году доказал, что нельзя: у графа мостов слишком много вершин нечётной степени. Сегодня графами описывают маршруты навигаторов и социальные сети.

Как это спрашивают на ОГЭ. Схема дорог между пунктами в практическом блоке 1–5 — это граф с длинами рёбер: «найдите длину кратчайшего пути», «на сколько километров длиннее маршрут через…». Перечислите все маршруты, не заходя в один пункт дважды, и сравните суммы.

Пример. В графе 7 вершин, степень каждой равна 4. Сколько в нём рёбер?
Решение. Сумма степеней \(7\cdot 4 = 28\) равна удвоенному числу рёбер, значит, рёбер \(28 : 2 = 14\).

Закрепите теорию: 10 заданий с проверкой и подсказками, урок зачитывается от 70 %.

Пройти урок arrow_forward