Введение

Количество ребер, инцидентных вершине в графе

В теории графов степень (или валентность) вершины графа — это количество ребер, инцидентных этой вершине; в мультиграфе петля вносит вклад 2 в степень вершины, учитывая оба ее конца. Степень вершины обозначается или . Максимальная степень графа обозначается , и является максимальной из степеней всех вершин графа. Минимальная степень графа обозначается , и является минимальной из степеней всех вершин графа. На мультиграфе, изображенном справа, максимальная степень равна 5, а минимальная степень равна 0. В регулярном графе каждая вершина имеет одинаковую степень, поэтому можно говорить о степени графа. Полный граф (обозначается , где — количество вершин в графе) — это особый вид регулярного графа, в котором все вершины имеют максимально возможную степень. В ориентированном графе число положительных ребер, соединенных с вершиной , называется положительной степенью, а число отрицательных ребер, соединенных с вершиной, называется отрицательной степенью.

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

Последовательность степеней ненаправленного графа — это неубывающая последовательность степеней его вершин; для вышеуказанного графа это (5, 3, 3, 2, 2, 1, 0). Последовательность степеней является инвариантом графа, поэтому изоморфные графы имеют одну и ту же последовательность степеней. Однако последовательность степеней не определяет граф однозначно; в некоторых случаях неизоморфные графы могут иметь одну и ту же последовательность степеней. Задача о последовательности степеней — это задача нахождения некоторых или всех графов, для которых заданная неубывающая последовательность положительных целых чисел является последовательностью степеней. (Конечные нули можно игнорировать, поскольку они тривиально реализуются добавлением соответствующего числа изолированных вершин к графу.) Последовательность, которая является последовательностью степеней некоторого графа, то есть для которой задача о последовательности степеней имеет решение, называется графической последовательностью. Как следствие формулы суммы степеней, любая последовательность с нечётной суммой, например (3, 3, 1), не может быть реализована как последовательность степеней графа. Обратное также верно: если последовательность имеет чётную сумму, то она является последовательностью степеней мультиграфа. Построение такого графа просто: соедините вершины с нечётными степенями попарно (образуя паросочетание) и дополните оставшиеся чётные степени самопетлями. Вопрос о том, может ли заданная последовательность степеней быть реализована простым графом, более сложен. Эта задача также называется задачей реализации графа и может быть решена либо теоремой Эрдеша — Галлаи, либо алгоритмом Хавели — Хакими. Задача нахождения или оценки числа графов с заданной последовательностью степеней относится к области перечисления графов. В более общем смысле, последовательность степеней гиперграфа — это неубывающая последовательность степеней его вершин. Последовательность называется графической, если она является последовательностью степеней некоторого однородного гиперграфа. В частности, графическая последовательность является графической. Определение того, является ли заданная последовательность графической, возможно за полиномиальное время для с помощью теоремы Эрдеша — Галлаи, но является NP-полной задачей для всех .

Особые значения

Вершина со степенью 0 называется изолированной вершиной. Вершина со степенью 1 называется листом, конечной вершиной или висячей вершиной, а ребро, инцидентное этой вершине, называется висячим ребром. На графе справа {3,5} является висячим ребром. Эта терминология часто используется при изучении деревьев в теории графов и особенно деревьев как структур данных. Вершина со степенью n − 1 в графе на n вершинах называется доминирующей вершиной.

Глобальные свойства

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