Читать онлайн «По океану дискретной математики. От перечислительной комбинаторики до современной криптографии. В 2 томах. Том 2. Графы. Алгоритмы. Коды, блок-схемы, шифры»

Ю. А. Зуев ПО ОКЕАНУ ДИСКРЕТНОЙ МАТЕМАТИКИ От перечислительной комбинаторики до современной криптографии Том 2 ГРАФЫ АЛГОРИТМЫ КОДЫ, БЛОК-СХЕМЫ, ШИФРЫ URSS МОСКВА ББК 22. 176 Зуев Юрий Анатольевич По океану дискретной математики: От перечислительной комбинаторики до современной криптографии. Т. 2: Графы. Алгоритмы. Коды, блок-схемы, шифры. — М. : Книжный дом «ЛИБРОКОМ», 2012. — 368 с. Содержание настоящей книги охватывает вузовский курс дискретной мате¬ матики, включая перечислительную комбинаторику, булевы функции, графы, алгоритмы, помехоустойчивое кодирование и криптографию, а также ряд дополни¬ тельных тем. Принцип построения «от простого — к сложному» делает начальные разделы каждой главы доступными для старшеклассника, а заключительные — цен¬ ными для аспиранта. Для самостоятельного решения предлагается большое число задач различной сложности, снабженных ответами и указаниями. В книге рассказы¬ вается также об истории математических открытий и формулируются открытые проблемы дискретной математики. Книга состоит из двух томов. Во втором томе рассматриваются графы, алго¬ ритмы в дискретной математике и теория кодирования (в том числе задачи сжатия информации, помехоустойчивого кодирования и криптографии). Первый том, в котором даются основные идеи и понятия дискретной математики, изучаются теория и методы перечисления, булевы функции, выходит одновременно со вторым в нашем издательстве. Написанная доступным языком, в яркой форме и с многочисленными приме¬ рами, книга будет полезна широкому кругу читателей, желающих познакомиться с основами дискретной математики. Издательство «Книжный дом “ЛИБРОКОМ”». 117335, Москва, Нахимовский пр-т, 56. Формат 60*90/16. Печ. л. 23. Зак. № ЖР-26. Отпечатано в ООО «ЛЕНАНД». 117312, Москва, пр-т Шестидесятилетия Октября, 11А, стр. 11. Никакая часть настоящей книги не может быть воспроизведена или передана в какой бы то ни было форме и какими бы то ни было средствами, будь то элек¬ тронные или механические, включая фотокопирование и запись на магнитный носитель, а также размещение в Интернете, если на то нет письменного разрешения владельца. Оглавление Глава 3. Графы 6 3. 1. Определения и примеры 6 3. 2. Деревья 18 3. 3. Двудольные графы 23 3. 4. Графы абстрактные и помеченные. Автоморфизмы 25 3. 5. Эйлеровы графы 30 3. 6. Гамильтоновы графы 33 3. 7. Паросочетания 40 3. 8. Связность 46 3. 9. Планарность 49 3. 10. Раскраски 54 3. 11. Теоремы Турана и Рамсея 62 3. 12. Перечисление графов 67 Задачи для самостоятельного решения 76 Литература 79 Глава 4. Алгоритмы 81 4. 1. Понятие алгоритма 81 4. 2. Алгоритмы на графах 97 4. 3. Потоки в сетях 109 4. 4. Практические методы решения задач дискретной оптимизации 119 4. 5. Жадные алгоритмы и матроиды 135 4. 6. Теория сложности: классы Р и NP 139 4. 7. Сложность приближённого решения 148 4. 8.