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

В каждом графе равное количество нечетных вершин.

В этом графе четное количество вершин (четыре вершины с номерами 2, 4, 5 и 6) имеют нечетные степени. Сумма степеней всех шести вершин равна 2 + 3 + 2 + 3 + 3 + 1 = 14 , что вдвое больше количества ребер.

В теории графов , разделе математики, лемма о рукопожатии — это утверждение, что в каждом конечном неориентированном графе число вершин, соприкасающихся с нечетным числом ребер, четно. Например, если есть группа людей, которые пожимают друг другу руки, число людей, которые пожимают руки нечетному числу других людей, является четным. ^[1] Лемма о квитировании является следствием формулы суммы степеней , также иногда называемой леммой о квитировании, ^[2] согласно которой сумма степеней ( количества касаний каждой вершины) равна удвоенному количеству ребер в график. Оба результата были доказаны Леонардом Эйлером  (1736) в его знаменитой статье о семи мостах Кенигсберга , положившей начало изучению теории графов. ^[3]

Помимо проблемы семи мостов Кенигсберга, которая впоследствии формализовала эйлеровы туры , другие применения формулы суммы степеней включают доказательства определенных комбинаторных структур. Например, при доказательстве леммы Спернера и задачи о восхождении на гору обычно возникают геометрические свойства формулы. Класс сложности PPA инкапсулирует сложность поиска второй нечетной вершины при наличии одной такой вершины в большом неявно определенном графе .

Определения и заявление

Неориентированный граф состоит из системы вершин и ребер , соединяющих неупорядоченные пары вершин. В любом графе степень вершины определяется как количество ребер, имеющих конечную точку. Для графов, которым разрешено содержать петли , соединяющие вершину с самой собой, цикл следует считать вносящим две единицы в степень его конечной точки для целей леммы о согласовании. ^[2] Тогда лемма о установлении связи гласит, что в каждом конечном графе должно быть четное число вершин, для которых является нечетным числом. ^[1] Вершины нечетной степени в графе иногда называют нечетными узлами (или нечетными вершинами ); В ^[4] в этой терминологии лемму о квитировании можно перефразировать как утверждение, что каждый граф имеет четное число нечетных узлов. ^{[4] [5]} ${\displaystyle \deg(v)}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \deg(v)}$

Формула суммы степеней гласит, что

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

^[6]ориентированных графах^[7]семействам множествмультиграфам.^[8] ${\displaystyle V}$ ${\displaystyle E}$

Оба результата применимы также к любому подграфу данного графа и, в частности, к его связным компонентам . Следствием этого является то, что для любой нечетной вершины должен существовать путь, соединяющий ее с другой нечетной вершиной. ^[9]

Приложения

Эйлеровы пути и туры

Леонард Эйлер впервые доказал лемму о рукопожатии в своей работе о семи мостах Кенигсберга , предложив совершить пешеходную экскурсию по городу Кенигсбергу (ныне Калининград ), пересекая каждый из семи его мостов один раз. Это можно перевести в термины теории графов как поиск эйлерова пути или эйлерова обхода связного графа, представляющего город и его мосты: обход графа , который пересекает каждое ребро один раз и заканчивается в вершине, отличной от той, в которой он начинается в в случае эйлерова пути или возвращение к исходной точке в случае эйлерова обхода. Эйлер сформулировал фундаментальные результаты для этой проблемы с точки зрения количества нечетных вершин в графе, которое лемма о установлении связи ограничивает четным числом. Если это число равно нулю, существует эйлеров путь, а если оно равно двум, существует эйлеров путь. В противном случае проблему невозможно решить. В случае «Семи мостов Кенигсберга» граф, представляющий задачу, имеет четыре нечетные вершины и не имеет ни эйлерова пути, ни эйлерова обхода. ^[3] Поэтому было невозможно обойти все семь мостов Кенигсберга, не повторив мост.

В алгоритме Христофидеса–Сердюкова аппроксимации задачи коммивояжера геометрические следствия формулы суммы степеней играют жизненно важную роль, позволяя алгоритму соединять вершины попарно, чтобы построить граф, на котором эйлеров тур образует приближенный тур TSP. . ^[10]

Комбинаторное перечисление

Можно показать, что несколько комбинаторных структур четны по количеству, связав их с нечетными вершинами в соответствующем «графе обмена». ^[11]

