Проблема Обервольфаха
Нерешенная задача по математике :
Для каких 2-регулярных -вершинных графов можно разложить полный граф на рёберно-непересекающиеся копии ? н {\displaystyle n} Г {\displaystyle G} К н {\displaystyle K_{n}} Г {\displaystyle G}
(еще нерешенные проблемы по математике)
Разложение полного графа на три копии , решение задачи Обервольфаха для входных данных К 7 {\displaystyle K_{7}} С 3 + С 4 {\displaystyle C_{3}+C_{4}} ( 3 , 4 ) {\displaystyle (3,4)}

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

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

На конференциях, проводимых в Обервольфахе, участники обычно обедают вместе в комнате с круглыми столами, не все одинакового размера, и с назначенными местами, которые переставляют участников от приема пищи к приему пищи. Задача Обервольфаха заключается в том, как составить схему рассадки для заданного набора столов так, чтобы все столы были заняты во время каждого приема пищи, и все пары участников конференции сидели рядом друг с другом ровно один раз. Пример задачи можно обозначить как где даны размеры столов. В качестве альтернативы, когда некоторые размеры столов повторяются, их можно обозначить с помощью экспоненциальной записи; например, описывает пример с тремя столами размера пять. [1] О П ( х , у , з , … ) {\displaystyle OP (x,y,z,\dots)} х , у , з , … {\displaystyle x,y,z,\точки} О П ( 5 3 ) {\displaystyle ОП(5^{3})}

Сформулированная как задача в теории графов, пары людей, сидящих рядом друг с другом за одним обедом, могут быть представлены как несвязное объединение циклических графов указанной длины, с одним циклом для каждого из обеденных столов. Это объединение циклов является 2 - регулярным графом, и каждый 2-регулярный граф имеет эту форму. Если является этим 2-регулярным графом и имеет вершины, вопрос заключается в том, может ли полный граф порядка быть представлен как рёберно-несвязное объединение копий . [1] С х + С у + С з + ⋯ {\displaystyle C_{x}+C_{y}+C_{z}+\cdots } G {\displaystyle G} n {\displaystyle n} K n {\displaystyle K_{n}} n {\displaystyle n} G {\displaystyle G}

Для того чтобы решение существовало, общее число участников конференции (или, что эквивалентно, общая вместимость столов или общее число вершин заданных циклических графов) должно быть нечетным числом. Так как за каждым приемом пищи каждый участник сидит рядом с двумя соседями, поэтому общее число соседей каждого участника должно быть четным, и это возможно только тогда, когда общее число участников нечетное. Однако задача была также расширена до четных значений путем вопроса для тех , могут ли все ребра полного графа, за исключением идеального паросочетания , быть покрыты копиями заданного 2-регулярного графа. Как и в задаче о меню (другая математическая задача, включающая рассадку обедающих и столов), этот вариант задачи можно сформулировать, предположив, что обедающие организованы в супружеские пары, и что рассадка должна размещать каждого обедающего рядом с каждым обедающим, за исключением его собственного супруга, ровно один раз. [2] n {\displaystyle n} n {\displaystyle n} n {\displaystyle n} n / 2 {\displaystyle n/2}

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

Единственными примерами проблемы Обервольфаха, которые, как известно, неразрешимы, являются , , , и . [3] Широко распространено мнение, что все остальные примеры имеют решение. Эта гипотеза подтверждается недавними неконструктивными и асимптотическими решениями для больших полных графов порядка, превышающего нижнюю границу, которая, однако, не поддается количественному определению. [4] [5] O P ( 3 2 ) {\displaystyle OP(3^{2})} O P ( 3 4 ) {\displaystyle OP(3^{4})} O P ( 4 , 5 ) {\displaystyle OP(4,5)} O P ( 3 , 3 , 5 ) {\displaystyle OP(3,3,5)}

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

  • Все случаи , кроме и . [6] [7] [8] [9] [2] O P ( x y ) {\displaystyle OP(x^{y})} O P ( 3 2 ) {\displaystyle OP(3^{2})} O P ( 3 4 ) {\displaystyle OP(3^{4})}
  • Все случаи, в которых все циклы имеют четную длину. [6] [10]
  • Все случаи (кроме известных исключений) с . [11] [3] n ≤ 60 {\displaystyle n\leq 60}
  • Все примеры для определенных выборов , принадлежащих бесконечным подмножествам натуральных чисел . [12] [13] n {\displaystyle n}
  • Все случаи, кроме известных исключений и . [14] O P ( x , y ) {\displaystyle OP(x,y)} O P ( 3 , 3 ) {\displaystyle OP(3,3)} O P ( 4 , 5 ) {\displaystyle OP(4,5)}

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

