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

Граф с петлей, вершины которой помечены степенями

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

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

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

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

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

${\ Displaystyle \ сумма _ {v \ in V} \ deg (v) = 2 | E | \,}$.

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

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

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

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

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

В целом, последовательность степени из гиперграфа является не возрастающей последовательностью его степеней вершин. Последовательность является -графической, если она является последовательностью степеней некоторого -равномерного гиперграфа. В частности, графическая последовательность является графической. Решить, является ли данная последовательность -графической, можно за полиномиальное время для с помощью теоремы Эрдеша – Галлаи, но NP-полно для всех (Deza et al., 2018). ${\ displaystyle k}$${\ displaystyle k}$${\ displaystyle 2}$${\ displaystyle k}$${\ displaystyle k = 2}$${\ Displaystyle к \ geq 3}$

Особые ценности

Неориентированный граф с листовыми узлами 4, 5, 6, 7, 10, 11 и 12

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

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

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

Смотрите также

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

Примечания

использованная литература

• Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4.
• Erds, P .; Галлай, Т. (1960), «Графок элőирт фоксзаму понтоккал» (PDF) , Математикаи Лапок (на венгерском языке), 11 : 264–274.
• Гавел Вацлав (1955), "Замечание о существовании конечных графов" , Časopis Pro Pěstování Matematiky (в Чехии), 80 (4): 477-480, DOI : 10.21136 / CPM.1955.108220
• Хакой, С. Л. (1962), «О реализуемости множества целых чисел как степени вершин линейного графа я.», Журнал Общества промышленной и прикладной математика , 10 (3): 496-506, DOI : 10,1137 / 0110037 , MR  0148049.
• Сирксма, Жерар; Хоогевеен, Хан (1991), "критерии Семь для целочисленных последовательностей графики" , Журнал теории графов , 15 (2): 223-231, DOI : 10.1002 / jgt.3190150209 , МР  1106533.