Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

1.1. Исторический экскурс в комбинаторику

Комбинаторная математика, комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого (обычно конечного) множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций, в частности вопросов их существования, алгоритмов построения, решения задач на перечисление. Примерами комбинаторных конфигураций являются перестановки, размещения и сочетания; блок-схемы и латинские квадраты [20], [79], [95].

Возникновение основных понятий и развитие комбинаторики шло параллельно с развитием других разделов математики, таких, как алгебра, теория чисел, теория вероятностей, с которыми комбинаторный анализ тесно связан. Ещё математикам Древнего Востока были известны, например, формула, выражающая число сочетаний через биномиальные коэффициенты, и формула Бинома Ньютона с натуральным показателем n. С мистическими целями изучались магические квадраты 3-го порядка.

Большой вклад в развитие комбинаторных методов был сделан Г. Лейбницем, Я. Бернулли, Л. Эйлером. С 50-х гг. XXвека интерес к комбинаторному анализу начал возрождаться, что связано с бурным развитием кибернетики, дискретной математики, теории планирования и теории информации. На формирование направления исследований в дальнейшем оказывают влияние два фактора. С одной стороны, выбор объектов исследований, с другой – формулировка целей исследования, зависящая в конечном счёте от сложности изучаемых объектов. Если исследуемая комбинаторная конфигурация имеет сложный характер, то целью исследования является выяснение условий её существования и разработка алгоритмов построения.

Другое направление комбинаторного анализа связано с теоремами выбора, т.е. теоремами, связанными с выбором элементов из данного множества, тем или иным способом соответствующих семейству подмножеств этого множества. В основе целого ряда результатов этого направления лежит теорема Холла о существовании системы различных представителей (трансверсали) семейства подмножеств некоторого множества [95].

Теорема Холла.Семейство S тогда и только тогда имеет систему различных представителей, когда объединение каждых k множеств из S содержит, по крайней мере, k различных элементов, .