Степень вершины (теория графов)

Рис. 1. Граф, на вершинах которого отмечены степени.

Степень вершины (англ. degree, также валентность, англ. valency) в теории графов — количество рёбер графа $G$, инцидентных вершине $x$. При подсчёте степени ребро-петля учитывается дважды.^[1] Степень вершины обозначается как $d(x)$ (в западных источниках — $\deg(v)$). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

Лемма о рукопожатиях

Основная статья: Лемма о рукопожатиях

По формуле суммы степеней для графа $G=(V, E)$,

$\sum_{v \in V} \deg(v) = 2|E|\, ,$

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

Последовательность степеней вершин

Рис. 2. Два неизоморфных графа с одинаковой последовательностью степеней (3, 2, 2, 2, 2, 1, 1, 1).

Последовательность степеней вершин неориентированного графа является невозрастающей последовательностью.^[2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, поэтому у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристкой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность d_i (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство

$\sum_{i=1}^{k}d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i,k) \quad \ k \in \{1,\dots,n\} \, .$

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, 2 или 4, но не при k равном 3.

С. Л. Хакими доказал, что (d₁, d₂, …, d_n) есть последовательность степеней простого графа только если существует (d₂ − 1, d₃ − 1, …, d_d1+1 − 1, d_d1+2, d_d1+3, …, d_n). Этот факт позволил разработать простой алгоритм нахождения простого графа с заданной реализуемой последовательностью:

1. Изначально граф не имеет рёбер.
2. Составляется список вершин, для которых требования по степеням пока не удовлетворены. Оставшиеся требования располагаются в порядке невозрастания.
3. Первая вершина соединяется со следующими d₁ вершинами из списка. После этого первая вершина удаляется, список пересортируется. Действие повторяется до тех пор, пока все требования не будут удовлетворены.

Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов.

Частные значения

Рис. 3. Концевыми вершинами являются 4, 5, 6, 7, 10, 11 и 12.

• Вершина степени 0 называется изолированной.
• Вершина степени 1 называется концевой (англ. end vertex), висячей (англ. pendant vertex) или листом графа (англ. leaf vertex). Ребро, инцидентное такой вершине называется висячим (англ. terminal (pendant) edge, end-edge). На рис. 3 висячим ребром является {3,5}. Подобная терминология используется в изучении деревьев в общем и как структур данных.
• Вершина степени n-1 графа порядка n называется доминирующей (англ. dominating vertex).

Общие свойства

• Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k. В этом случае сам граф имеет степень k.
• Эйлеров путь существует в неориентированном, связном графе если и только если граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом.
• Орграф является псевдолесом только если полустепень захода каждой вершины не больше 1. Функциональный граф — частный случай псевдолеса, в котором полустепени захода всех вершин равны 1.
• Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1.
• k-вырожденным графом называется граф, в котором каждый подграф имеет вершину степенью не больше k.

См. также

• Полустепень захода и полустепень исхода вершин ориентированных графов
• Распределение степеней

Примечания

1. ↑ Дистель, стр. 5
2. ↑ Дистель, стр. 278

Источники

• Дистель, Рейнхард (2005), «Graph Theory» (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <http://diestel-graph-theory.com/index.html> .
• Эрдёш, П. & Галлаи, T. (1960), "«Gráfok előírt fokszámú pontokkal»", Matematikai Lapok Т. 11: 264—274, <http://www.renyi.hu/~p_erdos/1961-05.pdf> .
• Хакими, С. Л. (1962), "«On realizability of a set of integers as degrees of the vertices of a linear graph. I»", Journal of the Society for Industrial and Applied Mathematics Т. 10: 496–506 .
• Сирксма, Хирард & Хоохефен, Хан (1991), "«Seven criteria for integer sequences being graphic»", Journal of Graph Theory Т. 15 (2): 223–231, DOI 10.1002/jgt.3190150209 .