Обервольфах проблемасы - Oberwolfach problem

Сұрақ, Web Fundamentals.svgМатематикадағы шешілмеген мәселе:
Ол үшін 2 тұрақты -текс сызбалары толық графикті жасай алады көшірілген бөліктерге бөлінеді ?
(математикадағы шешілмеген мәселелер)
Толық графиктің ыдырауы үш данада , енгізу үшін Обервольфах мәселесін шешу

The Обервольфах проблемасы математикада шешілмеген мәселе, ол тамақтанушыларға арналған орындықтарды жоспарлау мәселесі ретінде немесе абстрактілі түрде проблема ретінде тұжырымдалуы мүмкін графтар теориясы, үстінде жиек циклінің қақпақтары туралы толық графиктер. Оның аты аталған Обервольфахтың математикалық зерттеу институты, онда проблема 1967 жылы туындаған Герхард Рингел.[1]

Қалыптастыру

Обервольфахта өткізілген конференцияларда қатысушылар біркелкі емес дөңгелек үстелдері бар бөлмелерде және қатысушыларды тамақтан тамаққа ауыстыратын бөлмеде бірге тамақтануды әдетке айналдырды. Oberwolfach проблемасы берілген кестелер жиынтығына арналған кестені қалай жасау керектігін сұрайды, сонда барлық үстелдер әр тамақтанғанда толып, конференцияға қатысушылардың барлық жұптары дәл бір рет қатар орналасады. Мәселенің данасын келесі деп белгілеуге болады қайда берілген кесте өлшемдері. Сонымен қатар, кестенің кейбір өлшемдері қайталанған кезде, оларды экспоненциалды белгілерді қолдану арқылы белгілеуге болады; мысалы, бес өлшемді үш кестесі бар дананы сипаттайды.[1]

Графтар теориясындағы проблема ретінде тұжырымдалған, бір тамақ кезінде бір-бірінің қасында отырған жұптар а ретінде ұсынылуы мүмкін бірлескен одақ туралы циклдік графиктер көрсетілген ұзындықтағы, тамақтану үстелдерінің әрқайсысы үшін бір циклмен. Бұл циклдардың бірігуі а 2 тұрақты график, және әрбір 2 тұрақты графиктің осы формасы бар. Егер бұл 2 тұрақты график және бар төбелер, мәселе толық график пе деген сұрақ туындайды көшірмелерінің шеткі-бөлшектік одағы ретінде ұсынылуы мүмкін .[1]

Шешім болу үшін конференцияға қатысушылардың жалпы саны (немесе олардың эквивалентімен кестелердің жалпы сыйымдылығы немесе берілген цикл графиктерінің төбелерінің жалпы саны) тақ сан болуы керек. Себебі әр тамақ кезінде әр қатысушы екі көршісінің қасында отырады, сондықтан әр қатысушының көршілерінің жалпы саны жұп болуы керек және бұл қатысушылардың жалпы саны тақ болғанда ғана мүмкін болады. Мәселе сонымен қатар, тіпті мәндеріне дейін кеңейтілді сұрап, сол үшін , а-дан басқа толық графиктің барлық шеттері тамаша сәйкестік берілген 2 тұрақты графтың көшірмелерімен жабылуы мүмкін. Сияқты менеджмент мәселесі (басқа тамақтану орындары мен үстелдердің орналасуымен байланысты басқа математикалық есеп), есептің бұл нұсқасын асханалар орналастырылған ерлі-зайыптылар, және орындықтар бір-бірінің жанына олардың бір жұбайынан басқа бір рет орналастырылуы керек.[2]

Белгілі нәтижелер

Oberwolfach проблемасының шешілмейтіні белгілі жалғыз жағдайлар , , , және [3]. Барлық басқа инстанциялардың шешімі бар деген пікір кең таралған, бірақ ерекше жағдайлардың ғана шешілетіндігі дәлелденген.

Шешімі белгілі болған жағдайларға мыналар жатады:

  • Барлық инстанциялар қоспағанда және .[4][5][6][7][2]
  • Барлық циклдардың ұзындығы бірдей болатын барлық жағдайлар.[4][8]
  • Барлық даналар (белгілі ерекшеліктерден басқа) .[9][3]
  • Белгілі бір таңдау үшін барлық жағдайлар , натурал сандардың шексіз жиындарына жататын.[10][11]
  • Барлық инстанциялар белгілі ерекшеліктерден басқа және .[12]

Байланысты проблемалар

Киркманның мектеп оқушысы проблемасы, он бес оқушы қызды үш-үштен қатарға жеті жолмен топтастыру, осылайша әр үштен бір рет қыздардың жұбы пайда болуы - Обервольфах проблемасының ерекше жағдайы, . Проблемасы Гамильтондық ыдырау толық график бұл тағы бір ерекше жағдай, .[8]

