19. Проблемы комбинаторики

Мы рассказали об истории развития комбинаторики и О некоторых ее приложениях. Однако о том, что же такое комбинаторика, какие математические вопросы относятся к ней, а какие — к другим областям математики, было сказано весьма глухо. Это объясняется большим Разнообразием комбинаторных проблем, ЗАтрудняющим формулировку единого определения, которое охватывало бы Все частНЫе случаи, а такжЕ тем, что многие Комбинаторные задачи имеют пограничный характер, относясь и к КОмбинаторике, и к смежным областям знания.

В первом приближении можно сказать, что КомбинаТорика изучает способы выборки и расположения предметов, свойства различных конфигураций, которые можНО оБРазовать из элементов, причем элементами могут быть числа, точки, отрезки, шахматные фигуры и т. Д. Характерной чертой комбинаторных ЗАдач является то, что в них речь идет всегда о конечном множестве элеМЕнтов. Чтобы устранить влияние конкретного вида ВыбиРаемых и располагаемых предметов, надо воспользоваться ОбщИм языком теории множеств, говорить о множествах и их подмножествах (частях), об объединении нескольких множеств и их пересечении (образовании общей части) и т. д. Мы будем рассматривать лишь конечные МнОжества. Число элементов в множестве А будем ОбоЗначать N(A) и называть Мощностью этого множества, а множество из П элементов будем НАзывать N-множестВом.

С точки ЗРения теории множеств комбиНАторика иЗуЧает подмножества конечных множеств, их объедиНЕния и пересечения, а также различные способы упорядочивания этих подмножеств. Одной из общих задач Комбинаторики является следующая:

1. Найти конфигурацию элементов, обладающую ЗаранЕЕ заданными свойствами.

В некоторых случаях такую конфигурацию Удается Найти сразу. Например, если требуется Раслоложить 10 точек и 5 отрезков так, чтобЫ на каждом Отрезке Было По 4 точки, то поЕЛо недолгИХ размышлений мы ВспомиНаем фигуру

Пятиконечной звезды и располагаем ее элементы так, как показаНО на рис. 1. Иногда для Отыскания той или иной конфигурации оказываются полезными соображеНИя симмЕТрии. Если не уДАется НайТи решение из ПРостых соображений, в ход пускается тяжелая артиллерия: теория чисел, теория групп и т. Д.

Бывает, одНАко, что и она не помогает — Искомая КоНФигурация никак не складывается. Конечно, если задача возникла из практики, то в большинстве случаев можно быть уверенНЫм в существовании решениЯ. Гораздо хуже в этом отношении положение шахматиста рассчитывающего комбинацию, или специалиста по шифрам, придумывающего новый код с заранее задаНнЫ свойствами. Они не знают заранее, существует ли то, Что Они ищут, не являются ли их труды поискамИ черной кошки в темной комнате, где кошки и в помине не было. Таким образом возникает вторая проблема комбинаторики.

2. Доказать существование или отсутствие конфигурации с заданными свойствами.

Во многих случаях, однако, бывает недостаточно найти одну конфигурацию с заданными свойствами, a требуется описать все такие конфигурации и найти их число. НАпример, можно потребовать найти не одно, а все возМОжные расположения 10 точек на 5 отрезках, при которых на каждом отрезке лежат по 4 точки. Можно доказать, что кроме изображенной на рис. 1 пятиконечной зВЕзды есть еще пять расположений с такиМ свойством. ОнИ изображены на рис. 2. Любое другое расположенИЕ с требуемыми свойствами отличается от одного из указанных шести лишь размЕРами отрезков, но не их взаимным расПОложением.

Итак, мы пришли к двум проблемам комбинаторики, которые в XVIII и XIX вв. исчерпывали все содержание этой науки.

3. Найти общеЕ число коНФигураций с заданными сВОйствами.

4. Описать все способы решения данной комбинаторной задачи, дать алгоритм их перечисления.

Бурное развитие экономических приложений математики привело к возникновению и изучению обширного (и, быть может, сейчас самого важного) класса комбинаторных задач — задач на оптимизацию.

5. Из всех решений данной комбинаторной задачи Выбрать оптимальноЕ по тем или иным параметрам.

Например, существует очень много способов прикрепить потребителей каменного угля к шахтам. Экономист будет искать способ, при котором транспортные расходы окажутся минимальными.

Одной из классических оптимизационных задач является «задача о коммивояжере», в которой требуется наметить путь бродячего торговца, объезЖАющего задаННые П городов, причем он должен по одному разу Побывать в каждом городе и проделать весь путь за НаименьШее время. Несмотря на усилия многих специалистов до сих пор нет достаточно общего и Удовлетворительного Решения ЭТой задачи.

< Предыдущая		Следующая >