Как найти степень вершины графа

1. Основные понятия

В работе с графами важно понимать не только что такое вершина и её степень, но и к какому виду эта вершина относится.

Вспомним правило.
Степенью (или порядком) вершины называется количество рёбер, которые выходят из этой вершины.
Каждую вершину графа можно отнести к одному из двух видов вершин.
Вершина графа называется чётной, если её степень чётна, и нечётной, если её степень нечётна.

Например, на рисунке \(1\) вершины A, D — чётные, так как имеют степени \(2\) и \(4\) соответственно, а вершины B, C, E, K, N, F — нечётные, так как вершины B, E, K, N, F имеют степень \(1\), а вершина C — степень \(3\).

В прошлой теме мы, исходя из примеров, сформулировали и применяли для решения задач правило нахождения количества вершин, часто это правило называют леммой о рукопожатиях . Сформулируем его ещё раз.

Лемма о рукопожатиях.
Сумма степеней всех вершин графа равна удвоенному количеству рёбер.

Важную роль играет и следствие из леммы о рукопожатиях, оно позволяет определять, существует ли граф, если известно только количество нечётных вершин в графе.

Расчёт степени вершин

Для неорграфа степень вершин — это количество рёбер, входящих или исходящих из вершины.

Для орграфа сервис будет считать количество рёбер, исходящих из вершины.

Для использования алгоритма выберите пункт меню Алгоритмы -> Рассчитать степень вершин

Степень вершин будет написана над каждой вершиной. Вершины одинаковой степени будут одинакового цвета.

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

Как найти степень вершины графа

Вершины в графе могут отличаться друг от друга тем, скольким ребрам они принадлежат.
Степенью вершины называется число ребер графа, которым принадлежит эта вершина.
Обозначать степени вершин А, В, Сбудем соответственно так: d(А), d(В), d(С) и т. п.
Задача 2.1.
а) Найдите степени вершин А, В, С и D.
Ответ: степ.А=1; степ.В=2; степ.С=1; степ.D=2.

