WikiDer > Теорема Эрдеша – Галлаи

Erdős–Gallai theorem

В Теорема Эрдеша – Галлаи это результат теория графов, филиал комбинаторная математика. Он предоставляет один из двух известных подходов к решению задача реализации графа, т.е. дает необходимое и достаточное условие конечная последовательность из натуральные числа быть последовательность степеней из простой график. Последовательность, удовлетворяющая этим условиям, называется «графической». Теорема была опубликована в 1960 г. Пол Эрдёш и Тибор Галлай, в честь кого назван.

Заявление

Последовательность неотрицательных целые числа можно представить как последовательность степеней конечного простой график на п вершины тогда и только тогда, когда даже и

выполняется для любого k из .

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

Нетрудно показать, что условия теоремы Эрдеша – Галлаи необходимы для того, чтобы последовательность чисел была наглядной. Требование четности суммы степеней есть лемма о рукопожатии, уже использованный Эйлером в его статье 1736 г. мосты Кенигсберга. Неравенство между суммой наибольшие степени и сумма оставшихся степеней могут быть установлены двойной счет: в левой части указано количество смежностей ребер и вершин среди вершины наивысшей степени, каждая такая смежность должна быть на ребре с одной или двумя конечными точками высокой степени, Член справа дает максимально возможное количество смежностей ребер и вершин, в которых обе конечные точки имеют высокую степень, а оставшийся член в правой верхней границе ограничивает количество ребер, которые имеют ровно одну конечную точку высокой степени. Таким образом, более трудная часть доказательства - показать, что для любой последовательности чисел, удовлетворяющей этим условиям, существует граф, для которого это последовательность степеней.

Оригинальное доказательство Эрдеш и Галлай (1960) был долгим и интересным. Чоудум (1986) приводит более короткое доказательство Клод Берже, основанный на идеях сетевой поток. Чоудум вместо этого предоставляет доказательство математическая индукция по сумме степеней: он позволяет быть первым индексом числа в последовательности, для которого (или предпоследнее число, если все равны), использует анализ случая, чтобы показать, что последовательность, образованная вычитанием единицы из и от последнего числа в последовательности (и удаления последнего числа, если это вычитание приводит к тому, что оно становится равным нулю) снова является графическим и формирует граф, представляющий исходную последовательность, путем добавления края между двумя позициями, из которых была вычтена единица.

Трипати, Венугопалан и Запад (2010) Рассмотрим последовательность «подреализаций», графов, степени которых ограничены сверху данной последовательностью степеней. Они показывают, что если грамм является субреализацией, а я наименьший индекс вершины в грамм чья степень не равна dя, тогда грамм может быть изменен таким образом, чтобы произвести другую субреализацию, увеличивая степень вершины я без изменения степеней предыдущих вершин в последовательности. Повторяющиеся шаги такого рода должны в конечном итоге привести к реализации заданной последовательности, доказывающей теорему.

Отношение к целочисленным разделам

Эйгнер и Триеш (1994) описывают тесную связь между теоремой Эрдеша – Галлаи и теорией целые разделы.Позволять ; затем отсортированные целочисленные последовательности, суммирующие можно интерпретировать как разбиение . Под мажоризация от их префиксные суммы, перегородки образуют решетка, в котором минимальное изменение между отдельным разделом и другим разделом ниже по порядку разделов заключается в вычитании единицы из одного из чисел и добавьте его к числу что меньше как минимум на два ( может быть нулевым). Как показывают Айгнер и Триш, эта операция сохраняет свойство быть графическим, поэтому для доказательства теоремы Эрдеша – Галлаи достаточно охарактеризовать графические последовательности, которые максимальны в этом порядке мажорирования. Они дают такую ​​характеристику с точки зрения Диаграммы Феррерса соответствующих разбиений, и покажем, что это эквивалентно теореме Эрдеша – Галлаи.

Графические последовательности для других типов графиков

Подобные теоремы описывают последовательности степеней простых ориентированных графов, простых ориентированных графов с петлями и простых двудольных графов (Бергер 2012). Первая проблема характеризуется Теорема Фулкерсона – Чена – Ансти. Последние два случая, которые эквивалентны, характеризуются Теорема Гейла – Райзера.

Более сильная версия

Трипати и Виджай (2003) доказал, что достаточно рассмотреть -е неравенство такое, что с и для . Barrus et al. (2012) ограничить набор неравенств для графов противоположной направленности. Если положительная последовательность d с четной суммой не имеет повторяющихся записей, кроме максимума и минимума (и длина превышает наибольшую запись), то достаточно проверить только -е неравенство, где .

Обобщение

Конечная последовательность неотрицательных целые числа с является графическим, если четно и существует последовательность это наглядно и мажоритарный . Этот результат был дан Эйгнер и Триеш (1994). Махадев и Пелед (1995) заново изобрел его и дал более прямое доказательство.

Смотрите также

Рекомендации