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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Лемма о рукопожатиях''' (''Handshake's lemma'') - ''Сумма степеней всех вершин графа ---...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Лемма о рукопожатиях''' (''Handshake's lemma'') -
'''Лемма о рукопожатиях''' (''[[Handshake's lemma]]'')
''Сумма степеней всех вершин графа --- четное число, равное удвоенному числу ребер''.
''Сумма [[степень вершины|степеней]] всех [[вершина|вершин]] [[граф|графа]] — четное число, равное удвоенному числу [[ребро|ребер]]''.


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

Текущая версия от 13:05, 29 апреля 2011

Лемма о рукопожатиях (Handshake's lemma) — Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер.

Свое название лемма получила из-за следующей интерпретации: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма справедлива также для мульти- и псевдографов.

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.