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

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

Нерешённые проблемы математики: Для любого ли 2-регулярного графа с вершинами полный граф может быть разложен на непересекающиеся по рёбрам копии графа ?
Разложение полного графа на три копии графа , что решает задачу Обервольфаха для данных

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

На конференциях, проводимых в Обервольфахе, принято обедать вместе в зале с круглыми столами, не все из которых имеют один и тот же размер, а места за столами меняются от обеда к обеду. Задача Обервольфаха спрашивает, как задать распределение мест за столами, чтобы все места были заняты и все пары участников конференции сидели рядом только раз. Экземпляр задачи можно обозначить как , где задаёт размеры столов. Альтернативно, когда некоторые размеры столов повторяются, это может отражаться как верхний индекс, например описывает задачу с тремя столами на пять мест[1].

При формулировке задачи как задачи теории графов пары людей, сидящих рядом за конкретным обедом, могут быть представлены как объединение непересекающихся (по рёбрам) циклов определённой длины, по одному циклу для каждого обеденного стола. Это объединение циклов является 2-регулярным графом, а любой 2-регулярный граф имеет такой вид. Если является таким 2-регулярным графом и имеет вершин, вопрос ставится так: можно ли полный граф представить как непересекающееся по рёбрам объединение копий графа [1].

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

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

Известны только следующие экземпляры задачи Обервольфаха, о которых известно, что они не имеют решения: , , и . Широко распространено мнение, что все другие экземпляры решения имеют, но пока доказана разрешимость лишь специальных случаев.

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

  • Все экземпляры , за исключением и [3][4][5][6][2].
  • Все экземпляры, в которых все циклы имеют чётную длину[3][7].
  • Все экземпляры (кроме известных исключений) с [8].
  • Все экземпляры для некоторых , принадлежащих бесконечному набору простых чисел[9][10].
  • Все экземпляры , кроме известных исключений и [11].

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

  • Задача Киркмана о школьницах: группировки пятнадцати школьниц в ряды по три семью различными способами, так что каждая пара девочек оказывалась в тройке только раз, является частным случаем задачи Обервольфаха . Задача гамильтонова разложения полного графа является другим частным случаем [7].
  • Гипотеза Алспаха о разложении полного графа на циклы данных размеров связана с задачей Обервольфаха, но они не являются частными случаями друг друга. Если является 2-регулярным графом с вершинами, образованным непересекающимися циклами определённой длины, то решение задачи Обервольфаха для даёт разложение полного графа на копий каждого цикла графа . Однако не любое разложение на такое число циклов каждого размера может быть сгруппировано на непересекающиеся циклы, которые образуют копии , но, с другой стороны, не любой экземпляр гипотезы Алспаха вовлекает набор циклов, которые имеют копий каждого цикла.

Примечания

  1. 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.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.