Граф, вершина, ребро

Определение. Граф

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

Вершина — точка графа, обозначающая объект. Ребро — линия, соединяющая две вершины и обозначающая связь между ними. Ребро всегда соединяет ровно две вершины.

Степень вершины

Степень вершины — число рёбер, выходящих из этой вершины. Обозначается $\deg(v)$.

• Вершина, из которой выходит $k$ рёбер, имеет степень $k$.
• Вершина, из которой не выходит ни одного ребра, называется изолированной, её степень равна $0$.

Число рёбер и сумма степеней

Между числом рёбер и степенями вершин есть важная связь. Каждое ребро соединяет две вершины, поэтому оно «считается» в степени каждой из них. Значит:

$\sum_{v} \deg(v) = 2E$

где $E$ — число рёбер графа. Сумма степеней всех вершин равна удвоенному числу рёбер.

Пример 1. Степени вершин

Дан граф с вершинами A, B, C и рёбрами A–B, B–C. Найти степени всех вершин.

Дано: рёбра: A–B, B–C. Вершины: A, B, C.

Формула: степень вершины — число выходящих из неё рёбер.

Подстановка: из A выходит одно ребро (A–B) → $\deg(A)=1$. Из B выходят два ребра (A–B и B–C) → $\deg(B)=2$. Из C выходит одно ребро (B–C) → $\deg(C)=1$.

Ответ: $\deg(A)=1$, $\deg(B)=2$, $\deg(C)=1$.

Пример 2. Сумма степеней

Для графа из примера 1 проверить связь между суммой степеней и числом рёбер.

Дано: $\deg(A)=1$, $\deg(B)=2$, $\deg(C)=1$; рёбер $E = 2$.

Формула: $\sum \deg(v) = 2E$.

Подстановка: сумма степеней $= 1+2+1 = 4$. $2E = 2 \times 2 = 4$.

Ответ: сумма степеней $4$ равна $2E = 4$ — связь подтвердилась.

Пример 3. Изолированная вершина

Дан граф с вершинами A, B, C, D и рёбрами A–B, B–C. Найти степень вершины D.

Дано: рёбра: A–B, B–C. Вершины: A, B, C, D.

Формула: степень вершины — число выходящих из неё рёбер.

Подстановка: из D не выходит ни одного ребра → $\deg(D) = 0$.

Ответ: вершина D изолированная, её степень равна $0$.

Важно!

⚠️ Типичная ошибка — считать, что ребро «принадлежит» одной вершине. Каждое ребро соединяет две вершины и учитывается в степени обеих. Поэтому сумма всех степеней всегда чётная и равна удвоенному числу рёбер. Если сумма степеней получилась нечётной — ты где-то ошибся в подсчёте.