Степень вершины (теория графов)
Степень (валентность) вершины графа — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды.[1]
Степень вершины обычно обозначается как или . Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.
Лемма о рукопожатиях
По формуле суммы степеней для графа ,
то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, из формулы следует, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других, чётно.
Последовательность степеней вершин
Последовательность степеней вершин неориентированного графа называется невозрастающая последовательность, образованная степенями всех вершин графа.[2] Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, так как у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристикой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.
Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.
Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность di (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство
Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа; она удовлетворяет неравенству Эрдёша — Галлаи только при k равном 1, но не при k равном 2 или 3.
Согласно критерию Гавела — Хакими, если невозрастающая последовательность (d1, d2, …, dn) это последовательность степеней простого графа, то (d2 − 1, d3 − 1, …, dd1+1 − 1, dd1+2, dd1+3, …, dn) некоторая последовательность степеней простого графа. Этот факт позволяет построить полиномиальный алгоритм нахождения простого графа с заданной реализуемой последовательностью.
Сопоставим исходной последовательности чисел вершины графа без ребер с требуемыми степенями. Указанное преобразование последовательностей задает как минимум одну вершину графа, все инцидентные ей ребра и множество вершин с новыми требуемыми дополнениями степеней. Упорядочивая оставшиеся вершины по невозрастанию дополнений степеней, получим невозрастающую последовательность степеней простого графа. Повторяя преобразование и упорядочение не более n-1 раза, получаем весь граф.
Проблема нахождения или оценки числа графов по заданной последовательности относится к области перечисления графов.
Частные значения
- Вершина степени 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.
См. также
- Полустепень захода и полустепень исхода вершин ориентированных графов
- Распределение степеней
Примечания
Источники
- Дистель, Рейнхард (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4.
- Эрдёш, П.; Галлаи, T. (1960), "Gráfok előírt fokszámú pontokkal" (PDF), Matematikai Lapok (венг.), 11: 264—274.
- Хакими, С. Л. (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, MR 0148049.
- Сирксма, Хирард; Хоохефен, Хан (1991), "Seven criteria for integer sequences being graphic", Journal of Graph Theory, 15 (2): 223—231, doi:10.1002/jgt.3190150209, MR 1106533.