Читать онлайн «Введение в дискретную математику. Элементы комбинаторики, теории графов и теории кодирования»

Ю. Н. Мальцев, Е. П. Петров ВВЕДЕНИЕ В ДИСКРЕТНУЮ МАТЕМАТИКУ ЭЛЕМЕНТЫ КОМБИНАТОРИКИ, ТЕОРИИ ГРАФОВ И ТЕОРИИ КОДИРОВАНИЯ Барнаул ■ 1997 МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РФ АЛТАЙСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Ю. Н. МАЛЬЦЕВ, Е. П. ПЕТРОВ ВВЕДЕНИЕ В ДИСКРЕТНУЮ МАТЕМАТИКУ ЭЛЕМЕНТЫ КОМБИНАТОРИКИ, ТЕОРИИ ГРАФОВ И ТЕОРИИ КОДИРОВАНИЯ Издательство Алтайского государственного университета Барнаул - 1997 УДК 510. 51 Введение в дискретную математику (элементы комбинаторики, теории графов и теории кодирования): Учебное пособие. // Ю. Н. Мальцев, Е. П. Петров. Барнаул: Изд-во Алт. ун-та, 1997. 135 с. Цель данного пособия - излож:ить студентам математического факультета основные разделы дискретной математики в соответствии с новой программой. В пособии приведено больпюе количество примеров и задач, многие из которых снабж:ены указаниями к регаению. Авторы выражают благодарность генеральному директору фирмы " Байт" А. М. Стрыгину за финансовую номогць. Табл. 9. Ил. 80. Библиогр. 29 пазв. ©Мальцев Ю. П. , Петров Е. П. , 1997. ©Алтайский государственный университет, 1997. ОГЛАВЛЕНИЕ ГЛАВА 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 Глава 1 ЭЛЕМЕНТЫ КОМБИНАТОРИКИ Комбинаторика - раздел математики, посвященный решению задач выбора и располож:ения элементов некоторого множ:ества в соответствии с заданными условиями. Элементы комбинаторики встречались в трудах математиков Древнего Востока (число сочетаний, бином Ньютона). Б. Паскаль и П. Ферма являлись основоположниками комбинаторики как раздела математики. Больпюй вклад в развитие комбинаторики внесли Г. Лейбниц, Я. Бернулли, Л. Эйлер, Ф. Холл, Г. Пойа, Р. Дилуорс. 1. 1 Перестановки, сочетания, полиномиальная теорема Рассмотрим конечное множество М = {ai,... ,a^}, содержащее п элементов. Сочетание - подмнож:ество М, т. е. некоторая неупорядоченная выборка различных элементов из М.