ОГЛАВЛЕНИЕ

ГЛАВА 1. ЭЛЕМЕНТЫ КОМБИНАТОРИКИ стр.5

1.1. Перестановки, сочетания, полиномиальная теорема 5

1.2. Рекуррентные соотношения и производящие функции 10

1.3. Формула включения и исключения 17

1.4. Теорема Холла (о представителях) 21

1.5. Некоторые комбинаторные задачи на плоскости 24

ГЛАВА 2. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ 31

2.1. Основные понятия теории графов и способы

представления графов 31

2.2. Теорема Л.Эйлера о плоских графах 45

2.3. Оценка числа графов 48

2.4. Эйлеровы и гамильтоновы графы 50

2.5. Деревья 57

2.6. Экстремальные задачи: алгоритм Краскаля.

Задача о четырех красках 66

2.7. Теорема о целочисленности. Потоки в сетях.

Теорема о максимальном потоке и минимальном разрезе 74

ГЛАВА 3. ЭЛЕМЕНТЫ ТЕОРИИ КОДИРОВАНИЯ 81

3.1. Основные определения. Примеры кодов 81

3.2. Примеры кодов, исправляющих ошибки

(код Хэмминга) 91

3.3. Фактор-кольца коммутативных колец 97

3.4. Существование и строение конечных полей 100

3.5. Примеры кодов, исправляющих ошибки

(код Боуза-Чоудхури-Хоквингема) 102

3.6. Однозначно декодируемые коды.

Неравенство Крафта. Коды Фано и Хафмена 110

3.7. Линейные коды 117

3.8. Циклические коды 123

3.9. Код Боуза-Чоудхури-Хоквингема 129

ЛИТЕРАТУРА 134