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

Number of edges touching a vertex in a graph

Граф с циклом, вершины которого помечены степенью

В теории графов степень ( или валентность ) вершины графа — это количество ребер , инцидентных вершине ; в мультиграфе цикл добавляет 2 к степени вершины для двух концов ребра. ^[1] Степень вершины обозначается или . Максимальная степень графа , обозначаемая , и минимальная степень графа, обозначаемая , являются максимальной и минимальной степенями его вершин. В мультиграфе, показанном справа, максимальная степень равна 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}$

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

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

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

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

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

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

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

Последовательность степеней неориентированного графа — это невозрастающая последовательность степеней его вершин; ^[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}$

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

Неориентированный граф с листовыми узлами 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.
• k -вырожденный граф — это граф, в котором каждый подграф имеет вершину степени не выше k .

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

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

Примечания

1. Дистель, Рейнхард (2005). Теория графов (3-е изд.). Берлин, Нью-Йорк: Springer-Verlag. стр. 5, 28. ISBN. 978-3-540-26183-4.
2. Чиотти, Валерио; Бьянкони, Джестра; Капоччи, Андреа; Колайори, Франческа; Панзараса, Пьетро (2015). «Степень корреляции в подписанных социальных сетях». Физика А: Статистическая механика и ее приложения . 422 : 25–39. arXiv : 1412.1024 . Бибкод : 2015PhyA..422...25C. doi :10.1016/j.physa.2014.11.062. S2CID  4995458. Архивировано из оригинала 02 октября 2021 г. Проверено 10 февраля 2021 г.
3. Сабери, Маджерид; Хосровабади, Реза; Хатиби, Али; Мишич, Братислав; Джафари, Голамреза (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность мозговой сети в состоянии покоя». Научные отчеты . 11 (1): 2176. Бибкод : 2021НатСР..11.2176С. дои : 10.1038/s41598-021-81767-7. ПМЦ 7838299 . ПМИД  33500525. 
4. Гроссман, Питер (2009). Дискретная математика для вычислений. Блумсбери . п. 185. ИСБН 978-0-230-21611-2.
5. Дистель (2005), с. 216.
6. Деза, Антуан; Левин, Асаф; Мисам, Сайед М.; Онн, Шмуэль (январь 2018 г.). «Оптимизация по последовательностям степеней». SIAM Journal по дискретной математике . 32 (3): 2067–2079. arXiv : 1706.03951 . дои : 10.1137/17M1134482. ISSN  0895-4801. S2CID  52039639.

Рекомендации

• Эрдеш, П .; Галлай, Т. (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. дои : 10.1137/0110037. МР  0148049..
• Сиерксма, Жерар; Хугевен, Хан (1991). «Семь критериев графичности целочисленных последовательностей». Журнал теории графов . 15 (2): 223–231. дои : 10.1002/jgt.3190150209. МР  1106533..