105
правок
Изменения
м
ё
== Неориентированный граф ==
{{Лемма
|statement=
Сумма степеней всех вершин графа (или мультиграфа без петель) — четное чётное число, равное удвоенному числу реберрёбер:
<br /> <tex> \sum\limits_{v\in V(G)} deg\ v=2\cdot|E(G)|</tex>
|proof=
Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна чётна и равна удвоенному числу реберрёбер.
}}
Например, для следующего графа выполнено: <tex>deg(1)+\ldots+deg(6)=16=2\cdot|E|</tex>
[[Файл:undir_grap.png]]
'''Следствие 1.''' В любом графе число вершин нечетной нечётной степени четночётно.
'''Следствие 2.''' Число ребер рёбер в полном графе <tex dpi=150>\frac{n\cdot(n-1)}{2} </tex>.
<br />
{{Лемма
|statement=
Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное чётное число, равное удвоенному числу реберрёбер:
<br /> <tex>\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2\cdot |E(G)| </tex>
[[Файл:dir_grap.png|thumb|300px| <tex>deg^{-}+deg^{+}=10=2\cdot |E|</tex>]]
Аналогично доказательству леммы о рукопожатиях неориентированном графе.
То есть возьмем пустой граф и будем добавлять в него ребрарёбра. При этом каждое добавление ребра увеличивает на единицу сумму входящих и на единицу сумму исходящих степеней. Таким образом, сумма входящих и исходящих степеней всех вершин ориентированного графа четна чётна и равна удвоенному числу реберрёбер.
}}
[[Файл:inf_grap.png|thumb|300px|right|Пример бесконечного графа, в котором не выполняется лемма]]
В бесконечном графе лемма не работает, даже в случае с конечным числом вершин нечетной нечётной степени. Покажем это на примере.
При выборе бесконечного пути из вершины <tex> V </tex> (см. рисунок справа) имеем путь, в котором все вершины кроме стартовой имеют четную чётную степень, что противоречит следствию из леммы.
== Регулярный граф ==
{{Утверждение
|statement=
В регулярном графе с <tex> n </tex> вершинами ровно <tex dpi=150>\frac{k\cdot n}{2} </tex> реберрёбер.
}}
{{Утверждение
|statement=Если степень каждой вершины нечетна нечётна и равна <tex> k</tex>, то количество ребер рёбер кратно <tex> k </tex>.|proof= [[Файл:reg_grap.png|thumb|300px|right|Регулярный граф с <tex dpi=140>\frac{k\cdot n}{2} = \frac{3\cdot 6}{2}=9 </tex> ребрами рёбрами ]]Действительно, так как степень каждой вершины нечетнанечётна, то число вершин в графе четночётно(так сумма степеней всех вершин четначётна). Пусть <tex> n = 2\cdot r </tex>, то равенство принимает вид <tex dpi=150>|E| =\frac{k\cdot n}{2} = \frac{2\cdot k\cdot r}{2}=k\cdot r </tex>, то есть количество ребер рёбер кратно <tex> k</tex>.
}}
