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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма о рукопожатиях)
Строка 2: Строка 2:
 
== Лемма о рукопожатиях ==
 
== Лемма о рукопожатиях ==
 
==== Неориентированный граф ====
 
==== Неориентированный граф ====
 +
 +
 
{{Лемма
 
{{Лемма
 
|statement=
 
|statement=
Строка 8: Строка 10:
  
 
|proof=
 
|proof=
 +
[[Файл:undir_grap.png|thumb|300px| <tex>deg(1)+...+deg(6)=16=2|E|</tex>]]
 
Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.
 
Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.
}}
 
  
<br />
+
 
  
 
''Следствие 1''
 
''Следствие 1''
 
В любом графе число вершин нечетной степени четно
 
В любом графе число вершин нечетной степени четно
  
''Следствие 2''
+
''Следствие 2'' Число ребер в полном графе <tex>\frac{n(n-1)}{2} </tex>
Число ребер в полном графе <tex>\frac{n(n-1)}{2} </tex>
 
  
 +
}}
 +
<br />
 
==== Ориентированный граф ====
 
==== Ориентированный граф ====
  

Версия 14:57, 9 декабря 2012

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

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

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

Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.


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

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


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

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

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

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

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

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

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

В графе с [math] n [/math] вершинами, степени которых равны [math] k[/math] (регулярный граф), ровно [math]\frac{kn}{2} [/math] ребер.

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

Источники