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

В теории графов степень (или валентность ) вершины графа — это число ребер , инцидентных вершине; в мультиграфе петля добавляет 2 к степени вершины для двух концов ребра. ^[1] Степень вершины обозначается или . Максимальная степень графа обозначается , и является максимальной из степеней вершин. Минимальная степень графа обозначается , и является минимальной из степеней вершин. В мультиграфе, показанном справа, максимальная степень равна 5, а минимальная степень равна 0.${\displaystyle v}$${\displaystyle \deg(v)}$${\displaystyle \deg v}$${\displaystyle G}$${\displaystyle \Delta (G)}$${\displaystyle G}$${\displaystyle \delta (G)}$${\displaystyle G}$

В регулярном графе каждая вершина имеет одинаковую степень, поэтому мы можем говорить о степени графа. Полный граф (обозначается , где — число вершин в графе) — это особый вид регулярного графа, в котором все вершины имеют максимально возможную степень, .${\displaystyle K_{n}}$${\displaystyle n}$${\displaystyle n-1}$

В знаковом графе число положительных ребер, соединенных с вершиной, называется положительным градусом , а число соединенных отрицательных ребер называется отрицательным градусом . ^{[2] [3]}${\displaystyle v}$${\displaystyle (v)}$${\displaystyle (v)}$

Формула суммы степеней гласит , что для данного графика${\displaystyle G=(V,E)}$

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$.

Формула подразумевает, что в любом неориентированном графе число вершин с нечетной степенью четно. Это утверждение (как и формула суммы степеней) известно как лемма о рукопожатии . Последнее название происходит от популярной математической задачи, которая заключается в доказательстве того, что в любой группе людей число людей, пожимавших руки нечетному числу других людей из этой группы, четно. ^[4]

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

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

В более общем смысле, последовательность степеней гиперграфа — это невозрастающая последовательность степеней его вершин. Последовательность является -графической, если она является последовательностью степеней некоторого -однородного гиперграфа. В частности, -графическая последовательность является графической. Определение того, является ли заданная последовательность -графической , выполнимо за полиномиальное время для с помощью теоремы Эрдёша–Галлаи , но является NP-полной задачей для всех . ^[6]${\displaystyle k}$${\displaystyle k}$${\displaystyle 2}$${\displaystyle k}$${\displaystyle k=2}$${\displaystyle k\geq 3}$

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

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

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

• Эрдеш, П .; Галлай, Т. (1960). «Gráfok előírt fokszámú pontokkal» (PDF) . Математикай Лапок (на венгерском языке). 11 : 264–274..
• Гавел, Вацлав (1955). «Замечание о существовании конечных графов». Časopis Pro Pěstování Matematiky (на чешском языке). 80 (4): 477–480. дои : 10.21136/CPM.1955.108220 .
• Хакими, С.Л. (1962). «О реализуемости множества целых чисел в виде степеней вершин линейного графа. I». Журнал Общества промышленной и прикладной математики . 10 (3): 496–506. doi :10.1137/0110037. MR  0148049..
• Сиерксма, Жерар; Хугевен, Хан (1991). «Семь критериев графичности целочисленных последовательностей». Журнал теории графов . 15 (2): 223–231. дои : 10.1002/jgt.3190150209. МР  1106533..