Текст. Урок 14. Степень (валентность) вершины. Цепь и цикл. Ориентированные графы

1. Определение степени вершины

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

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

Для неориентированного графа ребро считается один раз, независимо от того, смотрим мы «из вершины» или «в вершину».

Пример 1.
Рассмотрим граф:
Вершины: A, B, C, D.
Рёбра: A–B, A–C, B–C, B–D.

Найдём степени:

• Из A выходят рёбра в B и C → $\mathrm{deg}(A)=2$.

• Из B — рёбра в A, C, D → $\mathrm{deg}(B)=3$.

• Из C — рёбра в A, B → $\mathrm{deg}(C)=2$.

• Из D — только в B → $\mathrm{deg}(D)=1$.

2. Теорема о сумме степеней вершин

Это одно из самых важных свойств графов.

Теорема (лемма о рукопожатиях):
Сумма степеней всех вершин графа равна удвоенному числу рёбер:

$$\mathrm{deg}(v_1)+\mathrm{deg}(v_2)+\cdots +\mathrm{deg}(v_n)=2\cdot E$$

где $E$ — количество рёбер.

Почему это так?
Каждое ребро соединяет две вершины и вносит вклад в степени обеих вершин. Значит, каждое ребро «учитывается» дважды.

Проверка на примере 1:
Сумма степеней = $2+3+2+1=8$.
Рёбер $E=4$ (AB, AC, BC, BD).
$2\cdot 4=8$. Равенство выполняется.

Следствие: В любом графе сумма степеней всегда чётная.
Значит, количество вершин нечётной степени обязательно чётно.

Пример 2 (полезно для самопроверки):
В графе 5 вершин, степени: 3, 3, 2, 2, 2.
Сумма = 12 → рёбер = 6. Всё верно.
А если бы степени были 3, 3, 3, 2, 1 (сумма 12 — чётная), то тоже возможно. А 3, 3, 3, 1, 1 (сумма 11 — нечётная) — такого графа не существует.

3. Понятие цепи (пути)

В графе часто нужно найти маршрут из одной вершины в другую.

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

Длина цепи — количество рёбер в ней.

Пример 3.
В графе из примера 1:
A – B – D — это цепь длины 2 из A в D.
A – C – B – A — это цепь? Нет, потому что A повторяется (кроме случая, когда это замкнутая цепь — см. цикл).

Цепь можно задавать списком вершин: (A, B, D).

4. Цикл — замкнутая цепь

Определение:
Цикл — это цепь, у которой начальная и конечная вершины совпадают, а все остальные вершины различны.
Длина цикла — количество рёбер в нём.

Пример 4.
В том же графе: A – B – C – A — это цикл длины 3 (треугольник).
A – B – D – … — из D обратно в A нельзя (нет ребра D–A), значит, не цикл.

Цикл длины 3 называется треугольником.
Цикл длины 1 — петля (ребро из вершины в неё саму) — в школьных задачах редко.
Цикл длины 2 — две вершины, соединённые двумя разными рёбрами (мультиграф).

Пример 5 (граф без циклов):
Дерево (например, схема родословной без браков между родственниками) не содержит циклов.

5. Ориентированные графы (рёбра со стрелками)

До сих пор мы рассматривали неориентированные графы: по ребру можно двигаться в обе стороны.

В реальности связи часто направлены:

• одностороннее движение на улице;

• подписка в Instagram (Аня подписана на Борю, но Боря — не обязательно на Аню);

• передача информации (из А в В, но не обратно).

Определение:
Ориентированный граф (орграф) — граф, у которого каждое ребро имеет направление (изображается стрелкой).

Ребро в орграфе называют дугой.

Пример 6. Схема одностороннего движения:
Вершины — перекрёстки A, B, C.
Дуги: A→B, B→C, C→A (кольцевая односторонняя).
Из A можно попасть в C: A→B→C.
Из C в B — нельзя, так как C→A→B? Проверим: C→A есть, A→B есть → да, можно C→A→B. Значит, граф сильно связный (из любой вершины в любую есть путь).

Пример 7. Подписки в соцсети:
Вершины: Аня, Боря, Витя.
Дуги: Аня → Боря (Аня подписана на Борю),
Боря → Витя,
Витя → Аня.
Здесь тоже можно добраться по кругу, но не все связи взаимны.

6. Свойства ориентированных графов

В орграфе различают:

• Полустепень исхода $de{g}^{+}(v)$ — количество дуг, выходящих из вершины.

• Полустепень захода $de{g}^{-}(v)$ — количество дуг, входящих в вершину.

Для неориентированного графа $deg(v)=de{g}^{+}(v)+de{g}^{-}(v)$ — но в нём они не разделены.

Теорема для орграфа:
Сумма всех полустепеней исхода = сумме всех полустепеней захода = общему числу дуг.

Пример 8.
Орграф: дуги A→B, A→C, B→C.
$de{g}^{+}(A)=2$, $de{g}^{+}(B)=1$, $de{g}^{+}(C)=0$ → сумма = 3.
$de{g}^{-}(A)=0$, $de{g}^{-}(B)=1$, $de{g}^{-}(C)=2$ → сумма = 3.
Дуг = 3. Равенство выполняется.

7. Задачи на поиск путей и циклов в графах

Задача 1 (неориентированный граф)

Условие:
Граф задан рёбрами: AB, BC, CD, DE, BE, AD.
Найдите:
а) степень каждой вершины;
б) есть ли цикл длины 3;
в) цепь из A в E максимальной длины без повторения вершин.

Решение:
Вершины: A, B, C, D, E.
Степени:
A: соединён с B, D → deg=2
B: A, C, E → deg=3
C: B, D → deg=2
D: C, E, A → deg=3
E: B, D → deg=2

Сумма = 2+3+2+3+2=12, рёбер = 6 (AB, BC, CD, DE, BE, AD) → 2×6=12.

б) Цикл длины 3: ищем треугольники.
A–B–E–D–A? Это длины 4.
A–B–E–… нет.
B–C–D–E–B? длина 4.
A–D–C–B–A? Это 4.
Треугольников нет.

в) Цепь A→…→E без повторений:
A–B–C–D–E (длина 4)
A–B–E (длина 2)
A–D–E (длина 2)
A–D–C–B–E (длина 4) — ещё один.
Максимальная длина = 4.

Задача 2 (ориентированный граф)

Условие:
Дан орграф: дуги: 1→2, 2→3, 3→1, 3→4, 4→2.

Вопросы:
а) Найдите полустепени исхода и захода для вершины 3.
б) Есть ли в орграфе цикл? Если да, какой длины?
в) Можно ли из вершины 4 попасть в вершину 1?

Решение:
а) Вершина 3:
Исход: дуги 3→1, 3→4 → $de{g}^{+}(3)=2$
Заход: дуги 2→3 → $de{g}^{-}(3)=1$

б) Цикл (ориентированный) — замкнутый путь по стрелкам.
1→2→3→1 — это цикл длины 3.
Есть также 2→3→4→2 — ещё один цикл длины 3.

в) Из 4 в 1: 4→2→3→1 — да, можно.

8. Итоги урока (что нужно запомнить):

1. Степень вершины — количество рёбер, выходящих из неё (в неориентированном графе).

2. Сумма степеней вершин = $2\times$ (число рёбер).

3. Цепь — путь без повторяющихся вершин (кроме концов).

4. Цикл — замкнутая цепь (начало = конец).

5. В ориентированном графе у каждой дуги есть направление.

6. Различают полустепень исхода и полустепень захода.

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