Например, как доказал К. А. Б. Смит , в любом кубическом графе должно быть четное число гамильтоновых циклов , проходящих через любое фиксированное ребро ; это циклы, которые проходят через каждую вершину ровно один раз. Томасон (1978) использовал доказательство, основанное на лемме о согласовании, чтобы распространить этот результат на графы, в которых все вершины имеют нечетную степень. Томасон определяет граф обмена , вершины которого находятся во взаимно однозначном соответствии с гамильтоновыми путями, начинающимися в ребре и продолжающимися до него . Два таких пути и определяются как соединенные ребром, если можно получить , добавив новое ребро в конец и удалив другое ребро из середины . Эта операция обратима, образуя симметричное отношение , как и неориентированный граф. Если путь заканчивается в вершине , то степень вершины, соответствующей in, равна числу способов, которыми может быть продолжено ребро, которое не соединяется обратно с ; то есть степень этой вершины в либо (четное число), если не образует часть гамильтонова цикла через , либо (нечетное число), если является частью гамильтонова цикла через . Поскольку имеет четное число нечетных вершин, должно иметь четное количество гамильтоновых циклов через . ^[12] ${\displaystyle G}$ ${\displaystyle uv}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle u}$ ${\displaystyle uv}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{2}}$ ${\displaystyle H}$ ${\displaystyle p_{2}}$ ${\displaystyle p_{1}}$ ${\displaystyle p_{1}}$ ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle w}$ ${\displaystyle p}$ ${\displaystyle H}$ ${\displaystyle p}$ ${\displaystyle u}$ ${\displaystyle H}$ ${\displaystyle \deg(w)-1}$ ${\displaystyle p}$ ${\displaystyle uv}$ ${\displaystyle \deg(w)-2}$ ${\displaystyle p}$ ${\displaystyle uv}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle uv}$

Другие приложения

Лемма о рукопожатии (или формула суммы степеней) также используется в доказательстве ряда других результатов в математике. К ним относятся следующие:

Раскраска Спернера треугольного треугольника, затененная, чтобы выделить три маленьких треугольника, которые имеют все три цвета вершин.

• Лемма Спернера гласит, что если большой треугольник разделить на меньшие треугольники, соединяющиеся ребром к краю, и вершины помечены тремя цветами так, что вдоль каждого края большого треугольника используются только два цвета, то по крайней мере один треугольников меньшего размера имеет вершины всех трех цветов; он имеет приложения в теоремах о неподвижной точке , алгоритмах поиска корней и справедливом делении . Одним из доказательств этой леммы является граф обмена, вершинами которого являются треугольники (как маленькие, так и большие), а ребра соединяют пары треугольников, которые имеют две общие вершины некоторых двух цветов. В этом графе обмена большой треугольник обязательно имеет нечетную степень, как и маленький треугольник всех трех цветов, но не другие маленькие треугольники. По лемме о рукопожатии должно быть нечетное количество маленьких треугольников всех трех цветов, и, следовательно, должен существовать хотя бы один такой треугольник. ^[13]

Проблема альпинизма

• Задача альпинизма утверждает, что для достаточно хорошо ведущих себя функций на единичном интервале с равными значениями на концах интервала можно скоординировать движение двух точек, начиная с противоположных концов интервала, так, что они встречаются где-то посередине, оставаясь в точках равной ценности на протяжении всего движения. Одно из доказательств этого включает в себя аппроксимацию функции кусочно-линейной функцией с одинаковыми крайними точками, параметризацию положения двух движущихся точек координатами одной точки в единичном квадрате и показ того, что доступные положения для двух точек образуют конечный граф, вложенный в этот квадрат, имеющий только начальную позицию и ее обращение в качестве нечетных вершин. По лемме о согласовании эти две позиции принадлежат одной и той же связной компоненте графа, и путь от одной к другой обязательно проходит через искомую точку встречи. ^[14]
• Гипотеза реконструкции касается проблемы однозначного определения структуры графа из мультимножества подграфов, образованного удалением из него единственной вершины. Учитывая эту информацию, формулу суммы степеней можно использовать для восстановления количества ребер в данном графе и степеней каждой вершины. Отсюда можно определить, является ли данный граф регулярным графом , и если да, то определить его однозначно из любого подграфа, удаленного из вершины, путем добавления нового соседа для всех вершин подграфа слишком низкой степени. Следовательно, все регулярные графы можно восстановить. ^[15]
• В игре «Гекс» участвуют два игрока, которые размещают фигуры своего цвета на мозаике доски в форме параллелограмма шестиугольниками до тех пор, пока у одного игрока не будет соединенный путь соседних фигур от одной стороны доски к другой. Она никогда не может закончиться ничьей: к тому времени, как доска полностью заполнится фигурами, у одного из игроков будет сформирован выигрышный путь. Одним из доказательств этого является граф из заполненного игрового поля с вершинами в углах шестиугольников и ребрами на сторонах шестиугольников, разделяющими цвета двух игроков. Этот граф имеет четыре нечетные вершины в углах доски и четные вершины в других местах, поэтому он должен содержать путь, соединяющий два угла, который обязательно имеет выигрышный путь для одного игрока на одной из своих сторон. ^[16]

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

