Задача Обервольфаха
Нерозв'язана проблема математики: Чи для будь-якого 2-регулярного графа з вершинами повний граф можна розкласти на неперетинні по ребрах копії графа ? (більше нерозв'язаних проблем математики)
|
Зада́ча Обервольфаха — це нерозв'язана математична задача, яку можна сформулювати як задачу розподілу місць для обідів, або, абстрактніше, як задачу теорії графів про покриття циклами ребер повних графів. Назва задачі походить від назви математичного інституту Обервольфаха, де її сформулював 1967 року Герхард Рінгель[ru][1].
Формулювання
ред.На конференціях, що проводяться в Обервольфасі, прийнято обідати разом у залі з круглими столами, не всі з яких мають однаковий розмір, а місця за столами змінюються від обіду до обіду. Задача Обервольфаха запитує, як задати розподіл місць за столами, щоб усі місця були зайняті та всі пари учасників конференції сиділи поряд лише раз. Примірник задачі можна позначити як , де задає розміри столів. Альтернативно, коли деякі розміри столів повторюються, це може позначатись як верхній індекс, наприклад описує задачу з трьома столами на п'ять місць[1].
При формулюванні задачі як задачі теорії графів пари людей, що сидять поруч за конкретним обідом, можна подати як об'єднання неперетинних (по ребрах)[en] циклів певної довжини, по одному циклу для кожного обіднього столу. Це об'єднання циклів є 2-регулярним графом, а будь-який 2-регулярний граф має такий вигляд. Якщо є таким 2-регулярним графом та має вершин, питання ставлять так: чи можна повний граф подати як об'єднання копій графа, що не перетинаються по ребрах [1].
Щоб розв'язок існував, загальна кількість учасників конференції (або, еквівалентно, повна кількість посадкових місць за столами, або загальна кількість вершин заданих циклів) має бути непарним числом. За кожним обідом учасник сидить поруч із двома іншими учасниками, отже загальна кількість сусідів кожного учасника має бути парним, але це можливо лише за непарному загальному числі учасників. Завдання, однак, можна поширити й на парні значення , якщо питати для цих , чи можна покрити всі ребра повного графа за винятком досконалого парування копіями заданого 2-регулярного графа. Подібно до задачі про подружні пари (іншої математичної задачі про розсаджування за обіднім столом), цей варіант задачі можна сформулювати в припущенні, що учасників обіду розбивається на подружніх пар, і що кожен учасник повинен пообідати рівно раз з кожним іншим учасником, за винятком подружжя[2].
Відомі результати
ред.Відомі лише такі екземпляри завдання Обервольфаха, про які відомо, що вони не мають розв'язку: , , і . Поширена думка, що решта екземплярів розв'язки мають, але поки що доведено розв'язність лише спеціальних випадків.
Випадки, для яких відомі розв'язки:
Пов'язані задачі
ред.- Задача Кіркмана про школярок: групування п'ятнадцяти школярок у ряди по три сімома різними способами, так щоб кожна пара дівчаток опинялася в трійці тільки раз, є окремим випадком завдання Обервольфаха . Задача гамільтонова розкладання повного графа є іншим окремим випадком [7].
- Гіпотеза Алспаха про розкладання повного графа на цикли даних розмірів пов'язана із задачею Обервольфаха, але вони не є окремими випадками одна одної. Якщо є 2-регулярним графом з вершинами, утвореними не перетинними циклами певної довжини, то розв'язок задачі Обервольфаха для дає розклад повного графа на копій кожного циклу графа . Однак не будь-який розклад на таке число циклів кожного розміру можна згрупувати на цикли, що не перетинаються, які утворюють копії , але, з іншого боку, не будь-який екземпляр гіпотези Алспаха залучає набір циклів, які мають копій кожного циклу.
Примітки
ред.- ↑ а б в Hanfried Lenz, Gerhard Ringel. A brief review on Egmont Köhler's mathematical work // Discrete Mathematics. — 1991. — Т. 97, вип. 1—3. — С. 3–16. — DOI:10.1016/0012-365X(91)90416-Y.
- ↑ а б Charlotte Huang, Anton Kotzig, Alexander Rosa. On a variation of the Oberwolfach problem // Discrete Mathematics. — 1979. — Т. 27, вип. 3. — С. 261–277. — DOI:10.1016/0012-365X(79)90162-6.
- ↑ а б Roland Häggkvist. A lemma on cycle decompositions // Cycles in graphs (Burnaby, B.C., 1982). — North-Holland, 1985. — Т. 115. — С. 227–232. — (North-Holland Math. Stud.). — DOI:10.1016/S0304-0208(08)73015-9.
- ↑ Brian Alspach, Roland Häggkvist. Some observations on the Oberwolfach problem // Journal of Graph Theory. — 1985. — Т. 9, вип. 1. — С. 177–187. — DOI:10.1002/jgt.3190090114.
- ↑ Brian Alspach, Schellenberg P. J., Stinson D. R., David Wagner. The Oberwolfach problem and factors of uniform odd length cycles // Journal of Combinatorial Theory. — 1989. — Т. 52, вип. 1. — С. 20–43. — DOI:10.1016/0097-3165(89)90059-9.
- ↑ Hoffman D. G., Schellenberg P. J. The existence of -factorizations of // Discrete Mathematics. — 1991. — Т. 97, вип. 1—3. — С. 243–250. — DOI:10.1016/0012-365X(91)90440-D.
- ↑ а б Darryn Bryant, Peter Danziger. On bipartite 2-factorizations of and the Oberwolfach problem // Journal of Graph Theory. — 2011. — Т. 68, вип. 1. — С. 22–37. — DOI:10.1002/jgt.20538.
- ↑ Deza A., Franek F., Hua W., Meszka M., Rosa A. Solutions to the Oberwolfach problem for orders 18 to 40 // Journal of Combinatorial Mathematics and Combinatorial Computing. — 2010. — Т. 74. — С. 95–102.
- ↑ Darryn Bryant, Victor Scharaschkin. Complete solutions to the Oberwolfach problem for an infinite set of orders // Journal of Combinatorial Theory. — 2009. — Т. 99, вип. 6. — С. 904–918. — DOI:10.1016/j.jctb.2009.03.003.
- ↑ Brian Alspach, Darryn Bryant, Daniel Horsley, Barbara Maenhaut, Victor Scharaschkin. On factorisations of complete graphs into circulant graphs and the Oberwolfach problem // Ars Mathematica Contemporanea. — 2016. — Т. 11, вип. 1. — С. 157–173.
- ↑ Tommaso Traetta. A complete solution to the two-table Oberwolfach problems // Journal of Combinatorial Theory. — 2013. — Т. 120, вип. 5. — С. 984–997. — DOI:10.1016/j.jcta.2013.01.003.