Степень (валентность) вершины графа — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дваждыДистель, стр. 5.
Степень вершины обычно обозначается как или . Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.
Лемма о рукопожатиях
По формуле суммы степеней для графа ,
то есть сумма степеней вершин любого графа равна удвоенному числу его рёбер. Кроме того, из формулы следует, что в любом графе число вершин нечётной степени чётно. Данное утверждение (и сама формула) известны как лемма о рукопожатиях. Название происходит от известной математической задачи: необходимо доказать, что в любой группе число людей, пожавших руку нечётному числу других, чётно.
Последовательность степеней вершин
Последовательность степеней вершин неориентированного графа называется невозрастающая последовательность, образованная степенями всех вершин графа.Дистель, стр. 278 Для графа, изображённого на рис. 1, она имеет вид (5, 3, 3, 2, 2, 1, 0). Последовательность степеней вершин есть инвариант графа, так как у изоморфных графов она одинакова. Однако последовательность степеней вершин не является уникальной характеристикой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью.
Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 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 называется концевой (), висячей () или листом графа (). Ребро, инцидентное такой вершине называется висячим (). На рис. 3 висячим ребром является {3,5}. Подобная терминология используется в изучении деревьев в общем и как структур данных. Вершина степени n-1 графа порядка n называется доминирующей ().
Общие свойства Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k. В этом случае сам граф имеет степень k. Аналогично, двудольный граф, в котором любые две вершины, находящиеся на одной стороне двудольного графа, имеют одинаковую степень, называется двурегулярным графом. Эйлеров путь существует в неориентированном, связном графе тогда и только тогда, когда граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом. Орграф является псевдолесом только если полустепень исхода каждой вершины не больше 1. Функциональный граф — частный случай псевдолеса, в котором полустепени исхода всех вершин равны 1. Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1. k-вырожденным графом называется граф, в котором каждый подграф имеет вершину степенью не больше k.
См. также Полустепень захода и полустепень исхода вершин ориентированных графов Распределение степеней
Примечания
Источники . . . .
Категория:Теория графов