Лемма о рукопожатиях: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Создана новая страница размером '''Лемма о рукопожатиях''' (''Handshake's lemma'') - ''Сумма степеней всех вершин графа ---...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| (не показана 1 промежуточная версия этого же участника) | |||
| Строка 1: | Строка 1: | ||
'''Лемма о рукопожатиях''' (''Handshake's lemma'') | '''Лемма о рукопожатиях''' (''[[Handshake's lemma]]'') — | ||
''Сумма степеней всех вершин графа | ''Сумма [[степень вершины|степеней]] всех [[вершина|вершин]] [[граф|графа]] — четное число, равное удвоенному числу [[ребро|ребер]]''. | ||
Свое название лемма получила из-за следующей интерпретации: поскольку | Свое название лемма получила из-за следующей интерпретации: поскольку | ||
| Строка 6: | Строка 6: | ||
рукопожатий общее число пожатых рук (при этом каждая рука учитывается | рукопожатий общее число пожатых рук (при этом каждая рука учитывается | ||
столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма | столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма | ||
справедлива также для мульти- и псевдографов. | справедлива также для [[мультиграф|мульти-]] и [[псевдограф|псевдографов]]. | ||
==Литература== | ==Литература== | ||
* Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990. | |||
Текущая версия от 13:05, 29 апреля 2011
Лемма о рукопожатиях (Handshake's lemma) — Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер.
Свое название лемма получила из-за следующей интерпретации: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма справедлива также для мульти- и псевдографов.
Литература
- Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.