В теории графов , разделе математики, лемма о рукопожатии - это утверждение, что каждый конечный неориентированный граф имеет четное количество вершин с нечетной степенью (количество ребер, соприкасающихся с вершиной). Говоря более разговорным языком, в группе людей, некоторые из которых пожимают руки, четное количество людей должно было пожать нечетное количество рук другим людям. Вершины нечетной степени в графе иногда называют нечетными узлами или нечетными вершинами ; в этой терминологии лемму о подтверждении связи можно переформулировать как утверждение, что каждый граф имеет четное число нечетных узлов.
Лемма о рукопожатии является следствием формулы суммы степеней (также иногда называемой леммой о рукопожатии ),
для графа с множеством вершин V и множеством ребер Е . Оба результата были доказаны Леонардом Эйлером ( 1736 г. ) в его знаменитой статье о семи мостах Кенигсберга , положившей начало изучению теории графов. [1]
Другие приложения включают доказательство того, что для определенных комбинаторных структур количество структур всегда четно, а также помощь в доказательствах леммы Спернера и проблемы альпинизма . Класс сложности PPA инкапсулирует сложность поиска второй нечетной вершины для одной такой вершины в большом неявно определенном графе .
Доказательство [ править ]
Доказательство формулы суммы степеней Эйлером использует технику двойного счета : он подсчитывает количество инцидентных пар ( v , e ), где e - ребро, а вершина v - одна из его конечных точек, двумя разными способами. Вершина v принадлежит град ( V ) , где пар, град ( v ) (далее степени из V ) является число ребер , инцидентных к нему. Следовательно, количество падающих пар - это сумма степеней. Однако каждое ребро в графе принадлежит ровно двум инцидентным парам, по одной для каждой из его конечных точек; следовательно, число инцидентных пар равно 2 | E|, Поскольку эти две формулы учитывают один и тот же набор объектов, они должны иметь равные значения.
В сумме целых чисел четность не влияет на четность суммы; общая сумма будет четной, если есть четное количество нечетных членов, и нечетной, если есть нечетное количество нечетных членов. Поскольку одна сторона формулы суммы степеней - четное число 2 | E |, сумма на другой стороне должна содержать четное число нечетных членов; то есть должно быть четное число вершин нечетной степени.
В качестве альтернативы можно использовать математическую индукцию, чтобы доказать, что количество вершин с нечетной степенью является четным, удаляя по одному ребру за раз из данного графа и используя случайный анализ степеней его конечных точек, чтобы определить влияние этого удаление от четности числа вершин нечетной степени.
В специальных классах графиков [ править ]
Обычные графики [ править ]
Формула степени суммы означает , что каждый г - регулярный граф с п вершинами имеет NR / 2 ребер. [2] В частности, если r нечетно, то количество ребер должно делиться на r , а количество вершин должно быть четным.
Бесконечные графики [ править ]
Лемма о рукопожатии неприменима к бесконечным графам, даже если они имеют только конечное число вершин нечетной степени. Например, бесконечный линейный граф с одной конечной точкой имеет только одну вершину нечетной степени, а не четное число таких вершин.
Приложения [ править ]
Пути и туры Эйлера [ править ]
Леонард Эйлер впервые доказал лемму о рукопожатии в своей работе о семи мостах Кенигсберга , попросив пешеходную экскурсию по городу Кенигсберг (ныне Калининград ), пересекая каждый из семи мостов один раз. Это можно перевести в теоретико-графические термины, как запрос пути Эйлера или тура Эйлера.связного графа, представляющего город и его мосты: прогулка по графу, которая пересекает каждое ребро один раз, либо заканчиваясь в другой вершине, чем она начинается в случае пути Эйлера, либо возвращаясь к своей начальной точке в случае пути Эйлера. тур. Эйлер сформулировал фундаментальные результаты для этой проблемы в терминах числа нечетных вершин в графе, которое лемма о подтверждении связи ограничивает четным числом. Если это число равно нулю, существует эйлеров тур, а если два, то существует эйлеров путь. Иначе проблему не решить. В случае Семи мостов Кенигсберга граф, представляющий задачу, имеет четыре нечетных вершины и не имеет ни пути Эйлера, ни тура Эйлера. [1]
В алгоритме Христофидеса – Сердюкова для аппроксимации задачи коммивояжера тот факт, что количество нечетных вершин является четным, играет ключевую роль, позволяя алгоритму соединять эти вершины попарно, чтобы построить граф, на котором тур Эйлера образует примерный тур по ТСП. [3]
В комбинаторном перечислении [ править ]
Можно показать, что несколько комбинаторных структур являются четными, если связать их с нечетными вершинами в соответствующем «графе обмена». [4]
Например, как доказал К. А. Смит , в любом кубическом графе G должно быть четное число гамильтоновых циклов, проходящих через любое фиксированное ребро uv ; Томасон (1978) использовал доказательство, основанное на лемме о рукопожатии, чтобы распространить этот результат на графы G, в которых все вершины имеют нечетную степень. Томасон определяет обменный граф H , вершины которого находятся во взаимно однозначном соответствии с гамильтоновыми путями, начинающимися в u и продолжающимися через v . Два таких пути p 1 и p 2 соединены ребром в Hесли можно получить p 2 , добавив новый край к концу p 1 и удалив другой край из середины p 1 ; это симметричное отношение , поэтому H - неориентированный граф. Если путь p заканчивается в вершине w , то вершина, соответствующая p в H, имеет степень, равную количеству способов, которыми p может быть расширен ребром, которое не соединяется обратно с u ; то есть степень этой вершины в H равна deg ( w ) - 1 (четное число), если pне является частью гамильтонова цикла через uv или deg ( w ) - 2 (нечетное число), если p является частью гамильтонова цикла через uv . Поскольку H имеет четное число нечетных вершин, G должна иметь четное число гамильтоновых циклов, проходящих через uv . [5]
Другие приложения [ править ]
Лемма о рукопожатии также используется при доказательстве леммы Спернера и кусочно-линейного случая задачи альпинизма .
Вычислительная сложность [ править ]
В связи с методом графа обмена для доказательства существования комбинаторных структур представляет интерес вопрос, насколько эффективно эти структуры могут быть найдены. Например, предположим, что на входе задан гамильтонов цикл в кубическом графе; из теоремы Смита следует, что существует второй цикл. Как быстро можно найти этот второй цикл? Пападимитриу (1994) исследовал вычислительную сложность таких вопросов, как этот, или, в более общем плане, нахождения второй вершины нечетной степени, когда дана одна нечетная вершина в большом неявно определенном графе . Он определил PPA класса сложности для инкапсуляции таких проблем, как эта; [6]Тесно связанный класс, определенный на ориентированных графах, PPAD , привлек значительное внимание в теории алгоритмических игр, поскольку вычисление равновесия по Нэшу с вычислительной точки зрения эквивалентно сложнейшим задачам этого класса. [7]
Заметки [ править ]
- ^ a b Эйлер, Л. (1736), "Solutio problematis ad geometriam situs pertinentis" (PDF) , Commentarii Academiae Scientiarum Imperialis Petropolitanae , 8 : 128–140. Перепечатано и переведено в Биггсе, Нидерланды; Ллойд, EK; Уилсон, Р.Дж. (1976), Теория графов 1736–1936 , Oxford University Press
- ^ Олдос, Джоан М .; Уилсон, Робин Дж. (2000), «Теорема 2.2», Графы и приложения: вводный подход , Серия «Математика для бакалавров», Открытый университет, Springer-Verlag, p. 44 , ISBN 978-1-85233-259-4
- ^ Кристофидес, Никос (1976), Анализ наихудшего случая новой эвристики для задачи коммивояжера (PDF) , Отчет 388, Высшая школа промышленного администрирования, CMU . Лемма о рукопожатии цитируется вверху страницы 2.
- ^ Кэмерон, Кэти; Эдмондс, Джек (1999), "Некоторое графическое использование четного числа нечетных узлов" , Annales де l'Institut Фурье , 49 (3): 815-827, DOI : 10.5802 / aif.1694 , MR 1703426
- ^ Томасон, А. Г. (1978), «Гамильтоновы циклы и уникально края благовидных графов», Авансы в теории графов (Кембридж Комбинаторных Conf., Тринити - колледж, Кембридж, 1977) , Annals дискретной математики, 3 , стр. 259-268, дои : 10.1016 / S0167-5060 (08) 70511-9 , MR 0499124
- ^ Papadimitriou, Christos H. (1994), "О сложности аргумента четности и других неэффективных доказательств существования", журнал компьютерных и системных наук , 48 (3): 498-532, DOI : 10.1016 / S0022-0000 ( 05) 80063-7 , Руководство по ремонту 1279412
- ^ Чен, Си; Дэн, Сяотэ (2006), "Урегулирование сложности равновесия по Нэшу для двух игроков", Proc. 47-й симпозиум. Основы информатики и вычислительной техники ., Стр 261-271, DOI : 10,1109 / FOCS.2006.69 , ECCC TR05-140
