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