Лемма о рукопожатиях: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Лемма о рукопожатиях''' (''Handshake's lemma'') - ''Сумма степеней всех вершин графа ---...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Лемма о рукопожатиях''' (''Handshake's lemma'') - | '''Лемма о рукопожатиях''' (''[[Handshake's lemma]]'') - | ||
''Сумма степеней всех вершин графа --- четное число, равное удвоенному числу ребер''. | ''Сумма [[степень вершины|степеней]] всех [[вершина|вершин]] [[граф|графа]] --- четное число, равное удвоенному числу [[ребро|ребер]]''. | ||
Свое название лемма получила из-за следующей интерпретации: поскольку | Свое название лемма получила из-за следующей интерпретации: поскольку | ||
| Строка 6: | Строка 6: | ||
рукопожатий общее число пожатых рук (при этом каждая рука учитывается | рукопожатий общее число пожатых рук (при этом каждая рука учитывается | ||
столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма | столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма | ||
справедлива также для мульти- и псевдографов. | справедлива также для [[мультиграф|мульти-]] и [[псевдограф|псевдографов]]. | ||
==Литература== | ==Литература== | ||
[Лекции] | [Лекции] | ||
Версия от 18:44, 18 ноября 2009
Лемма о рукопожатиях (Handshake's lemma) - Сумма степеней всех вершин графа --- четное число, равное удвоенному числу ребер.
Свое название лемма получила из-за следующей интерпретации: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма справедлива также для мульти- и псевдографов.
Литература
[Лекции]