Лемма о рукопожатиях

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Чётное число вершин (четыре: 2, 4, 5 и 6) данного графа имеют нечётную степень. Сумма степеней всех вершин равна 14, то есть удвоенному числу рёбер графа.

Лемма о рукопожатиях — положение теории графов, согласно которому любой конечный неориентированный граф имеет чётное число вершин нечётных степеней. Лемма берёт название от популярной аналогии: в группе людей, некоторые из которых пожимают друг другу руки, чётное число людей поприветствовало таким образом нечётное число коллег.

Лемма является следствием формулы суммы степеней, также иногда называемой леммой о рукопожатиях.

\sum_{v\in V} \deg(v) = 2|E|

для графа с множеством вершин V и множеством рёбер E. Оба результата доказаны Эйлером в его знаменитом докладе о семи мостах Кёнигсберга (1736). Эта работа положила начало исследованиям в области теории графов.

Вершины нечётных степеней графа иногда называются нечётными узлами или нечётными вершинами. Используя эту терминологию, можно перефразировать лемму таким образом: каждый граф имеет чётное число нечётных вершин.

Доказательство[править | править исходный текст]

При доказательстве упомянутой формулы Эйлер использовал технику двойного (повторного) счёта. Он посчитал количество инцидентных пар (v,e), где e — ребро и v — одна из его концевых вершин двумя разными способами. Вершина v принадлежит deg(v) парам, где deg(v) — степень вершины (количество инцидентных ей рёбер). Следовательно, число инцидентных пар совпадает с суммой всех степеней. Однако каждое ребро принадлежит двум инцидентным парам, так как имеет две концевые вершины. Поэтому число инцидентных пар равно 2|E|. Поскольку две данные формулы предназначены для одного и то же множества, их значения одинаковы.

Чётность или нечётность суммы целых чисел не зависит от количества чётных слагаемых. Сумма чётна, если число нечётных слагаемых чётно (и нечётна в противном случае). Так как одна часть уравнения всегда чётна (2|E|), другая часть должна содеражать чётное число нечётных слагаемых, т. е. вершин нечётной степени.

Регулярные графы[править | править исходный текст]

Формулы суммы степеней подразумевает, что k-регулярный граф с числом вершин n имеет kn/2 рёбер.[1] В частности, если k нечётно, число рёбер должно делиться на k.

Бесконечные графы[править | править исходный текст]

Лемма не применима к бесконечным графам, даже если они имеют конечное число нечётных вершин. Например, бесконечный путь с одной концевой вершиной имеет единственную нечётную вершину (то есть, нечётное количество).

Графы обмена[править | править исходный текст]

Вычислительная сложность[править | править исходный текст]

Другие приложения[править | править исходный текст]

Лемма о рукопожатиях также использована при доказательстве леммы Шпернера и кусочно-линейного случая проблемы «о восхождении на гору».

Примечания[править | править исходный текст]

  1. Олдес, Джоан M. & Уилсон, Робин Дж. (2000), "Theorem 2.2", «Graphs and Applications: an Introductory Approach», Undergraduate Mathematics Series, The Open University, Springer-Verlag, с. 44, ISBN 978-1-85233-259-4 

Источники[править | править исходный текст]