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

Табл. 1. Ил. 11. Библиогр. 29 назв.

Ещё сравнительно недавно комбинаторика представлялась большинству людей, в том числе и многим математикам, собранием более или менее трудных, но весьма занимательных головоломок. И хотя идеи комбинаторного характера возникали порой у самых выдающихся математических умов и оказывались плодотворными в разных областях, за комбинаторной математикой признавалась, за редкими исключениями, лишь вспомогательная роль в математических исследованиях. Положение изменилось и довольно резко с середины XX в.

Научно-техническая революция, в частности внедрение ЭВМ во все области жизни, вызвала подлинный расцвет дискретной математики. Её методы должны были стать достоянием не только математиков, но и научно-технических работников — программистов, инженеров, вычислителей, экономистов и других, обеспечивающих успешное функционирование, а также дальнейшую разработку и совершенствование многочисленных систем управления и сложных вычислительных устройств. И комбинаторика, будучи важной составной частью дискретной математики, одним из её краеугольных камней, также испытала подлинный подъём. Он сказался не только в усилении интереса к комбинаторным проблемам и получении всё большего числа результатов, но также в изменении самого отношения к ней: комбинаторика стала осознаваться математиками как самостоятельная, полноправная отрасль науки.

Как всякой математической дисциплине, комбинаторной математике свойствен вполне очерченный круг вадач. Эта специфически комбинаторная постановка проблемы ощущается даже при определённом типе рассмотрений в рамках других отраслей математики. Недаром говорят, например, о «комбинаторной теории групп», «комбинаторной геометрии» или «комбинаторной топологии».

Другой важной стороной всякой развитой математической теории является присущий только ей аппарат решения возникающих в ней проблем. Комбинаторная математика, однако, широко заимствует свои методы из разных математических дисциплин: алгебры, анализа, теории вероятностей, геометрии и др. В этом не только её слабость, но и сила: известно, что в настоящее время многие выдающиеся научные результаты получаются именно на стыке наук, на перекрёстках различных направлений. Тем не менее специалисты по комбинаторной математике с конца 60-х гг. стремятся выявить специфические комбинаторные методы трактовки задач дискретной математики, чтобы поставить комбинаторные исследования на более прочный теоретический фундамент.

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

Среди комбинаторных методов своё место занимает и матричный метод. Матрицы широко применяются практически во всех областях теоретической и прикладной математики. Однако их использование в комбинаторике имеет ряд специальных черт; одна из основных — систематическое рассмотрение матриц инцидентности различных комбинаторных конфигураций.

Настоящая книга посвящена матричным методам комбинаторной математики. Автор поставил своей целью показать, как матрицы из нулей и единиц используются для решения самых разных комбинаторных задач. При этом среди комбинаторных проблем автор старался выделить те, которые имеют наиболее принципиальный характер, — с точки зрения их универсальности.

Книга обращена ко всем интересующимся дискретной математикой. Для её чтения достаточно знаний в объёме курса математики обычного технического вуза. В целях облегчения понимания основной части в книгу включена вводная гл. 1, посвящённая матрицам и операциям над ними. Для желающих более глубоко изучить проблемы, затронутые в книге, в конце указана соответствующая литература.

ПРЕДИСЛОВИЕ

Книги на ту же тему

1. Прикладная комбинаторная математика, Беккенбах Э., ред., 1968
2. Комбинаторные методы дискретной математики, Сачков В. Н., 1977
3. Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
4. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
5. Дискретная математика для программистов, Хаггарти Р., 2004
6. Живые числа. Пять экскурсий, Боро В., Цагир Д., Рольфс Ю., Крафт Х., Янцен Е., 1985
7. Определители и матрицы. — 2-е изд., Боревич З. И., 1970
8. Алгоритмы решения экстремальных задач, Романовский И. В., 1977
9. Динамические задачи дискретной оптимизации, Рихтер К., 1985
10. Разреженные матрицы, Тьюарсон Р., 1977
11. Этюды для программистов, Уэзерелл Ч., 1982
12. Теория графов, Харари Ф., 1973
13. Кибернетическое моделирование. Некоторые приложения, Кемени Д. Д., Снелл Д. Л., 1972
14. Графы и их применение, Оре О., 1965
15. Эйлеровы графы и смежные вопросы, Фляйшнер Г., 2002
16. Группы и их графы, Гроссман И., Магнус В., 1971
17. Корневые трансфер-матрицы в моделях Изинга, Дмитриев А. А., Катрахов В. В., Харченко Ю. Н., 2004