Обервольфах проблема

Разложение полного графа на три копии , решение задачи Обервольфаха для входных данных.${\ displaystyle K_ {7}}$${\ displaystyle C_ {3} + C_ {4}}$${\ displaystyle (3,4)}$

Проблема Обервольф нерешенная проблема в математике , которые могут быть приготовлены либо в виде задачи планирования , вмещающие заданий для посетителей, или более абстрактно , как проблема в теории графов , на крышках краев цикла из полных графов . Он назван в честь Института математических исследований в Обервольфахе , где проблема была поставлена ​​в 1967 году Герхардом Рингелем . ^[1]

Формулировка [ править ]

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

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

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

Известные результаты [ править ]

Единственные экземпляры проблемы Oberwolfach которые , как известно , не разрешимы являются , , , и ^[3] . Широко распространено мнение, что во всех других случаях есть решение, но доказано, что только частные случаи разрешимы.${\ displaystyle OP (3 ^ {2})}$${\ displaystyle OP (3 ^ {4})}$${\ displaystyle OP (4,5)}$${\ displaystyle OP (3,3,5)}$

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

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

Связанные проблемы [ править ]

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

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

Ссылки [ править ]