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

Граф с петлей, вершины которой обозначены степенью

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

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

Содержание

• 1 Лемма о подтверждении связи
• Последовательность 2 степеней
• 3 Специальные значения
• 4 Глобальные свойства
• 5 См. Также
• 6 Примечания
• 7 Ссылки

Лемма о подтверждении связи

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

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

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

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

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

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

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

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

Специальные значения

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

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

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

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

См. также

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

Примечания

Ссылки

• Diestel, Reinhard (2005), Graph Theory (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
• Хакими, SL (1962), «О реализуемости набора целых чисел как степени вершин линейного графа. I ", Журнал Общества промышленной и прикладной математики, 10 (3): 496–506, doi : 10.1137 / 0110037, MR 0148049.
• Сирксма, Джерард; Hoogeveen, Han (1991), «Семь критериев для графических последовательностей целых чисел», Journal of Graph Theory, 15(2): 223–231, doi : 10.1002 / jgt.3190150209, MR 1106533.