В доказательстве Эйлером формулы суммы степеней используется техника двойного счета : он подсчитывает количество инцидентных пар, где - ребро, а вершина - одна из его конечных точек, двумя разными способами. Вершина принадлежит паре, где (степень ) — число инцидентных ей ребер. Следовательно, количество инцидентных пар есть сумма степеней. Однако каждое ребро графа принадлежит ровно двум инцидентным парам, по одному на каждую из его конечных точек; следовательно, число инцидентных пар равно . Поскольку эти две формулы учитывают один и тот же набор объектов, они должны иметь равные значения. То же доказательство можно интерпретировать как суммирование элементов матрицы инцидентности графа двумя способами: по строкам, чтобы получить сумму степеней, и по столбцам, чтобы получить удвоенное количество ребер. ^[5] ${\displaystyle (v,e)}$ ${\displaystyle e}$ ${\displaystyle v}$ ${\displaystyle v}$ ${\displaystyle \deg(v)}$ ${\displaystyle \deg(v)}$ ${\displaystyle v}$ ${\displaystyle 2|E|}$

Для графов лемма о согласовании является следствием формулы суммы степеней. ^[8] В сумме целых чисел на четность суммы не влияют четные члены суммы; общая сумма четна, если имеется четное количество нечетных членов, и нечетна, если имеется нечетное количество нечетных членов. Поскольку одна сторона формулы суммы степеней представляет собой четное число , сумма на другой стороне должна иметь четное количество нечетных членов; то есть должно быть четное число вершин нечетной степени. ^[5] ${\displaystyle 2|E|}$

В качестве альтернативы можно использовать математическую индукцию для доказательства формулы суммы степеней ^[2] или напрямую доказать, что число вершин нечетной степени четно, удаляя по одному ребру за раз из данного графа и используя анализ случаев. по степеням его концов, чтобы определить влияние этого удаления на четность числа вершин нечетной степени. ^[17]

В специальных классах графов

Обычные графики

Из формулы суммы степеней следует, что каждый правильный граф с вершинами имеет ребра. ^[18] Поскольку количество ребер должно быть целым числом, отсюда следует, что если число нечетно, то количество вершин должно быть четным. ^[19] Кроме того, для нечетных значений количество ребер должно делиться на . ^[20] ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle nr/2}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle r}$

Двудольные и бирегулярные графы

В двудольном графе вершины разделены на два подмножества, причем каждое ребро имеет одну конечную точку в каждом подмножестве. Из того же аргумента двойного подсчета следует, что в каждом подмножестве сумма степеней равна количеству ребер в графе. В частности, оба подмножества имеют равные суммы степеней. ^[21] Для бирегулярных графов с разделением вершин на подмножества и с каждой вершиной в подмножестве, имеющей степень , должно быть так, что ; оба равны количеству ребер. ^[22] ${\displaystyle V_{1}}$ ${\displaystyle V_{2}}$ ${\displaystyle V_{i}}$ ${\displaystyle r_{i}}$ ${\displaystyle |V_{1}|r_{1}=|V_{2}|r_{2}}$

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

Бесконечный граф только с одной нечетной вершиной

Лемма о рукопожатии не применима в своей обычной форме к бесконечным графам, даже если они имеют только конечное число вершин нечетной степени. Например, бесконечный граф путей с одной конечной точкой имеет только одну вершину нечетной степени, а не четное количество таких вершин. Однако можно сформулировать версию леммы о согласовании, используя понятие конца , класса эквивалентности полубесконечных путей («лучей»), рассматривающих два луча как эквивалентные, когда существует третий луч, который использует бесконечно много вершин из каждый из них. Степень конца — это максимальное количество лучей, не пересекающихся по краям, которые он содержит, и конец является нечетным, если его степень конечна и нечетна. В более общем смысле, можно определить конец как нечетный или четный, независимо от того, имеет ли он бесконечную степень, в графах, все вершины которых имеют конечную степень. Тогда в таких графах число нечетных вершин и нечетных концов, сложенных вместе, либо четное, либо бесконечное. ^[23]

Подграфы

