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

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 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]

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

Два неизоморфных графа с одинаковой последовательностью степеней (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. Ciotti, Valerio; Bianconi, Giestra; Capocci, Andrea; Colaiori, Francesca; Panzarasa, Pietro (2015). «Степень корреляции в подписанных социальных сетях». Physica A: Statistical Mechanics and Its Applications . 422 : 25–39. arXiv : 1412.1024 . Bibcode : 2015PhyA..422...25C. doi : 10.1016/j.physa.2014.11.062. S2CID  4995458. Архивировано из оригинала 2021-10-02 . Получено 2021-02-10 .
3. Сабери, Маджерид; Хосровабади, Реза; Хатиби, Али; Мисич, Братислав; Джафари, Голамреза (январь 2021 г.). «Топологическое влияние отрицательных связей на стабильность мозговой сети в состоянии покоя». Scientific Reports . 11 (1): 2176. Bibcode :2021NatSR..11.2176S. doi :10.1038/s41598-021-81767-7. PMC 7838299 . PMID  33500525. 
4. Гроссман, Питер (2009). Дискретная математика для вычислений. Bloomsbury . стр. 185. ISBN 978-0-230-21611-2.
5. Дистель (2005), стр. 216.
6. Деза, Антуан; Левин, Асаф; Меесум, Сайед М.; Онн, Шмуэль (январь 2018 г.). «Оптимизация последовательностей степеней». SIAM Journal on Discrete Mathematics . 32 (3): 2067–2079. arXiv : 1706.03951 . doi : 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. doi :10.1137/0110037. MR  0148049..
• Сиерксма, Жерар; Хугевен, Хан (1991). «Семь критериев графичности целочисленных последовательностей». Журнал теории графов . 15 (2): 223–231. дои : 10.1002/jgt.3190150209. МР  1106533..