Введение. В рамках этой модели две нижние страты (1-я и 2-я) объединяют около 20% россиян

Оглавление

Оглавление. 3

Введение. 5

1. Комбинаторика в задачах. 6

1.1 Основной принцип комбинаторики. 6

1.2 Размещения с повторениями. 6

1.3 Размещения без повторений. 7

1.4 Перестановки. 8

1.5 Сочетания (без повторений) 8

1.6 Свойства биномиальных коэффициентов. 9

1.7 Разбиения множеств. 9

1.8 Сочетания с повторениями. 10

1.9 Разные задачи. 10

1.10 Производящие функции. 12

1.11 Использование рекуррентных соотношений. 13

1.12 Формула включений и исключений. 14

1.13 Комбинаторные величины при больших значениях параметров 15

2 Множества и функции. 15

2.1 Множества и простейшие операции над ними. 16

2.2 Булеан множества. 20

2.3 Прямое произведение множеств. 21

2.4 Отношения на множествах. 22

2.5 Отображения (функции) 26

2.6 Мощность множеств. 30

2.7 Счетные множества. 35

2.8 Некоторые свойства бесконечных множеств. 37

2.9 Вопросы для самопроверки. 39

2.10 Упражнения. 40

3 Основы теории графов. 44

3.1 Основные понятия. 44

3.2 Компьютерные представления графов. 46

3.3 Маршруты и связность. 48

3.4 Кратчайшие пути в графах. 49

3.5 Деревья. 52

3.6 Кодирование деревьев. 54

3.7 Центр дерева. 54

3.8 Минимальное остовное дерево (остов) 55

3.9 Эйлеровы графы.. 56

3.10 Гамильтоновы графы.. 58

3.11 Графовые векторы.. 60

3.12 Паросочетания и реберные покрытия. 62

3.13 Паросочетания в двудольных графах. 64

3.14 Правильная нумерация вершин графа. 66

3.15 Сетевые графики. 67

3.16 Потоки в сетях. 68

3.17 Вопросы для самопроверки. 71

3.18 Упражнения. 72

Рекомендуемая литература. 75

Предметный указатель. 76

Введение

В пособии излагается краткий курс дискретной математики для студентов специальности «Математические методы в экономике». Курс состоит из трех разделов. Особенность первого раздела «Комбинаторика в задачах» состоит в том, что теоретические результаты возникают в процессе решения циклов задач, практика показала эффективность такого подхода. Второй раздел «Множества и функции» начинается с самых элементарных сведений об операциях над множествами, заканчивается при этом глубокими результатами, в частности, теоремой о несуществовании множества максимальной мощности. Второй и третий разделы сопровождаются вопросами для самопроверки и упражнениями.

Пособие рассчитано на активную работу. В частности, в нем практически нет рисунков, эта работа возлагается на читателя. В ряде упражнений к третьему разделу задания сформулированы, но не указаны объекты. Их читателю (и преподавателю) следует выбирать самостоятельно, подобные примеры подробно рассматриваются на практических занятиях.

Следует иметь в виду, что дискретная математика – математическая дисциплина, кардинально отличающаяся от математического анализа или линейной алгебры: ее предметом являются объекты, «отделимые» друг от друга. Например, какое вещественное число является соседним с 1? Такого нет! А такое натуральное число есть (это, как всем понятно, 2). Методы дискретной математики также весьма специфичны, очень поучительны и элегантны. Изучение этой дисциплины, надеюсь, доставит удовольствие любому заинтересованному читателю. Алгоритмы теории графов широко применяются при решении различных практических задач.