б) Чему равна степень каждой вершины?
Ответ: 2
в) Чему равна степень каждой вершины?
Ответ: 0.
Степень изолированной вершины равна 0.
Вершина называется нечетной,если ее степень — число не­
четное. Вершина называется четной,если ее степень — число
четное.
Задача 2.2. Уезжая из летнего лагеря, подружившиеся ребята обменялись конвертами с адресами. Докажите, что
а) всего было передано четное число конвертов;
б) число участников, обменявшихся конвертами нечетное чис­ло раз, четное.
Решение. Пусть участники слета А1, А2, A3. Ап — вершины графа, а ребра соединяют на рисунке 15 пары вершин, изобра­жающих ребят, обменявшихся конвертами:
рис. 15
а) степень каждой вершины Ai показывает число конвертов, которые передал участник Аi своим знакомым. Общее число переданных кон­вертов N равно сумме степеней всех вершин графа. N = степ. А1+степ. А2+. +степ. Ап-1+ степ. Ап, но N = 2р, где р — число ре­бер графа, то есть N — четное. Следовательно, было передано четное число конвертов.
б) в равенстве N = степ. А1 + степ. А2 + . + степ. Ап-1 + степ. Ап сумма нечетных слагаемых должна быть четной, а это может быть только в том случае, если число нечетных слагаемых четно. А это означает, что число участников, обменявшихся кон­вертами нечетное число раз, четное.
В ходе решения задачи 1 доказаны два свойства.
Свойство 1. В графе G сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа.
степ. А1 + степ. А2+ . + степ. Аn = 2р,
где р — число ребер графа Г, n — число его вершин.
Свойство 2. Число нечетных вершин любого графа четно.
Задача 2.3. Девять шахматистов проводят турнир в один круг (каждый из участников должен сыграть с каждым из осталь­ных по одному разу). Покажите, что в любой момент найдутся двое, закончившие одинаковое число партий.
Решение. Переведем условие задачи на язык графов. Каж­дому из шахматистов поставим в соответствие вершину графа, со­единим ребрами попарно вершины, соответствующие шахматистам, уже сыгравшим между собой партию. Получим граф с девятью вер­шинами. Степени его вершин равняются числу партий, сыгранных соответствующими игроками. Покажем, что во всяком графе с де­вятью вершинами всегда найдутся хотя бы две вершины одинаковой степени.
Каждая вершина графа с девятью вершинами может иметь сте­пень, равную 0, 1, 2, . 7, 8. Предположим, что существует граф G, все вершины которого имеют разную степень, т. е. каждое из чисел последовательности 0, 1, 2, . 7, 8 является степенью одной и только одной из его вершин. Но этого не может быть. Действитель­но, если в графе есть вершина Астепени 0, то в нем не найдется вер­шина Всо степенью 8, так как эта вершина В должна быть соедине­на ребрами со всеми остальными вершинами графа, в том числе и с А. Иначе говоря, в графе с девятью вершинами не могут быть одновременно вершины степени 0 и 8. Следовательно, найдутся хотя бы две вершины, степени которых равны между собой.
Вернемся к задаче. Доказано, что в любой момент найдутся хотя бы двое, сыгравшие одинаковое число партий.
Решение этой задачи почти дословно повторяется в ходе дока­зательства следующего свойства (только число 9 приходится заменить произвольным натуральным числом n ? 2).
Свойство 3. Во всяком графе с n вершинами, где n ? 2, всегда найдутся, по меньшей мере, две вершины с одинаковыми сте­пенями.
Задача 2.4. Девять человек проводят шахматный турнир в один круг. К некоторому моменту выясняется, что в точности двое сыграли одинаковое число партий. Докажите, что тогда либо в точности один участник еще не сыграл ни одной партии, либо в точности один сыграл все партии.
Решение: Условие задачи переведем на язык графов. Пусть вершины графа — игроки, а каждое ребро означает, что соответ­ствующие игроки уже сыграли между собой партию. Из условия известно, что в точности две вершины имеют одинаковые степе­ни. Требуется доказать, что в таком графе всегда найдется либо только одна изолированная вершина, либо только одна вершина степени 8.
В общем случае у графа с девятью вершинами степень каждой вершины может принимать одно из девяти значений: 0, 1, 2, . 7, 8. Но у такого графа степени вершин принимают только восемь разных значений, ибо ровно две вершины имеют одинако­вую степень. Следовательно, обязательно либо 0, либо 8 будет значением степени одной из вершин.
Докажем, что в графах с девятью вершинами, из которых в точности две имеют одинаковую степень, не может быть двух вершинстепени 0 или двух вершин степени 8. Допустим, что все же найдется граф с девятью вершинами, в котором ровно две вершины изолированные, а все остальные имеют разные между собой степени. Тогда, если не рассматривать эти две изолированные вершины, останется граф с семью вершинами, степени которых не совпадают. Но такого графа не существует (см. свойство 3). Значит, это предположение неверное.
Теперь допустим, что существует граф с девятью вершинами, в котором ровно две вершины имеют степень 8, а все остальные — несовпадающие степени. Тогда в дополнении данного графа ровно две вершины будут иметь степень 0, а остальные попарно различ­ные степени. Этого тоже не может быть (свойство 3), т. е. и второе предположение неверное.
Следовательно, у графа с девятью вершинами, из которых в точности две имеют одинаковую степень, всегда найдется либо одна изолированная вершина, либо одна вершина степени 8.
Вернемся к задаче. Как и требовалось доказать, среди рассмот­ренных девяти игроков либо только один еще не сыграл ни одной партии, либо только один сыграл уже все партии.
При решении этой задачи число 9 можно было заменить любым другим натуральным числом n > 2.
Это решение поможет вам провести доказательство следующего свойства:

Свойство 4. Если в графе с n вершинами (n > 2) в точно­сти две вершины имеют одинаковую степень, то в этом графе всег­да найдется либо в точности одна вершина степени 0, либо в точ­ности одна вершина степени n — 1.

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

