Лемма о рукопожатиях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Неориентированный граф)
(Ориентированный граф)
Строка 26: Строка 26:
 
|statement=
 
|statement=
 
Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное число, равное удвоенному числу ребер:
 
Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное число, равное удвоенному числу ребер:
<br /> <tex>\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2 |E(G)| </tex>
+
<br /> <tex>\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2\cdot|E(G)| </tex>
  
 
|proof=
 
|proof=
[[Файл:dir_grap.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2|E|</tex>]]
+
[[Файл:dir_grap.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2\cdot|E|</tex>]]
 
Аналогично доказательству леммы о рукопожатиях неориентированном графе.  
 
Аналогично доказательству леммы о рукопожатиях неориентированном графе.  
 
То есть возьмем пустой граф и будем добавлять в него ребра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа четна и равна удвоенному числу ребер.
 
То есть возьмем пустой граф и будем добавлять в него ребра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа четна и равна удвоенному числу ребер.
 
}}
 
}}
 +
 
==== Бесконечный граф ====
 
==== Бесконечный граф ====
 
[[Файл:inf_grap.png|thumb|300px|right|Пример бесконечного графа, в котором не выполняется лемма]]
 
[[Файл:inf_grap.png|thumb|300px|right|Пример бесконечного графа, в котором не выполняется лемма]]

Версия 17:13, 16 сентября 2015

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

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

Лемма:
Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер:
[math] \sum\limits_{v\in V(G)} deg\ v=2\cdot|E(G)|[/math]
Доказательство:
[math]\triangleright[/math]
Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.
[math]\triangleleft[/math]

Например, для следующего графа выполнено: [math]deg(1)+...+deg(6)=16=2\cdot|E|[/math]

Undir grap.png

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

Следствие 2. Число ребер в полном графе [math]\frac{n\cdot(n-1)}{2} [/math].


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

Лемма:
Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное число, равное удвоенному числу ребер:
[math]\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2\cdot|E(G)| [/math]
Доказательство:
[math]\triangleright[/math]
[math]deg^{-}+deg^{+}=10=2\cdot|E|[/math]

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

То есть возьмем пустой граф и будем добавлять в него ребра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа четна и равна удвоенному числу ребер.
[math]\triangleleft[/math]

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

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

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

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

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

Определение:
Граф называется регулярным, если степени всех его вершин равны.
Регулярный граф с [math]\frac{kn}{2} = \frac{3*6}{2}=9 [/math] ребрами

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

Следствие.

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

Доказательство.

Действительно, так как степень каждой вершины нечетна, то число вершин в графе четно(так сумма степеней всех вершин четна). Пусть [math] n = 2r [/math], то равенство принимает вид [math]|E| =\frac{kn}{2} = \frac{2kr}{2}=kr [/math], то есть количество ребер кратно [math] k[/math].

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