Лемма о рукопожатии - Handshaking lemma - Wikipedia

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

В теория графов, раздел математики, лемма о рукопожатии утверждение, что каждое конечное неориентированный граф имеет четное количество вершин с нечетным степень (количество ребер, соприкасающихся с вершиной). Говоря более разговорным языком, в группе людей, некоторые из которых пожимают руки, четное количество людей должно было пожать нечетное количество рук другим людям.

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

{ Displaystyle сумма _ {v in V} deg v = 2 | E |}

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

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

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

Доказательство Эйлера формулы суммы степеней использует технику двойной счет: он считает количество пар инцидентов (v,е) куда е это ребро и вершина v является одной из его конечных точек двумя разными способами. Вершина v принадлежит deg (v) пары, где deg (v) ( степень из v) - количество инцидентных ему ребер. Следовательно, количество падающих пар - это сумма степеней. Однако каждое ребро в графе принадлежит ровно двум инцидентным парам, по одной для каждой из его конечных точек; следовательно, число инцидентных пар равно 2 |E|, Поскольку эти две формулы рассчитывают один и тот же набор объектов, они должны иметь равные значения.

В сумме целых чисел паритет на сумму не влияет четность в сумме; общая сумма будет четной, если есть четное количество нечетных членов, и нечетной, если есть нечетное количество нечетных членов. Поскольку одна сторона формулы суммы степеней - четное число 2 |E|, сумма на другой стороне должна иметь четное количество нечетных членов; то есть должно быть четное число вершин нечетной степени.

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

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

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

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

Бесконечный граф, не подчиняющийся лемме о рукопожатии

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

Графики обмена

Несколько комбинаторных структур, перечисленных Кэмерон и Эдмондс (1999) можно показать, что их число четное, связав их с нечетными вершинами в соответствующем «графе обмена».

Например, как К. А. Б. Смит доказано, в любом кубический граф грамм должно быть четное количество Гамильтоновы циклы через любой фиксированный край УФ; Томасон (1978) использовал доказательство, основанное на лемме о рукопожатии, чтобы распространить этот результат на графы грамм в котором все вершины имеют нечетную степень. Томасон определяет граф обмена ЧАС, вершины которых находятся во взаимно однозначном соответствии с гамильтоновыми путями, начинающимися в ты и продолжая через v. Два таких пути п₁ и п₂ связаны ребром в ЧАС если можно получить п₂ добавив новый край в конец п₁ и удалив еще один край из середины п₁; это симметричное отношение, так ЧАС - неориентированный граф. Если путь п заканчивается в вершине ш, то вершина, соответствующая п в ЧАС имеет степень, равную количеству способов, которыми п может быть расширен кромкой, которая не соединяется с ты; то есть степень этой вершины в ЧАС является либо deg (ш) - 1 (четное число), если п не входит в гамильтонов цикл через УФ, или град (ш) - 2 (нечетное число), если п является частью гамильтонова цикла через УФ. С ЧАС имеет четное количество нечетных вершин, грамм должно иметь четное число гамильтоновых циклов через УФ.

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

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

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

Лемма о рукопожатии также используется при доказательстве Лемма Спернера и кусочно-линейного случая проблема альпинизма.

Примечания

^ Олдос, Джоан М .; Уилсон, Робин Дж. (2000), «Теорема 2.2», Графики и приложения: вводный подход, Серия бакалавриата по математике, Открытый университет, Springer-Verlag, стр.44, ISBN 978-1-85233-259-4
^ Чен, Си; Дэн, Сяотэ (2006), "Урегулирование сложности равновесия по Нэшу для двух игроков", Proc. 47-й симпозиум. Основы информатики, стр. 261–271, Дои:10.1109 / FOCS.2006.69, ECCC TR05-140