Задача Обервольфаха

Нерешённые проблемы математики: Для любого ли 2-регулярного графа $G$ с $n$ вершинами полный граф $K_{n}$ может быть разложен на непересекающиеся по рёбрам копии графа $G$?

Разложение полного графа $K_{7}$ на три копии графа $C_{3}+C_{4}$, что решает задачу Обервольфаха для данных $(3,4)$

Задача Обервольфаха — это нерешённая математическая задача, которую можно сформулировать как задачу распределения мест для обедов, или, более абстрактно, как задачу теории графов о покрытиях циклами рёбер полных графов. Задача получила название по имени математического института Обервольфаха, где задачу сформулировал в 1967 году Герхард Рингель.

Формулировка

На конференциях, проводимых в Обервольфахе, принято обедать вместе в зале с круглыми столами, не все из которых имеют один и тот же размер, а места за столами меняются от обеда к обеду. Задача Обервольфаха спрашивает, как задать распределение мест за столами, чтобы все места были заняты и все пары участников конференции сидели рядом только раз. Экземпляр задачи можно обозначить как $OP(x,y,z,\dots )$, где $x,y,z,\dots$ задаёт размеры столов. Альтернативно, когда некоторые размеры столов повторяются, это может отражаться как верхний индекс, например $OP(5^{3})$ описывает задачу с тремя столами на пять мест.

При формулировке задачи как задачи теории графов пары людей, сидящих рядом за конкретным обедом, могут быть представлены как объединение непересекающихся (по рёбрам) циклов $C_{x}+C_{y}+C_{z}+\cdots$ определённой длины, по одному циклу для каждого обеденного стола. Это объединение циклов является 2-регулярным графом, а любой 2-регулярный граф имеет такой вид. Если $G$ является таким 2-регулярным графом и имеет $n$ вершин, вопрос ставится так: можно ли полный граф $K_{n}$ представить как непересекающееся по рёбрам объединение копий графа $G$.

Чтобы решение существовало, общее число участников конференции (или, эквивалентно, полное число посадочных мест за столами, или общее число вершин заданных циклов) должно быть нечётным числом. За каждым обедом участник сидит рядом с двумя другими участниками, так что общее число соседей каждого участника должно быть чётным, а это возможно только при нечётном общем числе участников. Задачу, однако, можно распространить и на чётные значения $n$, если спрашивать для этих $n$, можно ли покрыть все рёбра полного графа за исключением совершенного паросочетания копиями заданного 2-регулярного графа. Подобно задаче о супружеских парах (другой математической задаче о рассаживании за обеденным столом), этот вариант задачи можно сформулировать в предположении, что $n$ участников обеда разбивается на $n/2$ супружеских пар, и что каждый участник должен пообедать ровно раз с каждым другим участником, за исключением супруги (супруга).

Известные результаты

Известны только следующие экземпляры задачи Обервольфаха, о которых известно, что они не имеют решения: $OP(3^{2})$, $OP(3^{4})$, $OP(4,5)$ и $OP(3,3,5)$. Широко распространено мнение, что все другие экземпляры решения имеют, но пока доказана разрешимость лишь специальных случаев.

Случаи, для которых известны решения:

• Все экземпляры $OP(x^{y})$, за исключением $OP(3^{2})$ и $OP(3^{4})$.
• Все экземпляры, в которых все циклы имеют чётную длину.
• Все экземпляры (кроме известных исключений) с $n\leqslant 40$.
• Все экземпляры для некоторых $n$, принадлежащих бесконечному набору простых чисел.
• Все экземпляры $OP(x,y)$, кроме известных исключений $OP(3,3)$ и $OP(4,5)$.

Связанные задачи

• Задача Киркмана о школьницах: группировки пятнадцати школьниц в ряды по три семью различными способами, так что каждая пара девочек оказывалась в тройке только раз, является частным случаем задачи Обервольфаха $OP(3^{5})$. Задача гамильтонова разложения полного графа $K_{n}$ является другим частным случаем $OP(n)$.

• Гипотеза Алспаха о разложении полного графа на циклы данных размеров связана с задачей Обервольфаха, но они не являются частными случаями друг друга. Если $G$ является 2-регулярным графом с $n$ вершинами, образованным непересекающимися циклами определённой длины, то решение задачи Обервольфаха для $G$ даёт разложение полного графа на $(n-1)/2$ копий каждого цикла графа $G$. Однако не любое разложение $K_{n}$ на такое число циклов каждого размера может быть сгруппировано на непересекающиеся циклы, которые образуют копии $G$, но, с другой стороны, не любой экземпляр гипотезы Алспаха вовлекает набор циклов, которые имеют $(n-1)/2$ копий каждого цикла.