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

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

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

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

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

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

Доказ[ред.ред. код]

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

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

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

Регулярні графи[ред.ред. код]

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

Нескінченні графи[ред.ред. код]

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

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

Обмін графів[ред.ред. код]

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

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

Обчислювальна складність[ред.ред. код]

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

Інше[ред.ред. код]

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

Примітки[ред.ред. код]

  1. Aldous, Joan M.; Wilson, Robin J. (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. 

Посилання[ред.ред. код]