Аннотация: По океану дискретной математики, От перечислительной комбинаторики до современной криптографии, Том 2, Графы, Алгоритмы, Коды, блок-схемы, шифры, Зуев Ю.А., 2012.

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


Графы.
Определения и примеры
Теория графов используется для построения моделей в экономических, биологических и естественных науках. Помимо этого она представляет значительный интерес и как чисто математическая дисциплина, изучающая с определённых позиций бинарные отношения на конечном множестве. Графом G = (V,E) называется конечное множество V с заданным семейством Е его двухэлементных подмножеств. Элементы множества V называются вершинами (vertices), а элементы множества Е — рёбрами (edges). Если v₁,v₂ Œ V и {v₁,v₂} Œ E, то говорят, что вершины v₁ и v₂ смежны. Поэтому граф можно определить также как заданное на множестве V бинарное отношение смежности. Это отношение является симметричным и иррефлексивным.

Эпизодически появляясь в контексте различных исследований, термин «граф» окончательно утвердился в математике после выхода в 1936 году книги венгерского математика Денеша Кёнига (1884-1944) «Теория конечных и бесконечных графов», ставшей первой в мире монографией по теории графов. Слово «граф» в переводе с греческого означает «пишу», «черчу», «рисую». И, действительно, графы с небольшим числом вершин удобно представлять рисунками, на которых вершинам соответствуют точки, а рёбрам — соединяющие их линии. Например (рис. I).

Оглавление
Глава 3. Графы
3.1.Определения и примеры
3.2.Деревья
3.3.Двудольные графы
3.4.Графы абстрактные и помеченные. Автоморфизмы
3.5.Эйлеровы графы
3.6.Гамильтоновы графы
3.7.Паросочетания
3.8.Связность
3.9.Планарность
3.10.Раскраски
3.11.Теоремы Турана и Рамсея
3.12.Перечисление графов
Задачи для самостоятельного решения
Литература
Глава 4. Алгоритмы
4.1.Понятие алгоритма
4.2.Алгоритмы на графах
4.3.Потоки в сетях
4.4.Практические методы решения задач дискретной оптимизации
4.5.Жадные алгоритмы и матроиды
4.6.Теория сложности: классы Р и NР
4.7.Сложность приближённого решения
4.8.Машина Тьюринга
4.9.Теорема Кука
Задачи для самостоятельного решения
Литература
Глава 5. Коды, блок-схемы, шифры
5.1.Задачи кодирования
5.2.Экономное кодирование. Алгоритм Хаффмана
5.3.Принципы помехоустойчивого кодирования
5.4.Линейные коды. Коды Хэмминга
5.5.Скорость передачи и вероятность ошибки. Теорема Шеннона
5.6.Коды Рида- Маллера
5.7.Конечные поля
5.8.Коды БЧХ
5.9.Латинские квадраты. Блок-схемы. Матрицы Адамара
5.10.Коды Адамара. Совершенный код Голея
5.11.О плотности упаковки шаров Хэмминга
5.12.Математические принципы современной криптографии
Задачи для самостоятельного решения
Литература
Дополнение 1. Упорядоченные множества
Определения и примеры (265); линейные продолжения (269); разбиения на цепи (272); решетки и булевы алгебры (279); модулярные и геометрические решетки (288); алгебра инцидентности (293); обращение Мёбиуса (295); свойства функции Мёбиуса (296); примеры обращения Мёбиуса (300)
Задачи для самостоятельного решения
Литература
Дополнение 2. Вероятностный метод
Основы (310); случайные величины (316); метод математических ожиданий (321); длина д. н. ф. типичной булевой функции (323); теорема Шеннона (328); максимальная тень антицепи (332); случайные (±1)-матрицы и детерминанты (336); дальнейшие результаты и гипотезы (343)
Задачи для самостоятельного решения
Литература
Ответы и указания к решению задач
Оглавление тома 1.