Комбинаторные Задачи

Класс и ческ незадачи выбора и расположения элементов конечного множества, имеющие в качестве исходной нек-рую формулировку развлекательного содержания типа головоломок. Одной из классических К. з., фигурирующей еще в мифах Древнего Востока, является построение магического квадрата, т. е. расположение первых n2 натуральных чисел в квадрате nxn так, чтобы все суммы по строкам, столбцам и диагоналям были равны одному и тому же числу. Напр.,- магический квадрат при n=3. Известен ряд методов построения таких квадратов (см., напр., [1]). Определение числа магических квадратов порядка ппри n>4 представляет трудную еще нерешенную (1978) задачу. Ряд К. з. был рассмотрен Л. Эйлером (L. Euler). Одна из них — задача о 36 офицерах, состоящая в том, чтобы указанное число офицеров 6 различных воинских званий и из 6 различных полков так расположить в ячейках квадрата (каре), чтобы каждая колонна и каждая шеренга содержали одновременно одного и только одного офицера каждого ранга и каждого полка. Квадрат размером содержащий в ячейках элементы 1, 2, . . ., п, наз. латинским, если элементы в каждой строке и каждом столбце различны. Два латинских квадрата наз. ортогональными, если при их наложении все п 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 местах за круглым столом так, чтобы ни один муж не сидел рядом со своей женой. Тогда М п =2n!Un, |, где е- единичная подстановка, а с=(1, 2, ... , п). Получена формула: Если то величина Un(s1, s2 )зависит только от цикловой структуры и может быть выражена в виде формулы с использованием Чебышева многочленов (см. [4]). Тесную связь с приведенными задачами имеет проблема определения числа Lkn латинских прямоугольников и числа Ln латинских квадратов. Латинский прямоугольник может рассматриваться как упорядоченный набор подстановок s1, s2, .. ., sk степени п таких, что p(si, sj)=n.Показано, что Установлено, что при k<п 1/3-e, е>0, где при Число латинских квадратов порядка п известно до n=9 включительно. Задача о числе разбиений натурального числа n на слагаемые впервые появилась в письме Г. Лейбница (G. Leibniz) к Я. Бернулли (J. Bernoulli) в 1669. Однако разработка методов решения целого класса задач такого типа была осуществлена Л. Эйлером, к-рый эффективно использовал для этой цели производящие функции, задаваемые в виде бесконечных произведений. Он, в частности, установил, что число разбиений m+n на пслагаемых равно числу разбиений тна не более чем пслагаемых, равно числу разбиений тна слагаемые, не превосходящие п, и равно числу разбиений на празличных слагаемых. Классическая задача размещения состоит в определении числа С пт(r)способов размещения тразличных предметов в празличных ячейках с заданным числом rпустых ячеек. Получено, что Исследования здесь велись в плане теоретико-вероятностных приложений, включая разнообразные обобщения и модификации. Наиболее интересная часть этих исследований касается получения различных асимптотических результатов, когда ти пнеограниченно возрастают. Лит.:[1] Постников М. М., Магические квадраты, М., 1964; [2] Холл М., Комбинаторика, пер. с англ., М., 1970; [3] Оре О., Теория графов, пер. с англ., М., 1968; [4] Риордан Д ж., Введение в комбинаторный анализ, пер. с англ., М., 1963; [5] Харари Ф., Теория графов, пер. с англ., М., 1973. В. Я. Сачков.