Теорема Эрдеша – Галлаи является результатом теории графов , раздела комбинаторной математики . Она обеспечивает один из двух известных подходов к решению проблемы реализации графа , т.е. дает необходимое и достаточное условие для конечной последовательности из натуральных чисел , чтобы быть последовательностью степени из простого графа . Последовательность, удовлетворяющая этим условиям, называется «графической». Теорема была опубликована в 1960 году Полом Эрдёшем и Тибором Галлаи , в честь которых она названа.
Заявление
Последовательность неотрицательных целых чисел можно представить как последовательность степеней конечного простого графа на n вершинах тогда и только тогда, когда даже и
выполняется для любого k из .
Доказательства
Нетрудно показать, что условия теоремы Эрдеша – Галлаи необходимы для того, чтобы последовательность чисел была наглядной. Требование четности суммы степеней - это лемма о рукопожатии , уже использованная Эйлером в его статье 1736 года о мостах в Кенигсберге . Неравенство между суммойнаибольшие степени и сумма оставшихся степеней могут быть установлены двойным счетом : в левой части указано количество смежностей ребер и вершин среди вершины наивысшей степени, каждая такая смежность должна быть на ребре с одной или двумя конечными точками высокой степени, Член справа дает максимально возможное количество смежностей ребер и вершин, в которых обе конечные точки имеют высокую степень, а оставшийся член в правой верхней границе ограничивает количество ребер, которые имеют ровно одну конечную точку высокой степени. Таким образом, более трудная часть доказательства - показать, что для любой последовательности чисел, удовлетворяющей этим условиям, существует граф, для которого она является последовательностью степеней.
Первоначальное доказательство Erdős & Gallai (1960) было длинным и сложным. Чоудум (1986) цитирует более короткое доказательство Клода Берже , основанное на идеях сетевого потока . Вместо этого Чоудум предоставляет доказательство математической индукции по сумме степеней: он позволяет быть первым индексом числа в последовательности, для которого (или предпоследнее число, если все равны), использует анализ случая, чтобы показать, что последовательность, образованная вычитанием единицы из и от последнего числа в последовательности (и удаления последнего числа, если это вычитание приводит к тому, что оно становится равным нулю) снова является графическим и формирует граф, представляющий исходную последовательность, путем добавления края между двумя позициями, из которых вычиталась единица.
Tripathi, Venugopalan & West (2010) рассматривают последовательность «субреализаций», графов, степени которых ограничены сверху заданной последовательностью степеней. Они показывают, что, если G является субреализацией, а i - наименьший индекс вершины в G , степень которой не равна d i , то G может быть изменен таким образом, чтобы произвести другую субреализацию, увеличивая степень вершины i без изменение степени более ранних вершин в последовательности. Повторяющиеся шаги такого рода должны в конечном итоге привести к реализации заданной последовательности, что доказывает теорему.
Отношение к целочисленным разделам
Айгнер и Триш (1994) описывают тесную связь между теоремой Эрдеша – Галлаи и теорией целочисленных разбиений . Позволять; затем отсортированные целочисленные последовательности суммируются с можно интерпретировать как разбиение . При мажоризации своих префиксных сумм разделы образуют решетку , в которой минимальное изменение между отдельным разделом и другим разделом ниже по порядку разделов состоит в вычитании единицы из одного из чисел. и добавьте его к числу что меньше как минимум на два (может быть нулевым). Как показывают Айгнер и Триш, эта операция сохраняет свойство быть графическим, поэтому для доказательства теоремы Эрдеша – Галлаи достаточно охарактеризовать графические последовательности, которые максимальны в этом порядке мажорирования. Они обеспечивают такую характеристику в терминах диаграмм Феррерса соответствующих разбиений и показывают, что это эквивалентно теореме Эрдеша – Галлаи.
Графические последовательности для других типов графиков
Подобные теоремы описывают последовательности степеней простых ориентированных графов, простых ориентированных графов с петлями и простых двудольных графов ( Berger 2012 ). Первая проблема описывается теоремой Фулкерсона – Чена – Ансти . Последние два случая, которые эквивалентны, характеризуются теоремой Гейла – Райзера .
Более сильная версия
Tripathi & Vijay (2003) доказали, что достаточно рассмотреть-е неравенство такое, что с участием и для . Barrus et al. (2012) ограничивают набор неравенств для графов в противоположном направлении. Если положительная последовательность d с четной суммой не имеет повторяющихся записей, кроме максимума и минимума (и длина превышает самую большую запись), то достаточно проверить только-е неравенство, где .
Обобщение
Конечная последовательность неотрицательных целых чисел с участием является графическим, если четно и существует последовательность это наглядно и мажоритарно . Этот результат был дан Aigner & Triesch (1994) . Махадев и Пелед (1995) заново изобрели это и предоставили более прямое доказательство.
Смотрите также
Рекомендации
- Айгнер, Мартин ; Триеш, Эберхард (1994), «Реализуемость и единственность в графах», Дискретная математика , 136 (1–3): 3–20, DOI : 10.1016 / 0012-365X (94) 00104-Q , MR 1313278.
- Barrus, MD; Hartke, SG; Джао, Кайл Ф .; West, DB (2012), «Пороговые значения длины для графических списков с фиксированными наибольшими и наименьшими записями и ограниченными промежутками» , Дискретная математика , 312 (9): 1494–1501, doi : 10.1016 / j.disc.2011.05.001
- Бергер, Аннабелл (2012), Связь между количеством реализаций для последовательностей степеней и мажоризацией , arXiv : 1212.5443 , Bibcode : 2012arXiv1212.5443B
- Choudum, С. (1986), "Простое доказательство теоремы Эрдеша-Галлаи на графике последовательностей", Бюллетень австралийского математического общества , 33 (1): 67-70, DOI : 10,1017 / S0004972700002872 , МР 0823853.
- Erds, P .; Галлай, Т. (1960), "Графок элőирт фоксзаму понтоккал" (PDF) , Математикаи Лапок , 11 : 264–274
- Махадев, NVR; Пелед, ООН (1995), Пороговые графики и связанные темы , Elsevier
- Трипати, Амитабха; Виджай, Суджит (2003), "Замечание о теореме Эрдеша и Галлаи", Дискретная математика , 265 : 417-420, DOI : 10.1016 / s0012-365x (02) 00886-5 , MR 1969393
- Трипати, Амитабха; Венугопалан, Сушмита; Запад, Douglas B. (2010), "Короткое конструктивное доказательство характеристики Erdős-Галлаи графических списков" , Дискретная математика , 310 (4): 843-844, DOI : 10.1016 / j.disc.2009.09.023 , MR 2574834