Теорема Посы

Теорема Поши в теории графов является достаточным условием существования гамильтонова цикла , основанным на степенях вершин в неориентированном графе. Она влечет за собой два других достаточных условия, основанных на степенях, теорему Дирака о гамильтоновых циклах и теорему Оре . В отличие от этих условий, ее можно применять к графам с небольшим числом вершин низкой степени. Она названа в честь Лайоша Поши , ученика Пауля Эрдёша, родившегося в 1947 году, который открыл эту теорему в 1962 году.

Условие Посы для конечного неориентированного графа, имеющего вершины, требует, чтобы, если степени вершин в порядке возрастания${\displaystyle G}$${\displaystyle n}$${\displaystyle n}$

${\displaystyle d_{1}\leq d_{2}\leq ...\leq d_{n},}$

тогда для каждого индекса неравенство выполняется.${\displaystyle к<н/2}$${\displaystyle к<d_{к}}$

Теорема Посы утверждает, что если конечный неориентированный граф удовлетворяет условию Посы, то в этом графе есть гамильтонов цикл.

• Поса, Л. (1962), «Теорема о линиях Гамильтона», Magyar Tud. Акад. Мат. Кутато Междунар. Кёзл. , 7 : 225–226 , МР  0184876
• Катона-Речски-Сабо: A számítástudomány alapjai , Typotex, Будапешт, 2003 г. (Курс венгерского бакалавриата).
• Кронк, Хадсон В. (1969), «Обобщение теоремы Посы», Труды Американского математического общества , 21 (1): 77– 78, doi :10.2307/2036861, JSTOR  2036861, MR  0237377
• Кюн, Даниэла ; Остхус, Дерик ; Треглоун, Эндрю (2009), "Последовательности степеней, вызывающие циклы Гамильтона в ориентированных графах", Европейская конференция по комбинаторике, теории графов и приложениям (EuroComb 2009) , Electron. Notes Discrete Math., т. 34, Амстердам: Elsevier Sci. BV, стр.  347–351 , doi :10.1016/j.endm.2009.07.057, MR  2591466
• Инь, Цзянь-Хуа; Чжан, Юэ (2011), «Условие Посы и нигде не нулевые 3-потоки», Дискретная математика , 311 (12): 897– 907, doi :10.1016/j.disc.2011.02.023, MR  2787300

• Вайсштейн, Эрик В. , «Теорема Посы», MathWorld
• О теореме Посы