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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
== Неориентированный граф ==
 
== Неориентированный граф ==
  

Текущая версия на 19:20, 4 сентября 2022

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

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

Например, для следующего графа выполнено: [math]deg(1)+\ldots+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] n [/math] вершинами ровно [math]\frac{k\cdot n}{2} [/math] рёбер.


Утверждение:
Если степень каждой вершины нечётна и равна [math] k[/math], то количество рёбер кратно [math] k [/math].
[math]\triangleright[/math]
Регулярный граф с [math]\frac{k\cdot n}{2} = \frac{3\cdot 6}{2}=9 [/math] рёбрами
Действительно, так как степень каждой вершины нечётна, то число вершин в графе чётно(так сумма степеней всех вершин чётна). Пусть [math] n = 2\cdot r [/math], то равенство принимает вид [math]|E| =\frac{k\cdot n}{2} = \frac{2\cdot k\cdot r}{2}=k\cdot r [/math], то есть количество рёбер кратно [math] k[/math].
[math]\triangleleft[/math]

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