WikiSort.ru - Не сортированное

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

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

$${\displaystyle \sum _{v\in V}\deg(v)=2|E|}$$

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

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

Доказательство

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

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

Регулярные графы

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

Бесконечные графы

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

Приложения

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

Примечания

Источники

• Кэмерон, Кэти & Эдмондс, Джек (1999), "Some graphic uses of an even number of odd nodes", Annales de l'Institut Fourier Т. 49 (3): 815–827, <http://www.numdam.org/item?id=AIF_1999__49_3_815_0> .
• Эйлер, Л. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Imperialis Petropolitanae Т. 8: 128–140, <http://math.dartmouth.edu/~euler/docs/originals/E053.pdf> . Печать и перевод: Биггз, Н. Л.; Лойд, И. K. & Уилсон, Р. Дж. (1976), Graph Theory 1736–1936, Oxford University Press .
• Пападимитриу, Христос Х. (1994), "On the complexity of the parity argument and other inefficient proofs of existence", Journal of Computer and System Sciences Т. 48 (3): 498–532, DOI 10.1016/S0022-0000(05)80063-7 .
• Томасон, A. Дж. (1978), "Hamiltonian cycles and uniquely edge colourable graphs", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), vol. 3, Annals of Discrete Mathematics, с. 259–268, DOI 10.1016/S0167-5060(08)70511-9 .