Степень вершины (англ. degree , также валентность, англ. valency ) в теории графов — количество рёбер графа , инцидентных вершине . При подсчёте степени ребро-петля учитывается дважды. [1] Степень вершины обозначается как (в западных источниках — ). Максимальная и минимальная степень вершин графа G обозначаются соответственно Δ(G) и δ(G). На рис. 1 максимальная степень равна 5, минимальная — 0. В регулярном графе степени всех вершин одинаковы, поэтому в данном случае можно говорить о степени графа.

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

Основная статья: Лемма о рукопожатиях

По формуле суммы степеней для графа ,

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

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

Проблема последовательности степеней заключается в нахождении некоторых или всех графов с заданной невозрастающей последовательностью, состоящей из натуральных чисел (нулевые степени при этом могут быть проигнорированы, так как их количество изменяется добавлением или удалением изолированных вершин). Последовательность, являющаяся последовательностью степеней какого-либо графа, называется графической (англ. graphical sequence ). Из формулы суммы степеней следует, что любая последовательность с нечётной суммой (как, к примеру, 3, 3, 1) не может быть последовательностью степеней графа. Обратное также верно: если последовательность имеет чётную сумму, она представляет собой последовательность степеней мультиграфа. Построение такого графа осуществляется достаточно простым способом: необходимо объединить вершины нечётных степеней в пары, к оставшимся незаполненными вершинам следует добавить петли.

Сложнее реализовать простой граф с заданной последовательностью. Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность d_i (при i = 1,…,n) может быть последовательностью простого графа только если её сумма чётна и выполняется неравенство

Рис. 3. Концевыми вершинами являются 4, 5, 6, 7, 10, 11 и 12.

• Вершина степени 0 называется изолированной.
• Вершина степени 1 называется концевой (англ.end vertex ), висячей (англ.pendant vertex ) или листом графа (англ.leaf vertex ). Ребро, инцидентное такой вершине называется висячим (англ.terminal (pendant) edge, end-edge ). На рис. 3 висячим ребром является . Подобная терминология используется в изучении деревьев в общем и как структур данных.
• Вершина степени n-1 графа порядка n называется доминирующей (англ.dominating vertex ).

Общие свойства

• Если все вершины графа имеют одинаковую степень k, граф называют k-регулярным или регулярным графом степени k. В этом случае сам граф имеет степень k.
• Эйлеров путь существует в неориентированном, связном графе если и только если граф имеет 0 или 2 вершины нечётной степени. Если граф содержит 0 вершин нечётной степени, Эйлеров путь является циклом.
• Орграф является псевдолесом только если полустепень захода каждой вершины не больше 1. Функциональный граф — частный случай псевдолеса, в котором полустепени захода всех вершин равны 1.
• Согласно теореме Брукса, хроматическое число любого графа за исключением клики или нечётного цикла не превышает максимальной степени его вершин (Δ). Согласно теореме Визинга, хроматический индекс любого графа не превышает Δ + 1.
• k-вырожденным графом называется граф, в котором каждый подграф имеет вершину степенью не больше k.

См. также

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

Примечания

Источники

• Дистель, Рейнхард (2005), «Graph Theory» (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4 , .
• Эрдёш, П. & Галлаи, T. (1960), ««Gráfok előírt fokszámú pontokkal»», Matematikai Lapok Т. 11: 264—274 , .
• Хакими, С. Л. (1962), ««On realizability of a set of integers as degrees of the vertices of a linear graph. I»», Journal of the Society for Industrial and Applied Mathematics Т. 10: 496–506 .
• Сирксма, Хирард & Хоохефен, Хан (1991), ««Seven criteria for integer sequences being graphic»», Journal of Graph Theory Т. 15 (2): 223–231 , DOI 10.1002/jgt.3190150209 .

• Теория графов

Wikimedia Foundation . 2010 .