Как найти сумму степеней вершин графа

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)

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

Undir grap.png

Следствие 1. В любом графе число вершин нечётной степени чётно.

Следствие 2. Число рёбер в полном графе [math]\frac [/math] .

Ориентированный граф

Сумма входящих и исходящих степеней всех вершин ориентированного графа — чётное число, равное удвоенному числу рёбер:
[math]\sum\limits_ deg^\ v \; + \sum\limits_ deg^\ v=2\cdot |E(G)| [/math]

[math]deg^<->+deg^=10=2\cdot |E|[/math]

Аналогично доказательству леммы о рукопожатиях неориентированном графе.

Бесконечный граф

Пример бесконечного графа, в котором не выполняется лемма

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

При выборе бесконечного пути из вершины [math] V [/math] (см. рисунок справа) имеем путь, в котором все вершины кроме стартовой имеют чётную степень, что противоречит следствию из леммы.

Регулярный граф

Определение:

Граф называется регулярным, если степени всех его вершин равны.

Утверждение:

В регулярном графе с [math] n [/math] вершинами ровно [math]\frac [/math] рёбер.

Если степень каждой вершины нечётна и равна [math] k[/math] , то количество рёбер кратно [math] k [/math] .

Регулярный граф с [math]\frac = \frac=9 [/math] рёбрами

Источники информации

Lecture Notes on Graph Theory By Tero Harju, Department of Mathematics University of Turku, 2011 — с. 7-8
Handshaking lemma — Wikipedia

7.4. Степень вершин.

Определение 7.10. Степенью вершины v для неориентированного графа, обозначается d(v), называется количество ребер, инцидентных этой вершине. Вершина степени 0 называется изолированной. Вершина степени 1 называется висячей. Определение 7.11. Полустепенью исхода вершины v для орграфа называется количество дуг, для которых v является начальной вершиной, обозначается . Полустепенью захода вершины v называется количество дуг, для которых v является конечной вершиной, обозначается . Если, то вершинаv называется истоком. Если , то вершинаv называется стоком. Теорема 7.2. (Теорема Эйлера) Сумма степеней вершин графа равна удвоенному количеству ребер: . Доказательство. При подсчете суммы степеней вершин каждое ребро учитывается два раза: для одного конца ребра и для другого. Следствие 1. Число вершин нечетной степени четно. Доказательство. По теореме Эйлера сумма степеней всех вершин – четное число. Сумма степеней вершин четной степени четна, значит, сумма степеней вершин нечетной степени также четна, следовательно, их четное число. Следствие 2. Сумма полустепеней вершин орграфа равна удвоенному количеству дуг: . Доказательство. Сумма полустепеней вершин орграфа равна сумме степеней вершин графа, полученного из орграфа забыванием ориентации дуг. Пример 7.5. Определить степени вершин данного графа. Пример 7.6. Определить полустепени исхода и захода данного орграфа.

7.5. Представление (способы задания) графов.

Граф как алгебраическая система:

модель, носителем которой является множество вершин, а отношение – бинарное отношение смежности вершин. < a,b,c,d>; — множество вершин <(a,b),(b,a),(b,c),(c,b),(a,c),(c,a),(c,d),(d,c)> – множество рёбер >

Геометрический

Получается путём расположения различных точек на плоскости для каждой вершины vÎV, причём если (v₁,v₂)ÎЕ, то проводится ребро (дуга) из v₁ в v₂. Для представления в компьютере чаще всего граф задается либо матрицей смежности, либо матрицей инциденций. Матрицей смежности вершин неориентированного графаG, содержащего n вершин, называют квадратную матрицу A=a_ij n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам неориентированного графа. Элементы a_ij матрицы A равны числу ребер, направленных из i-й вершины в j-ю. В случае неориентированного графаG ему вместе с ребром (v_i, v_j) принадлежит и ребро (v_j, v_i), поэтому матрица смежности вершин A=a_ij будет симметрична относительно главной диагонали. ПРИМЕР. Граф: множество вершин V = Множество ребер Е = , , , , , >, Матрица смежности симметрична относительно главной диагонали. На главной диагонали стоит 1 (символ Л) из-за нерефлексивности отношения на множестве вершин (EÍV´V) Логическая матрица отношения на множестве вершин графа, которое задается его ребрами. abcd a 0 1 0 1 b 1 0 1 1 с 0 1 0 1 d 1 1 1 0 простой граф abcd a 1 1 0 1 b 1 0 3 0 c 0 3 0 2 d 1 0 2 0 граф с кратными рёбрами и петлёй Определение 7.12.Матрица смежности вершин орграфаG, содержащего n вершин- это квадратная матрица A=a_ij n-го порядка, у которой строки и столбцы матрицы соответствуют вершинам орграфа. Элементы a_ij матрицы A равны числу дуг, направленных из i-й вершины в j-ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1. Матрица смежности: Пусть дан граф G, его матрица смежности А = [a_ij] определяется следующим образом: a_ij= 1 если вGсуществует дуга (x_i, x_j)a_ij= 0 если вGнет дуги (x_i, x_j)Определение 7.14.Матрицей инциденций (инцидентности) неориентированного графа с вершинамии ребрами называется матрица размерности, строки которой соответствуют вершинам, а столбцы – ребрам. Элементыматрицы инциденций неориентированного графа равны 1, если вершинаинцидентна ребру, и 0 в противном случае. Матрицей инциденций (инцидентности) орграфа с вершинамии дугами называется матрица размерностиnm, строки которой соответствуют вершинам, а столбцы -дугам орграфа. Элементы c_ij равны 1, если дуга e_j исходит из i-й вершины; –1, если дуга e_j заходит в i-ю вершину; 0, если дуга не инцидентна i-й вершине Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один – равный –1, либо все элементы столбца равны 0. Степень вершины равна сумме элементов строки, обозначенной этой вершиной, так как каждая единица в этой строке представляет инцидентность этой вершины ребру. В каждом столбце также будут две единицы, так как каждое ребро инцидентно двум вершинам. Матрицы инцидентности не имеют большого значения при рассмотрении ориентированных графов, т.к. они не содержат информации о том, как ребро ориентировано. Поэтому, используя матрицу инцидентности, нельзя восстановить ориентированный граф. Такую возможность обеспечивает матрица смежности, Пример7.7.1. Для заданного неориентированного графа построить матрицы смежностей и матрицу инциденций. Решение. 1) Строим матрицу смежности вершин, которая будет размерности 44. Строим матрицу смежности ребер, которая будет размерности 55. 2) Строим матрицу инциденций, которая будет размерности 45. Пример7.7.2. Для заданного ориентированного графа построить матрицы смежностей и матрицу инциденций. Решение. 1) Строим матрицу смежности вершин, которая будет размерности 44. Строим матрицу смежности ребер, которая будет размерности 55. 2) Строим матрицу инциденций, которая будет размерности 45.