Альпахтың болжамдары, толық графиктің берілген өлшемдердің циклдеріне ыдырауы бойынша, Обервольфах мәселесімен байланысты, бірақ екіншісі де ерекше жағдай емес. дегеніміз - 2 тұрақты график белгілі бір ұзындықтағы циклдардың бөлінуінен пайда болған шыңдар, содан кейін Обервольфах мәселесінің шешімі толық графтың ыдырауын да қамтамасыз етеді циклдарының әрқайсысының көшірмелері . Алайда, әрқайсысының ыдырауы емес әрбір өлшемдегі көптеген циклдарды дисконтталған циклдарға топтастыруға болады, олардың көшірмелерін құрайды Екінші жағынан, Альпахтың болжамының кез-келген нұсқасында циклдар жиынтығы болмайды әр циклдің көшірмелері.

Әдебиеттер тізімі

  1. ^ а б c Ленц, Ханфрид; Рингел, Герхард (1991), «Эгмонт Кёлердің математикалық жұмысына қысқаша шолу», Дискретті математика, 97 (1–3): 3–16, дои:10.1016 / 0012-365X (91) 90416-Y, МЫРЗА  1140782
  2. ^ а б Хуанг, Шарлотта; Котциг, Антон; Роза, Александр (1979), «Обервольфах мәселесінің вариациясы туралы», Дискретті математика, 27 (3): 261–277, дои:10.1016 / 0012-365X (79) 90162-6, МЫРЗА  0541472
  3. ^ а б Саласса, Ф .; Драготто, Г .; Траетта, Т .; Буратти, М .; Делла Кроче, Ф. (2019), Комбинаторлық дизайн мен оңтайландыруды біріктіру: Обервольфах мәселесі, arXiv:1903.12112, Бибкод:2019arXiv190312112S
  4. ^ а б Хаггквист, Роланд (1985), «Циклдің ыдырауы туралы лемма», Графиктердегі циклдар (Burnaby, BC, 1982), Солтүстік-Голландия математикасы. Stud., 115, Амстердам: Солтүстік-Голландия, 227–232 б., дои:10.1016 / S0304-0208 (08) 73015-9, МЫРЗА  0821524
  5. ^ Альпах, Брайан; Хаггквист, Роланд (1985), «Обервольфах мәселесіне қатысты кейбір ескертулер», Графикалық теория журналы, 9 (1): 177–187, дои:10.1002 / jgt.3190090114, МЫРЗА  0785659
  6. ^ Альпах, Брайан; Шелленберг, П.Ж .; Стинсон, Д.Р.; Вагнер, Дэвид (1989), «Оберволфах мәселесі және біркелкі тақ ұзындық циклдерінің факторлары», Комбинаторлық теория журналы, А сериясы, 52 (1): 20–43, дои:10.1016/0097-3165(89)90059-9, МЫРЗА  1008157
  7. ^ Гофман, Д.Г .; Шелленберг, П.Ж. (1991), «Болуы -факторизациялары ", Дискретті математика, 97 (1–3): 243–250, дои:10.1016 / 0012-365X (91) 90440-D, МЫРЗА  1140806
  8. ^ а б Брайант, Даррин; Данцигер, Питер (2011), «Екі факторлы факторизация туралы және Обервольфах проблемасы » (PDF), Графикалық теория журналы, 68 (1): 22–37, дои:10.1002 / jgt.20538, МЫРЗА  2833961
  9. ^ Деза, А .; Фрэнек, Ф .; Хуа, В .; Меска М .; Роза, А. (2010), «18-ден 40-қа дейін тапсырыс бойынша Обервольфах мәселесін шешу» (PDF), Комбинаторлық математика және комбинациялық есептеу журналы, 74: 95–102, МЫРЗА  2675892
  10. ^ Брайант, Даррин; Шарашкин, Виктор (2009), «Шексіз тапсырыстар жиынтығы үшін Обервольфах мәселесінің толық шешімдері», Комбинаторлық теория журналы, B сериясы, 99 (6): 904–918, дои:10.1016 / j.jctb.2009.03.003, МЫРЗА  2558441
  11. ^ Альпах, Брайан; Брайант, Даррин; Хорси, Даниэль; Maenhaut, Барбара; Шарашкин, Виктор (2016), «Толық графиканы циркуляциялық графикаға факторизациялау және Обервольфах мәселесі туралы», Ars Mathematica Contemporanea, 11 (1): 157–173, arXiv:1411.6047, дои:10.26493/1855-3974.770.150, МЫРЗА  3546656
  12. ^ Траетта, Томмасо (2013), «Екі кестелік Обервольфах мәселелерін толық шешу», Комбинаторлық теория журналы, А сериясы, 120 (5): 984–997, дои:10.1016 / j.jcta.2013.01.003, МЫРЗА  3033656