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

Розклад повного графа $K_7$ на три копії графа $C_3+C_4$, що розв'язує задачу Обервольфаха для даних $(3,4)$

Зада́ча Обервольфаха — це нерозв'язана математична задача, яку можна сформулювати як задачу розподілу місць для обідів, або, абстрактніше, як задачу теорії графів про покриття циклами ребер повних графів. Назва задачі походить від назви математичного інституту Обервольфаха, де її сформулював 1967 року Шаблон:НпШаблон:R.

Формулювання

На конференціях, що проводяться в Обервольфасі, прийнято обідати разом у залі з круглими столами, не всі з яких мають однаковий розмір, а місця за столами змінюються від обіду до обіду. Задача Обервольфаха запитує, як задати розподіл місць за столами, щоб усі місця були зайняті та всі пари учасників конференції сиділи поряд лише раз. Примірник задачі можна позначити як $OP(x,y,z,\dots )$, де $x,y,z,\dots$ задає розміри столів. Альтернативно, коли деякі розміри столів повторюються, це може позначатись як верхній індекс, наприклад $OP(5^3)$ описує задачу з трьома столами на п'ять місцьШаблон:R.

При формулюванні задачі як задачі теорії графів пари людей, що сидять поруч за конкретним обідом, можна подати як Шаблон:Не перекладено циклів $C_x+C_y+C_z+\cdots$ певної довжини, по одному циклу для кожного обіднього столу. Це об'єднання циклів є 2-регулярним графом, а будь-який 2-регулярний граф має такий вигляд. Якщо $G$ є таким 2-регулярним графом та має $n$ вершин, питання ставлять так: чи можна повний граф $K_n$ подати як об'єднання копій графа, що не перетинаються по ребрах $G$Шаблон:R.

Щоб розв'язок існував, загальна кількість учасників конференції (або, еквівалентно, повна кількість посадкових місць за столами, або загальна кількість вершин заданих циклів) має бути непарним числом. За кожним обідом учасник сидить поруч із двома іншими учасниками, отже загальна кількість сусідів кожного учасника має бути парним, але це можливо лише за непарному загальному числі учасників. Завдання, однак, можна поширити й на парні значення $n$, якщо питати для цих $n$, чи можна покрити всі ребра повного графа за винятком досконалого парування копіями заданого 2-регулярного графа. Подібно до задачі про подружні пари (іншої математичної задачі про розсаджування за обіднім столом), цей варіант задачі можна сформулювати в припущенні, що $n$ учасників обіду розбивається на $n/2$ подружніх пар, і що кожен учасник повинен пообідати рівно раз з кожним іншим учасником, за винятком подружжяШаблон:R.

Відомі результати

Відомі лише такі екземпляри завдання Обервольфаха, про які відомо, що вони не мають розв'язку: $OP(3^2)$, $OP(3^4)$, $OP(4,5)$ і $OP(3,3,5)$. Поширена думка, що решта екземплярів розв'язки мають, але поки що доведено розв'язність лише спеціальних випадків.

Випадки, для яких відомі розв'язки:

• Усі примірники $OP(x^y)$, за винятком $OP(3^2)$ і $OP(3^4)$Шаблон:R.
• Усі примірники, в яких усі цикли мають парну довжинуШаблон:R.
• Усі примірники (крім відомих винятків) з $n⩽40$Шаблон:R.
• Усі примірники для деяких $n$, що належать нескінченному набору простих чиселШаблон:R.
• Усі примірники $OP(x,y)$ крім відомих винятків $OP(3,3)$ і $OP(4,5)$Шаблон:R.

Пов'язані задачі

• Задача Кіркмана про школярок: групування п'ятнадцяти школярок у ряди по три сімома різними способами, так щоб кожна пара дівчаток опинялася в трійці тільки раз, є окремим випадком завдання Обервольфаха $OP(3^5)$ . Задача гамільтонова розкладання повного графа $K_n$ є іншим окремим випадком $OP(n)$Шаблон:R.
• Гіпотеза Алспаха про розкладання повного графа на цикли даних розмірів пов'язана із задачею Обервольфаха, але вони не є окремими випадками одна одної. Якщо $G$ є 2-регулярним графом з $n$ вершинами, утвореними не перетинними циклами певної довжини, то розв'язок задачі Обервольфаха для $G$ дає розклад повного графа на $(n-1)/2$ копій кожного циклу графа $G$. Однак не будь-який розклад $K_n$ на таке число циклів кожного розміру можна згрупувати на цикли, що не перетинаються, які утворюють копії $G$, але, з іншого боку, не будь-який екземпляр гіпотези Алспаха залучає набір циклів, які мають $(n-1)/2$ копій кожного циклу.