Гипотеза Олспаха о разложении полного графа на циклы заданных размеров связана с проблемой Обервольфаха, но ни одна из них не является частным случаем другой. Если — 2-регулярный граф с вершинами, образованный из несвязного объединения циклов определенных длин, то решение проблемы Обервольфаха для также даст разложение полного графа на копии каждого из циклов . Однако не каждое разложение на такое количество циклов каждого размера можно сгруппировать в несвязные циклы, которые образуют копии , и, с другой стороны, не каждый пример гипотезы Олспаха включает наборы циклов, которые имеют копии каждого цикла. G {\displaystyle G} n {\displaystyle n} G {\displaystyle G} ( n − 1 ) / 2 {\displaystyle (n-1)/2} G {\displaystyle G} K n {\displaystyle K_{n}} G {\displaystyle G} ( n − 1 ) / 2 {\displaystyle (n-1)/2}

Ссылки

  1. ^ abc Lenz, Hanfried ; Ringel, Gerhard (1991), "Краткий обзор математических работ Эгмонта Кёлера", Discrete Mathematics , 97 (1–3): 3–16, doi : 10.1016/0012-365X(91)90416-Y , MR  1140782
  2. ^ ab Хуан, Шарлотта; Коциг, Антон ; Роза, Александр (1979), «О вариации задачи Обервольфаха», Дискретная математика , 27 (3): 261–277, doi : 10.1016/0012-365X(79)90162-6 , MR  0541472
  3. ^ ab Саласса, Ф.; Драготто, Г.; Траэтта, Т.; Буратти, М.; Делла Кроче, Ф. (2019), Объединение комбинаторного проектирования и оптимизации: задача Обервольфаха , arXiv : 1903.12112 , Bibcode : 2019arXiv190312112S
  4. ^ Глок, Стефан; Йос, Феликс; Ким, Джэхун; Кюн, Даниэла ; Остхус, Дерик (2021), «Решение проблемы Обервольфаха», Журнал Европейского математического общества , 23 (8): 2511–2547, arXiv : 1806.04644 , doi : 10.4171/jems/1060, MR  4269420
  5. ^ Киваш, Питер ; Штаден, Кэтрин (2022), «Обобщенная задача Обервольфаха» (PDF) , Журнал комбинаторной теории , Серия B, 152 : 281–318, arXiv : 2004.09937 , doi : 10.1016/j.jctb.2021.09.007, MR  4332743
  6. ^ ab Häggkvist, Roland (1985), "Лемма о разложении циклов", Cycles in graphs (Burnaby, BC, 1982) , North-Holland Math. Stud., т. 115, Амстердам: North-Holland, стр. 227–232, doi :10.1016/S0304-0208(08)73015-9, ISBN 978-0-444-87803-8, МР  0821524
  7. ^ Alspach, Brian ; Häggkvist, Roland (1985), «Некоторые наблюдения над проблемой Обервольфаха», Journal of Graph Theory , 9 (1): 177–187, doi :10.1002/jgt.3190090114, MR  0785659
  8. ^ Alspach, Brian ; Schellenberg, PJ; Stinson, DR ; Wagner, David (1989), «Проблема Обервольфаха и факторы равномерных нечетных циклов», Journal of Combinatori Theory , Series A, 52 (1): 20–43, doi :10.1016/0097-3165(89)90059-9, MR  1008157
  9. ^ Хоффман, Д.Г.; Шелленберг, П.Дж. (1991), «Существование -факторизаций » , Дискретная математика , 97 (1–3): 243–250, doi : 10.1016/0012-365X(91)90440-D , MR  1140806 C k {\displaystyle C_{k}} K 2 n − F {\displaystyle K_{2n}-F}
  10. ^ ab Брайант, Даррин; Данцигер, Питер (2011), «О двудольных 2-факторизациях K n − I {\displaystyle K_{n}-I} и проблеме Обервольфаха» (PDF) , Журнал теории графов , 68 (1): 22–37, doi :10.1002/jgt.20538, MR  2833961
  11. ^ Деза, А.; Франек, Ф.; Хуа, В.; Мешка, М.; Роза, А. (2010), «Решения проблемы Обервольфаха для порядков от 18 до 40» (PDF) , Журнал комбинаторной математики и комбинаторных вычислений , 74 : 95–102, MR  2675892
  12. ^ Брайант, Даррин; Шарашкин, Виктор (2009), «Полные решения проблемы Обервольфаха для бесконечного множества порядков», Журнал комбинаторной теории , Серия B, 99 (6): 904–918, doi :10.1016/j.jctb.2009.03.003, MR  2558441
  13. ^ Alspach, Brian ; Bryant, Darryn; Horsley, Daniel; Maenhaut, Barbara; Scharaschkin, Victor (2016), «О факторизациях полных графов в циркулянтные графы и проблеме Обервольфаха», Ars Mathematica Contemporanea , 11 (1): 157–173, arXiv : 1411.6047 , doi : 10.26493/1855-3974.770.150, MR  3546656
  14. ^ Траэтта, Томмазо (2013), «Полное решение двухтабличных задач Обервольфаха», Журнал комбинаторной теории , Серия A, 120 (5): 984–997, doi : 10.1016/j.jcta.2013.01.003 , MR  3033656
Retrieved from "https://en.wikipedia.org/w/index.php?title=Oberwolfach_problem&oldid=1243011020"