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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Лемма о рукопожатиях для ориентированного графа)
(Лемма о рукопожатиях для ориентированного графа)
Строка 23: Строка 23:
 
|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 \plus \sum\limits_{v\in V(G)} deg_{+}\ v = 2 |E(G)| </tex>
  
 
|proof=
 
|proof=
 
Аналогично доказательству о неориентированном графе.
 
Аналогично доказательству о неориентированном графе.
 
}}
 
}}

Версия 23:14, 13 октября 2010

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

Лемма о рукопожатиях для неориентированного графа

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


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

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

Лемма о рукопожатиях для ориентированного графа

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