В теории графов , то степень (или валентность ) из вершины в виде графа является числом ребер , которые падающие к вершине; в мультиграфе , А цикл способствует от 2 до степени вершины, в течение двух концов ребра. [1] Степень вершины обозначается или же . Максимальная степень графа, обозначаемый , и минимальная степень графа, обозначаемая, - максимальная и минимальная степени его вершин. В мультиграфе, показанном справа, максимальная степень равна 5, а минимальная - 0.
В регулярном графе , каждая вершина имеет ту же степень, и поэтому мы можем говорить о о степени графа. Полный граф (обозначается, где количество вершин в графе) - это особый вид регулярного графа, в котором все вершины имеют максимальную степень, .
В подписанном графе количество положительных ребер, соединенных с вершинойназывается положительным градусома количество связанных отрицательных ребер называется отрицательным градусом. [2] [3]
Лемма о рукопожатии
Формула суммы степеней утверждает, что, учитывая график,
- .
Из формулы следует, что в любом неориентированном графе число вершин нечетной степени четно. Это утверждение (как и формула суммы степеней) известно как лемма о рукопожатии . Последнее название происходит от популярной математической задачи, которая состоит в том, чтобы доказать, что в любой группе людей количество людей, которые пожали руку нечетному количеству других людей из группы, является четным.
Последовательность степеней
Последовательность степеней неориентированного графа - это невозрастающая последовательность степеней его вершин; [4] для приведенного выше графика это (5, 3, 3, 2, 2, 1, 0). Последовательность степеней является инвариантом графа , поэтому изоморфные графы имеют одинаковую последовательность степеней. Однако последовательность степеней, как правило, не однозначно идентифицирует граф; в некоторых случаях неизоморфные графы имеют одинаковую последовательность степеней.
Проблема последовательности степеней - это проблема поиска некоторых или всех графов, в которых последовательность степеней является заданной невозрастающей последовательностью положительных целых чисел. (Конечные нули можно игнорировать, поскольку они тривиально реализуются путем добавления соответствующего числа изолированных вершин к графу.) Последовательность, которая является последовательностью степеней некоторого графа, т. Е. Для которой проблема последовательности степеней имеет решение, называется графической. или графическая последовательность . Как следствие формулы суммы степеней, любая последовательность с нечетной суммой, такая как (3, 3, 1), не может быть реализована как последовательность степеней графа. Верно и обратное: если последовательность имеет четную сумму, это последовательность степеней мультиграфа. Построение такого графа несложно: соедините вершины с нечетными степенями попарно (образуя соответствие ) и заполните оставшиеся четные числа степеней с помощью петель. Вопрос о том, может ли данная последовательность степеней быть реализована простым графом, является более сложным. Эта проблема также называется проблемой реализации графа и может быть решена либо с помощью теоремы Эрдеша – Галлаи, либо с помощью алгоритма Гавела – Хакими . Проблема поиска или оценки количества графов с заданной последовательностью степеней является проблемой из области перечисления графов .
В целом, последовательность степени из гиперграфа является не возрастающей последовательностью его степеней вершин. Последовательность-графическая, если это последовательность степеней некоторого-равномерный гиперграф. В частности,-графическая последовательность графическая. Определение того, является ли данная последовательность-graphic выполняется за полиномиальное время дляпо теореме Эрдеша – Галлаи, но NP-полна для всех(Deza et al., 2018 [5] ).
Особые ценности
- Вершина степени 0 называется изолированной вершиной .
- Вершина со степенью 1 называется листовой или конечной вершиной, а ребро, инцидентное этой вершине, называется висячим ребром. На графике справа {3,5} - висячий край. Эта терминология распространена при изучении деревьев в теории графов и особенно деревьев как структур данных .
- Вершина степени n - 1 в графе из n вершин называется доминирующей вершиной .
Глобальные свойства
- Если каждая вершина графа имеет одинаковую степень k , граф называется k -регулярным графом, а сам граф имеет степень k . Точно так же двудольный граф, в котором каждые две вершины на одной стороне двудольного деления имеют одинаковую степень, называется бирегулярным графом .
- Неориентированный связный граф имеет эйлеров путь тогда и только тогда, когда он имеет 0 или 2 вершины нечетной степени. Если он имеет 0 вершин нечетной степени, эйлеров путь является эйлеровым контуром.
- Ориентированный граф является направленным псевдолесом тогда и только тогда, когда каждая вершина имеет исходную степень не выше 1. Функциональный граф - это частный случай псевдолеса, в котором каждая вершина имеет исходную степень ровно 1.
- По теореме Брукса любой граф G, кроме клики или нечетного цикла, имеет хроматическое число не более Δ ( G ), а по теореме Визинга любой граф имеет хроматический индекс не более Δ ( G ) + 1.
- К -degenerate график представляет собой график , в котором каждый подграф имеет вершину степени по большей к .
Смотрите также
Заметки
- ^ Diestel, стр. 5, 28
- ^ Ciotti В (2015). «Степенные корреляции в подписанных социальных сетях» . Physica A: Статистическая механика и ее приложения . arXiv : 1412.1024 . DOI : 10.1016 / j.physa.2014.11.062 .
- ^ Сабери М., Хосровабади Р., Хатиби А., Мисич Б., Джафари Г. (январь 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.