Лема про рукостискання

У теорії графів, галузі математики, Лема про рукостискання є твердженням, що у кожного кінцевого неорієнтованого графу є парне число вершин із непарним степенем (число граней, що інцидентні вершині). Якщо простіше, у групі людей, які обмінюються рукостисканнями, є парне число людей, які напевно потиснули непарну кількість рук інших людей.

На цьому графі, з парним числом вершин (чотири вершини пронумеровані 2, 4, 5 і 6) мають непарні степені. Сума степенів вершин дорівнює 2 + 3 + 2 + 3 + 3 + 1 = 14, подвійному числу ребер.

Лема про рукостискання — наслідок формули суми степенів (яку також іноді називають лемою про рукостискання).

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

Для графа з множиною вершин V і множиною ребер Е. Обидва результати довів Леонард Ейлер (1736) у своїй відомій роботі про Сім мостів Кеніґсберґа, з якої починається теорія графів.

Вершини непарного степеня в графі іноді називають непарними вузлами або непарними вершинами. У цій термінології лему про рукостискання можна переформулювати як твердження, що кожен граф має парне число непарних вузлів.

Доказ

Доказ формули суми степенів Ейлера використовує техніку подвійного підрахунку: він підраховує кількість інцидентних пар (v, e), де e — ребро, а вершина v — це один із його кінців у двох різних кінцях. Вершина v належить до пар deg(v), де deg(v) (степінь вершини v) — це кількість ребер, інцидентних їй. Тому число інцидентних пар є сумою степенів. Тим не менш, кожне ребро в графі належить саме двом інцидентним парам, по одному для кожного з його кінців. Тому число інцидентних пар — 2|E|. Так як ці дві формули розраховують один і той самий набір об'єктів, вони повинні мати однакові значення.

Отже, парність суми цілих чисел не залежить від парності доданків. Загальна сума є парною, якщо є парне число непарних точок, і непарною, коли є непарне число непарних членів. Зважаючи на те, що одна частина формули суми степенів є парним числом 2|E|, сума на іншій стороні повинна бути парним числом непарних членів. Тобто, повинно бути парне число вершин з непарним степенем.

Як альтернативу можна використовувати математичну індукцію, щоб довести, що число вершин з непарним степенем є парним. Це можна зробити шляхом видалення одного ребра з цього графу і одночасно використати аналіз випадків на степенях його кінцевих точок, щоб визначити вплив видалення парності числа непарного степеня вершин.

Регулярні графи

Формула степеня суми припускає, що кожен r-регулярний граф з n вершинами має nr/2 граней. Зокрема, якщо r непарне, то число ребер має ділитися на r.

Нескінченні графи

Нескінченний граф, який не підкорюється лемі про рукостискання

Лема про рукостискання не поширюється на нескінченні графи, навіть якщо вони мають кінцеве число вершин з непарним степенем. Наприклад, нескінченний шлях графа з однієї кінцевої точки має тільки одну вершину з непарним степенем замість парного числа таких вершин.

Обмін графів

Кілька комбінаторних структур, наведених Кемероном і Едмондсом (Cameron та Edmonds, (1999)), можуть бути показаними навіть у ряді, зв'язавши їх з непарними вершинами у відповідному «графі обміну».

Наприклад, як довів С. Сміт, у будь-якому кубічному графі G має бути парне число гамільтонових циклів, що проходять через будь-яку фіксовану uv. Томасон у 1978 використав доказ, заснований на лемі рукостискання, аби поширити цей результат на граф G, в якому всі вершини мають непарний степінь. Томасон визначає граф обміну H, вершини якого знаходяться в однозначній відповідності з гамильтоновим шляхом, починаючи з u і продовжуючи через v. Два таких шляхи p₁ і p₂ з'єднані ребром в H, якщо можна отримати p₂ шляхом додаванням нового ребра до кінця p₁ і видалення іншого ребра з середини p_1, це симетричне відношення, тобто Н — неорієнтований граф. Якщо шлях р закінчується у вершині w, то вершина, відповідна р в Н має степінь, рівний кількості способів, у якій може бути продовжений по ребру, що не пов'язує його назад з u. Тобто, степінь цієї вершини в Н або deg(w) — 1 (парне число), якщо р не є частиною гамільтонового циклу через uv, або deg(w) — 2 (непарне число), якщо р є частиною гамільтонового циклу через uv. Так як H має парне число непарних вершин, G повинен мати парне число гамільтонових циклів через uv.

Обчислювальна складність

У зв'язку з тим, що спосіб обміну графів для доказу існування комбінаторних структур представляє інтерес, постає питання, наскільки ефективно ці структури можуть бути знайдені. Наприклад, припустимо, що вона задана як частина гамільтонового циклу в кубічний граф. Із теореми Сміта випливає, що існує другий цикл. Як швидко можна знайти другий цикл? Професор Христос Пападімітріу досліджував обчислювальну складність питань, подібних цьому, або в більш загальному вигляді знаходження другої вершини з непарним степенем, коли один отримує одиночну непарну вершину у великому неявному графі. Він визначив обчислювальну складність PPAD для інкапсуляції таких проблем, як ця.

Інше

Лема про рукостискання також використовується в доказі леми Шпернера та у кусково-лінійному випадку теореми про сходження на гору.

Посилання

• Cameron, Kathie; Edmonds, Jack (1999), Some graphic uses of an even number of odd nodes, Annales de l'Institut Fourier, 49 (3): 815—827, doi:10.5802/aif.1694, MR 1703426, архів оригіналу за 3 березня 2016, процитовано 6 травня 2016.
• Euler, L. (1736), Solutio problematis ad geometriam situs pertinentis (PDF), Commentarii Academiae Scientiarum Imperialis Petropolitanae, 8: 128—140, архів оригіналу (PDF) за 20 травня 2011, процитовано 6 травня 2016. Reprinted and translated in Biggs, N. L.; Lloyd, E. K.; Wilson, R. J. (1976), Graph Theory 1736–1936, Oxford University Press.
• Papadimitriou, Christos H. (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, MR 1279412.
• Thomason, A. G. (1978), Hamiltonian cycles and uniquely edge colourable graphs, Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, т. 3, с. 259—268, doi:10.1016/S0167-5060(08)70511-9, MR 0499124.