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

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

Следствие 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. Представление (способы задания) графов.

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

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

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

Получается путём расположения различных точек на плоскости для каждой вершины 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.

04. Степень вершины графа

Рассмотрим граф , Имеющий P вершин и Q ребер.

Определение. Степенью вершины графа называется число ребер, инцидентных этой вершине .

Теорема.5. Степень любой вершины графа удовлетворяет неравенству .

Определение. Изолированной называется такая вершина графа, степень которой .

Определение. Концевой, или висячей, называется такая вершина графа, степень которой .

Теорема 6. (Теорема Эйлера.) Сумма степеней всех вершин графа равна удвоенному числу его рёбер: .

Например, для графа на рис. 1 степени его вершин , , , . Изолированных и концевых вершин в графе нет. Число ребер графа . По теореме Эйлера .

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

Название леммы интерпретируется так: вершины графа – это люди, а ребра – рукопожатия двух людей. При Любом числе рукопожатий общее число пожатых рук всегда чётное.

Задачи и упражнения

12. Определите степени вершин графа задачи 1. Укажите концевые и изолированные вершины.

13. В здании имеется 15 телефонных аппаратов. Докажите, что их нельзя соединить проводами так, чтобы каждый аппарат был соединен ровно с пятью другими.

14. В некотором государстве имеется 100 городов. Каждый город соединяется дорогами с пятью другими городами. Установите, сколько всего дорог в этом государстве.

15. На втором курсе института обучаются 253 студента. Одни из них знакомы, другие – не знакомы друг с другом. Докажите, что хотя бы у одного студента имеется чётное число знакомых среди студентов второго курса.

16. Для графа сформулируйте свойство вершин нечетной степени.

• Главная
• Заказать работу
• Стоимость решения
• Варианты оплаты
• Ответы на вопросы (FAQ)
• Отзывы о нас
• Примеры решения задач
• Методички по математике
• Помощь по всем предметам
• Заработок для студентов

Теория: 03 Свойство суммы степеней вершин, сравнение графов

Для графа, изображенного на рисунке, определите степени вершин. Найдите сумму степеней вершин.

Сколько рёбер в данном графе?

Во сколько раз сумма степеней вершин больше количества рёбер?

Вершина	Степень вершины
\(\displaystyle \bf A\)
\(\displaystyle \bf B\)
\(\displaystyle \bf C\)
\(\displaystyle \bf D\)
\(\displaystyle \bf E\)
Сумма степеней

Граф содержит рёбер.

Сумма степеней вершин больше количества рёбер в раз(а).

Требуется найти степени всех вершин графа, сумму степеней, количество рёбер и ответить на вопрос, во сколько раз сумма степеней вершин больше количества рёбер.

Определение

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

Шаг 1. Определим по рисунку степени вершин графа и найдём сумму степеней вершин.

Степень вершины \(\displaystyle A\) равна \(\displaystyle \color\)

Видим, что из вершины \(\displaystyle A\) исходят \(\displaystyle \color\) ребра.

Степень вершины \(\displaystyle B\) равна \(\displaystyle \color\)

Видим, что из вершины \(\displaystyle B\) исходят \(\displaystyle \color\) ребра.

Степень вершины \(\displaystyle C\) равна \(\displaystyle \color\)

Из вершины \(\displaystyle C\) исходит \(\displaystyle \color\) ребро.

Степень вершины \(\displaystyle D\) равна \(\displaystyle \color\)

Из вершины \(\displaystyle D\) исходят \(\displaystyle \color\) ребра.

Степень вершины \(\displaystyle E\) равна \(\displaystyle \color\)

Из вершины \(\displaystyle E\) исходят \(\displaystyle \color\) ребра.

Сумма степеней вершин:

Вершина	Степень вершины
\(\displaystyle \bf A\)	\(\displaystyle 2\)
\(\displaystyle \bf B\)	\(\displaystyle 2\)
\(\displaystyle \bf C\)	\(\displaystyle 1\)
\(\displaystyle \bf D\)	\(\displaystyle 3\)
\(\displaystyle \bf E\)	\(\displaystyle 2\)
Сумма степеней	\(\displaystyle \color\)

Шаг 2. Определим количество рёбер графа.

Граф содержит \(\displaystyle \color\) рёбер.

Можем просто перечислить эти рёбра: \(\displaystyle A-B\,A-D\,B-E\,D-E\) и \(\displaystyle C-D\)

Шаг 3. Вычислим, во сколько раз сумма степеней вершин больше количества рёбер.

Таким образом, сумма степеней вершин графа больше количества его рёбер в \(\displaystyle 2\) раза.

Замечание / комментарий

Заметим, что каждое ребро графа имеет начало и конец. Значит, при подсчёте степеней вершин каждое ребро подсчитано дважды: для вершины, являющейся началом ребра, и для вершины, являющейся его концом.

Таким образом, будет верна теорема

Теорема

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