КОМБИНАТО́РНЫЕ ЗАДА́ЧИ КЛАССИ́ЧЕСКИЕ
-
Рубрика: Математика
-
-
Скопировать библиографическую ссылку:
Книжная версия:
Электронная версия:
КОМБИНАТО́РНЫЕ ЗАДА́ЧИ КЛАССИ́ЧЕСКИЕ, задачи выбора и расположения элементов конечного множества, в которых на выбор и расположение налагаются те или иные условия. К К. з. к. можно отнести мн. задачи развлекательного характера типа головоломок.
Одной из К. з. к., упоминающейся ещё в мифах Древнего Востока, является построение магич. квадратов, т. е. расположение первых n2 натуральных чисел в квадрате n×n так, чтобы все суммы чисел по строкам, столбцам и диагоналям были равны одному и тому же числу. Напр., 492357816 – магич. квадрат при n=3. Известен ряд методов построения таких квадратов. Задача о нахождении формулы для числа магич. квадратов порядка n для любого натурального n до сих пор не решена.
Ряд К. з. к. был рассмотрен Л. Эйлером. Одна из них – задача о 36 офицерах, в которой требуется расположить в ячейках квадрата 6×6 (каре) 36 офицеров 6 разл. воинских званий и 6 разл. полков так, чтобы каждая колонна и каждая шеренга содержали одновременно одного и только одного офицера каждого звания и каждого полка. Эта задача эквивалентна задаче о существовании пары ортогональных латинских квадратов порядка 6. Эйлер высказал гипотезу о том, что ортогональных лат. квадратов порядков n=4k+2,k=1,2,…, не существует. В 1900 франц. математик Г. Тарри подтвердил эту гипотезу для n=6 и тем самым доказал, что задача о 36 офицерах не имеет решения. В 1959 инд. математиком С. Човлой, венг. математиком П. Эрдёшем и нем. математиком Г. Штраусом была доказана теорема о существовании пары ортогональных латинских квадратов для каждого n=4k+2,k=2,3,…
Др. задача, рассмотренная Эйлером, – задача о кёнигсбергских мостах, формулируемая следующим образом. В городе имеется 7 мостов, соединяющих берега реки и 2 острова, расположенные на ней. Спрашивается, можно ли обойти все мосты, проходя по каждому только 1 раз, и возвратиться в исходную точку. В терминах графов теории эта задача формулируется следующим образом. Полагая, что вершины соответствуют районам суши, а рёбра – мостам, задачу о кёнигсбергских мостах можно сформулировать в виде вопроса о возможности последовательного обхода графа, изображённого на рис. 1, проходя его рёбра по одному разу и возвращаясь в исходную точку. Если в графе такой обход возможен, то говорят, что он обладает эйлеровым циклом. Эйлер установил, что такой цикл в графе существует тогда и только тогда, когда он является связным и число рёбер, инцидентных каждой вершине, чётно. Т. к. граф на рис. 1 не удовлетворяет этому требованию, то задача о кёнигсбергских мостах неразрешима. Она неразрешима и в том случае, если отбросить требование совпадения точек начала и конца обхода; в этом случае ставится вопрос о существовании эйлеровой цепи в графе. Граф обладает эйлеровой цепью тогда и только тогда, когда он связен и число вершин, инцидентных нечётному числу рёбер, равно 0 или 2. Граф на рис. 1 не удовлетворяет и этому условию.
В 1859 У. Гамильтон предложил головоломку «Кругосветное путешествие», состоящую в отыскании такого пути, проходящего через все вершины (их можно интерпретировать как городá) графа, изображённого на рис. 2, чтобы посетить каждую вершину только один раз и вернуться в исходную вершину. Пути в графах, обладающие таким свойством, называются гамильтоновыми циклами. Необходимые и достаточные условия существования гамильтонова цикла в графе неизвестны. Задача о гамильтоновых циклах в графе получила разл. обобщения. Одно из них – задача коммивояжёра, имеющая ряд приложений в исследовании операций, в частности при решении некоторых транспортных проблем. Она состоит в следующем: имеется некоторое количество городов, расстояния между которыми известны; нужно найти кратчайший замкнутый путь, проходящий через все города.
В 1847 англ. математик Т. Киркман поставил и решил задачу о 15 школьницах, которые должны гулять ежедневно пятью группами по трое в каждой группе. Необходимо так составить расписание для их прогулок, чтобы каждая школьница в течение семи дней точно один раз попадала в одну группу с каждой из остальных. Эта задача связана с задачей, поставленной швейц. математиком Я. Штейнером (1853), о построении систем троек. Системой троек Штейнера порядка vназывается такой набор троек из множества, содержащего v элементов, что каждая пара элементов входит точно в одну тройку. Системы троек Штейнера описаны для v⩽15 . Оказывается, что для v=3, 7, 9 системы троек единственны с точностью до эквивалентности (до перестановки v элементов и перестановки троек); для v=13 существуют две неэквивалентные системы троек; при v=15 таких троек 80 . Для v>15 число разл. систем троек Штейнера неизвестно.
Классич. задача о встречах состоит в следующем. Имеются две одинаковые колоды карт из n разл. карт каждая. Необходимо определить число расположений карт D_{nr}, r=0,1,… n, во второй колоде таких, что при сравнении соответствующих карт первой и второй колоды число совпадений равно r. Частный случай этой задачи при r=0 впервые был сформулирован франц. учёным П. де Монмором в нач. 18 в.
К К. з. к. относится т. н. задача о супружеских парах, которая состоит в определении числа рассаживаний n супружеских пар на 2n местах за круглым столом так, чтобы ни один муж не сидел рядом со своей женой.
Задача о числе разбиений натурального числа n на слагаемые появилась в письме Г. В. Лейбница к Я. Бернулли (1669). Разработка методов решения задач такого типа была осуществлена Эйлером, который эффективно использовал для этой цели производящие функции.
Классич. задача размещения состоит в определении числа C_{nm} (r) способов размещения m разл. предметов в n разл. ячейках с заданным числом r пустых ячеек. Оказывается, чтоC_{nm}(r)=c_n^rΔ^{n-r}0^m, r=0,1,…, n, где
Δ^k0^m=\sum_{j=0}^k (-1)^jC_k^j (k-j)^m.
Эта задача имеет разл. теоретико-вероятностные приложения. При этом в осн. получаются асимптотич. результаты, когда m и n неограниченно возрастают.
