Математическая энциклопедия - комбинаторные задачи

класс и ческ незадачи выбора и расположения элементов конечного множества, имеющие в качестве исходной нек-рую формулировку развлекательного содержания типа головоломок.

Одной из классических К. з., фигурирующей еще в мифах Древнего Востока, является построение магического квадрата, т. е. расположение первых n² натуральных чисел в квадрате nxn так, чтобы все суммы по строкам, столбцам и диагоналям были равны одному и тому же числу. Напр.,

магический квадрат при n=3. Известен ряд методов построения таких квадратов (см., напр., [1]). Определение числа магических квадратов порядка ппри n>4 представляет трудную еще нерешенную (1978) задачу. Ряд К. з. был рассмотрен Л. Эйлером (L. Euler). Одна из них задача о 36 офицерах, состоящая в том, чтобы указанное число офицеров 6 различных воинских званий и из 6 различных полков так расположить в ячейках квадрата (каре), чтобы каждая колонна и каждая шеренга содержали одновременно одного и только одного офицера каждого ранга и каждого полка. Квадрат размером содержащий в ячейках элементы 1, 2, . . ., п, наз. латинским, если элементы в каждой строке и каждом столбце различны. Два латинских квадрата наз. ортогональными, если при их наложении все п ² пар элементов в ячейках различны. Задача о 36 офицерах эквивалентна задаче о существовании пары ортогональных латинских кнадратов порядка 6. Л. Эйлер высказал гипотезу о несуществовании ортогональных латинских квадратов порядка n=4k+2, k=l, 2, ... В 1900 Г. Тарри (G. Tarry) подтвердил эту гипотезу для п=6. и тем самым доказал, что задача о 36 офицерах не имеет решения. В 1959-60 была доказана теорема о существовании пары ортогональных латинских квадратов для каждого n=4k+2, k= 2,3, ... (см. [2]).

Другая задача, рассмотренная Л. Эйлером,задача о кёнигсбергских мостах, формулируемая следующим образом. Имеется семь мостов, соединяющих берега реки, протекающей через город, и два острова, расположенные на ней. Спрашивается, можно ли обойти все мосты, проходя по каждому только один раз, и возвратиться в исходную точку. Полагая, что вершины соответствуют районам суши, а ребра мостам, эту задачу можно сформулировать в виде вопроса о возможности последовательного обхода графа, изрбраженного на рис. 1, с условием однократного использования его ребер и возвращения в исходную точку (см. Графа обход). Если в графе такой обход возможен, то говорят, что он обладает эйлеровым циклом. Л. Эйлер установил, что такой цикл в графе существует тогда и только тогда, когда он связен, и число ребер, инцидентных каждой вершине, четно. Так как граф на рис. 1 не удовлетворяет этому требованию, то задача о кёнигсбергских мостах неразрешима. Она неразрешима и в том случае, если отбросить требование совпадения точек начала и конца обхода. В этом случае решается воцрос о существовании эйлеровой цепи в графе. Граф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин, инцидентных нечетному числу ребер, равно 0 или 2. Граф на рис. 1 не удовлетворяет и этому условию (см. [3]).

В 1859 У. Гамильтон (W. Hamilton) придумал игру "Кругосветное путешествие", состоящую в отыскании такого пути, проходящего через все вершины (города) графа, изображенного на рис. 2, чтобы посетить каждую вершину однократно и вернуться в исходную. Пути в графах, обладающие таким свойством, наз. гамильтоновыми циклам и. Необходимые и достаточные условия существования гамильтонова цикла в графе пока (1978) неизвестны (см. [3]).

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

В 1847 Р. Киркман (R. Th. Kirkman) поставил и решил задачу о 15 школьницах. Они должны были гулять ежедневно пятью группами по три в каждой группе. При этом необходимо было так составить расписание для их прогулок, чтобы каждая школьница в течение семи дней смогла точно один раз попасть в одну группу с каждой из остальных. Эта задача связана с задачей построения системы троек, поставленной Я. Штеинером (J. Steiner, 1853). Системой троек Штейнера порядка vназ. такой набор троек из множества, содержащего vэлементов, что каждая пара элементов входит точно в одну тройку. Системы троек Штейнера описаны для v<15. Оказывается, что для v-3,7, 9 системы троек единственны, с точностью до эквивалентности (подстановка vэлементов, перестановка троек); для v=13 существуют две неэквивалентные системы троек; при v=15 таких троек 80. Для v>15 число различных систем троек Штейнера пока (1978) неизвестно. При v>3 система троек Штейнера является частным случаем неполной частично уравновешенной блок-схемы.

Классическая задача о встречах состоит в следующем. Имеются две одинаковые колоды из празличных карт каждая. Необходимо определить Dnr r=0, 1, ... , и,число расположений карт во второй колоде таких, что при сравнении соответствующих карт первой и второй колоды число совпадений равно r, r=0, 1, ... , n. Частный случай этой задачи при r=0 впервые был сформулирован П. Монмором (P. Montmort, 1708). Л. Эйлер рассматривал задачу отыскания числа членов определителя, не имеющих общих элементов с главной диагональю, эквивалентную определению Dno.

Задача о встречах была исходным пунктом для возникновения раздела комбинаторного анализа, связанного с иссдедованнем перестановок с ограниченными позициями. На совокупности Sn подстановок степени п, действующих на множестве X, можно ввести расстояние р, полагая

Тогда

причем

В терминах расстояний между подстановками можно сформулировать и другую классическую К. з., называемую обычно задачей о супружеских парах. Она состоит в определении числа М п рассаживаний псупружеских пар на 2n местах за круглым столом так, чтобы ни один муж не сидел рядом со своей женой. Тогда