По теореме Галлаи вершины любого графа можно разложить так: где все степени четные, а все степени нечетные с четными, согласно лемме о рукопожатии. В 1994 году Яир Каро ^[24] доказал это , а в 2021 году препринт Фербера Асафа и Михаила Кривелевича показал это . ^{[25] [26]} ${\displaystyle V=V_{e}\cup V_{o}}$ ${\displaystyle G(V_{e})}$ ${\displaystyle G(V_{o})}$ ${\displaystyle |V_{o}|}$ ${\displaystyle |V_{o}|/|V|>1/{\sqrt {n}}}$ ${\displaystyle |V_{o}|/|V|>1/10000}$

Вычислительная сложность

В связи с методом графа обмена для доказательства существования комбинаторных структур представляет интерес вопрос, насколько эффективно можно найти эти структуры. Например, предположим, что в качестве входных данных задан гамильтонов цикл в кубическом графе; из теоремы Смита следует, что существует второй цикл. Как быстро можно найти этот второй цикл? Пападимитриу (1994) исследовал вычислительную сложность подобных вопросов или, в более общем плане, поиска второй вершины нечетной степени, когда задана единственная нечетная вершина в большом неявно определенном графе . Он определил класс сложности PPA для инкапсуляции таких проблем, как эта; ^[27] тесно связанный класс, определенный на ориентированных графах, PPAD , привлек значительное внимание в алгоритмической теории игр , поскольку вычисление равновесия Нэша вычислительно эквивалентно самым сложным задачам этого класса. ^[28]

Вычислительные задачи, доказавшие свою полноту для класса сложности PPA, включают вычислительные задачи, связанные с леммой Спернера ^[29] и справедливым разделением ресурсов согласно теореме Хобби–Райса . ^[30]

Примечания

