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

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

В теории графов , то степень (или валентность ) из вершины в виде графа является числом ребер , которые падающие к вершине, а в мультиграфе , петли учитываются дважды. ^[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}$

В графе со знаком количество положительных ребер, соединенных с вершиной , называется положительным градусом, а количество связанных отрицательных ребер - отрицательным градусом . ^[2]^[3] ${\ 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).

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

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

В целом, последовательность степени из гиперграфа является не возрастающей последовательностью его степеней вершин. Последовательность является -графической, если она является последовательностью степеней некоторого -однородного гиперграфа. В частности, графическая последовательность является графической. Решение о том, является ли данная последовательность -графической, выполняется за полиномиальное время для с помощью теоремы Эрдеша – Галлаи, но является NP-полной для всех (Deza et al., 2018 ^[5] ). ${\ 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.
По теореме Брукса любой граф, кроме клики или нечетного цикла, имеет хроматическое число не более Δ, а по теореме Визинга любой граф имеет хроматический индекс не более Δ + 1.
К -degenerate график представляет собой график , в котором каждый подграф имеет вершину степени по большей к .

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

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

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

^ Дистель стр.5
^ Ciotti В (2015). «Степенные корреляции в подписанных социальных сетях» . Physica A: Статистическая механика и ее приложения . arXiv : 1412.1024 . DOI : 10.1016 / j.physa.2014.11.062 .
^ Сабери М, Khosrowabadi R, Хатиби А, Мисич В, С Джафари (январь 2021 года). «Топологическое влияние отрицательных связей на стабильность сети мозга в состоянии покоя» . Научные отчеты . DOI : 10.1038 / s41598-021-81767-7 . PMC 7838299 . PMID 33500525 .
^ Diestel p.216
^ Деза, Антуан; Левин, Асаф; Meesum, Syed M .; Онн, Шмуэль (январь 2018 г.). «Оптимизация по степенным последовательностям». Журнал СИАМ по дискретной математике . 32 (3): 2067–2079. arXiv : 1706.03951 . DOI : 10.1137 / 17M1134482 . ISSN 0895-4801 . S2CID 52039639 .

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

Дистель, Рейнхард (2005), Теория графов (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-3-540-26183-4.
Erdős, 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 , Руководство по ремонту 0148049.
Сирксма, Жерар; Хоогевеен, Хан (1991), "критерии Семь для целочисленных последовательностей графики" , Журнал теории графов , 15 (2): 223-231, DOI : 10.1002 / jgt.3190150209 , МР 1106533.

[1] Дистель стр.5

[10.1016/j.physa.2014.11.062-2] Ciotti В (2015). «Степенные корреляции в подписанных социальных сетях» . Physica A: Статистическая механика и ее приложения . arXiv : 1412.1024 . DOI : 10.1016 / j.physa.2014.11.062 .

[10.1038/s41598-021-81767-7-3] Сабери М, Khosrowabadi R, Хатиби А, Мисич В, С Джафари (январь 2021 года). «Топологическое влияние отрицательных связей на стабильность сети мозга в состоянии покоя» . Научные отчеты . DOI : 10.1038 / s41598-021-81767-7 . PMC 7838299 . PMID 33500525 .

[4] Diestel p.216

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

[1]