Гипотеза Алспаха — это математическая теорема, которая описывает покрытия рёбер непересекающимися циклами полных графов при заданных длинах циклов. Гипотеза названа в честь Брайана Алспаха, который сформулировал её как исследовательскую задачу в 1981 году. В 2014 году Даррин Брайант, Даниэль Хорсли и Уильям Петтерссон опубликовали доказательство теоремы.
Формулировка В этом контексте покрытие рёбер непересекающимися циклами представляет собой набор простых циклов, никакие два из которых не используют одно и то же ребро и которые в совокупности содержат все рёбра графа. Чтобы покрытие рёбер непересекающимися циклами существовало, необходимо, чтобы каждая вершина имела чётную степень, поскольку степень каждой вершины равна удвоенному числу циклов, которые содержат данную вершину, то есть чётное число. А для циклов в покрытии рёбер непересекающимися циклами с данным набором длин необходимо, чтобы сумма длин циклов совпадала с общим числом рёбер в графе. Алспах высказал гипотезу, что для полных графов эти два необходимых условия являются достаточными — если нечётно (так что степени чётны) и задан список длин циклов (все длины которых не превосходят ), имеющий суммарную длину (число рёбер в полном графе), то полный граф можно всегда разложить на циклы заданных длин. Именно это утверждение доказали Брайант, Хорсли и Петтерссон.
Обобщение на чётное число вершин Для полных графов , число вершин которых чётно, Алспах предположил, что всегда можно разложить граф на совершенное паросочетание и набор циклов предписанных длин, дающих общую длину . В этом случае паросочетание исключает нечётность степени каждой вершины, оставляя граф с чётными степенями, и остаётся условие, что сумма длин циклов равна числу оставшихся рёбер. Этот вариант гипотезы Брайант, Хорсли и Петтерссон также доказали.
Связанные проблемы Задача Обервольфаха о разложении полного графа на копии заданного 2-регулярного графа связана с данной задачей, но ни одна из них не является частным случаем другой. Если является 2-регулярным графом с вершинами, образованным объединением непересекающихся циклов определённой длины, то решение задачи Обервольфаха для также даёт разложение полного графа на копий каждого цикла графа . Однако не любое разложение графа на такое число циклов каждого размера может быть сгруппировано в непересекающиеся циклы, которые образуют копии графа , а с другой стороны, не во всех случаях гипотезы Алспаха фигурируют наборы циклов, содержащие копий каждого цикла.
Литература
Примечания
Категория:Теоремы теории графов Категория:Доказанные математические гипотезы