1. Хейн, Джеймс Л. (2015), «Пример 3: Проблема установления связи», Дискретные структуры, логика и вычислимость , Jones & Bartlett Publishers, стр. 703, ISBN 9781284070408
2. Гундерсон, Дэвид С. (2014), Справочник по математической индукции: теория и приложения, CRC Press, стр. 240, ISBN 9781420093650
3. Эйлер, Л. (1736), «Solutio проблемное объявление geometriam situs pertinentis» (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128–140. Перепечатано и переведено в Биггсе, Нидерланды ; Ллойд, ЕК; Уилсон, Р.Дж. (1976), Теория графов 1736–1936 , Oxford University Press
4. Хиггинс, Питер М. (1998), Математика для любознательных, Oxford University Press, стр. 201, ISBN 9780192880727
5. Биггс, Норман Л. (2002), «15,3: Степень», Дискретная математика , Oxford University Press, стр. 181–182, ISBN 9780198507178
6. Уэст, Дуглас Б. (1996), «1.3.3. Теорема. (Формула суммы степеней)», Введение в теорию графов (2-е изд.), Прентис Холл, стр. 26, ISBN 9780132278287
7. Лоер, Николас (2011), «3.31. Теорема: формула суммы степеней для орграфов», Биективная комбинаторика , CRC Press, стр. 106, ISBN 9781439848869
8. Jukna, Stasys (2011), «Предложение 1.7», Экстремальная комбинаторика , Тексты по теоретической информатике. Серия EATCS, Springer, стр. 9, номер домена : 10.1007/978-3-642-17364-6, ISBN 978-3-642-17363-9
9. Рэй, Сантану Саха (2012), «Теорема 2.2», Теория графов с алгоритмами и ее приложения в прикладной науке и технологиях, Springer, стр. 16, ISBN 9788132207504
10. Кристофидес, Никос (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного управления, CMU, заархивировано (PDF) из оригинала 21 июля 2019 г.. Лемма о рукопожатии приведена вверху страницы 2.
11. Кэмерон, Кэти; Эдмондс, Джек (1999), «Некоторые графические использования четного числа нечетных узлов», Annales de l'Institut Fourier , 49 (3): 815–827, doi : 10.5802/aif.1694 , MR  1703426
12. Томасон, А.Г. (1978), «Гамильтоновы циклы и графы, раскрашиваемые однозначно по краям», Достижения в теории графов (Кембриджская комбинаторная конференция, Тринити-колледж, Кембридж, 1977) , Анналы дискретной математики, том. 3, стр. 259–268, doi :10.1016/S0167-5060(08)70511-9, MR  0499124
13. Айгнер, Мартин ; Циглер, Гюнтер М. (2018), «Раздел 28.6: Лемма Спернера», Доказательства из КНИГИ (6-е изд.), Берлин: Springer, стр. 203–205, doi : 10.1007/978-3-662-57265-8 , ISBN 978-3-662-57264-1, МР  3823190
14. Гудман, Джейкоб Э .; Пах, Янош ; Ага, Чи-К. (1989), «Альпинизм, перемещение по лестнице и ширина кольца многоугольника» (PDF) , The American Mathematical Monthly , 96 (6): 494–510, doi : 10.2307/2323971, JSTOR  2323971, MR  0999412
15. Лаури, Йозеф; Скапеллато, Раффаэле (2016), Темы автоморфизмов и реконструкции графов, Серия лекций Лондонского математического общества, том. 432 (2-е изд.), Cambridge University Press, стр. 105–106, номер документа : 10.1017/CBO9781316669846, ISBN. 978-1-316-61044-2, МР  3496604
16. Гейл, Дэвид (1979), «Игра в Hex и теорема Брауэра о неподвижной точке», The American Mathematical Monthly , 86 (10): 818–827, doi : 10.1080/00029890.1979.11994922, JSTOR  2320146, MR  0551501
17. Нето, Антонио Каминья Мунис (2018), Экскурс по элементарной математике, Том III: Дискретная математика и полиномиальная алгебра , Сборники задач по математике, Springer, стр. 132, 562, ISBN 9783319779775
18. Олдос, Джоан М.; Уилсон, Робин Дж. (2000), «Теорема 2.2», Графики и приложения: вводный подход , Серия по математике для студентов, Открытый университет, Springer-Verlag, стр. 44, ISBN 978-1-85233-259-4
19. Уоллис, WD (2011), «Раздел 7.1, Введение в графики, следствие 1», Руководство для начинающих по дискретной математике (2-е изд.), Springer, p. 219, ISBN 9780817682866
20. Кларк, Джон; Холтон, Дерек Аллан (1995), «Проблема 1.4.6», Первый взгляд на теорию графов , Allied Publishers, стр. 16, ISBN 9788170234630
21. Ловас, Ласло (2014), Комбинаторные задачи и упражнения (2-е изд.), Elsevier, стр. 2014. 281, ISBN 9780080933092
22. Писанский, Томаж ; Серватиус, Бриджит (2013), «2.3.4: Полурегулярные двудольные графы», Конфигурации с графической точки зрения , Расширенные тексты Birkhäuser: Basler Lehrbücher, Нью-Йорк: Birkhäuser/Springer, стр. 35, номер домена : 10.1007/978-0-8176-8364-1, ISBN 978-0-8176-8363-4, МР  2978043
23. Брюн, Хеннинг; Штейн, Майя (2007), «О конечных степенях и бесконечных циклах в локально конечных графах», Combinatorica , 27 (3): 269–291, doi : 10.1007/s00493-007-2149-0, MR  2345811, S2CID  8367713; см. предложение 15, с. 284
24. Каро, Яир (15 сентября 1994 г.). «О индуцированных подграфах нечетных степеней». Дискретная математика . 132 (1–3): 23–28. дои : 10.1016/0012-365X(92)00563-7 .
25. Фербер, Асаф; Кривелевич, Михаил (2020). «Каждый граф содержит индуцированный подграф линейного размера со всеми нечетными степенями». arXiv : 2009.05495 ​​[math.CO].
26. Хоннер, Патрик (24 марта 2022 г.). «Что математическая вечеринка говорит нам о теории графов». Журнал Кванта . Проверено 27 марта 2022 г.
27. Пападимитриу, Христос Х. (1994), «О сложности аргумента четности и других неэффективных доказательствах существования», Journal of Computer and System Sciences , 48 ​​(3): 498–532, doi : 10.1016/S0022-0000( 05)80063-7 , МР  1279412
28. Чен, Си; Дэн, Сяоте (2006), «Урегулирование сложности равновесия Нэша для двух игроков», Proc. 47-й симп. Основы информатики , стр. 261–271, номер документа : 10.1109/FOCS.2006.69, S2CID  14102058, ECCC  TR05-140.
29. Гриньи, Микеланджело (2001), «Завершение леммы Спернера для PPA», Information Processing Letters , 77 (5–6): 255–259, doi : 10.1016/S0020-0190(00)00152-6, MR  1818525
30. Филос-Рацикас, Арис; Голдберг, Пол В. (2018), «Консенсусное сокращение вдвое является PPA-полным», в Диакониколасе, Илиасе; Кемпе, Дэвид; Хензингер, Моника (ред.), Труды 50-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2018, Лос-Анджелес, Калифорния, США, 25–29 июня 2018 г. , стр. 51–64, arXiv : 1711.04503 , doi : 10.1145/3188745.3188880, S2CID  8111195