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

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

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

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

Лемма о рукопожатии [ править ]

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

\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), не может быть реализована как последовательность степеней графа. Верно и обратное: если последовательность имеет четную сумму, это последовательность степеней мультиграфа. Построение такого графа простое: соедините вершины с нечетными степенями попарно (образуя паросочетание ) , а оставшиеся четные степени заполните циклами. Вопрос о том, может ли данная последовательность степеней быть реализована с помощью простого графа, является более сложным. Эту проблему еще называют Проблема реализации графа и может быть решена либо с помощью теоремы Эрдеша–Галлаи , либо с помощью алгоритма Гавела–Хакими . Задача нахождения или оценки количества графов с заданной последовательностью степеней является задачей из области нумерации графов .

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

Специальные значения [ править ]

Неориентированный граф с листовыми узлами 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 .

См. также [ править ]

Примечания [ править ]

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

Ссылки [ править ]

Эрдеш, П .; Галлай, Т. (1960). «Графики с точками заданной степени» (PDF) . Математические статьи (на венгерском языке). 11 : 264–274. .
Гавел, Вацлав (1955). «Замечание о существовании конечных графов» . Журнал по развитию математики (на чешском языке). 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 . .

[1] Дистель, Рейнхард (2005). Теория графов (3-е изд.). Берлин, Нью-Йорк: Springer Verlag. стр. 5, 28. ISBN 978-3-540-26183-4 .

[10.1016/j.physa.2014.11.062-2] Чиотти, Валерио; Бьянкони, Джестра; Капоччи, Андреа; Колайори, Франческа; Панзараса, Пьетро (2015). «Степень корреляции в подписанных социальных сетях» . Физика А: Статистическая механика и ее приложения . 422 : 25–39. arXiv : 1412.1024 . Бибкод : 2015PhyA..422...25C . дои : 10.1016/j.physa.2014.11.062 . S2CID 4995458 . Архивировано из оригинала 2 октября 2021 г. Проверено 10 февраля 2021 г.

[3] Сабери, Маджерид; Хосровабади, Реза; Хатиби, Али; Мишич, Братислав; Джафари, Голамреза (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность сети мозга в состоянии покоя» . Научные отчеты . 11 (1): 2176. Бибкод : 2021NatSR..11.2176S . дои : 10.1038/s41598-021-81767-7 . ПМЦ 7838299 . ПМИД 33500525 .

[4] Гроссман, Питер (2009). Дискретная математика для вычислений . Блумсбери . п. 185. ИСБН 978-0-230-21611-2 .

[FOOTNOTEDiestel2005216-5] Дистель (2005) , с. 216.

[6] Деза, Антуан; Левин, Асаф; Мисам, Сайед М.; Онн, Шмуэль (январь 2018 г.). «Оптимизация по последовательностям степеней». SIAM Journal по дискретной математике . 32 (3): 2067–2079. arXiv : 1706.03951 . дои : 10.1137/17M1134482 . ISSN 0895-4801 . S2CID 52039639 .

[1]

[2]

[3]

[4]

[5]

[6]