Читать онлайн «По океану дискретной математики. Том 2»

По океану ю. а. зуев дискретной ма ем* ι . ι ι . ' »' η ι: · ιw . Графы % Алгоритмы Ι Коды, блок-схемы, Г" I шифры *Ь URSS Ю. А. Зуев ПО ОКЕАНУ ДИСКРЕТНОЙ МАТЕМАТИКИ От перечислительной комбинаторики до современной криптографии Том 2 ГРАФЫ АЛГОРИТМЫ КОДЫ, БЛОК-СХЕМЫ, ШИФРЫ URSS МОСКВА ББК 22. 176 Зуев Юрий Анатольевич По океану дискретной математики: От перечислительной комбинаторики до современной криптографии. Т. 2: Графы. Алгоритмы. Коды, блок-схемы, шифры. — М. : Книжный дом «ЛИБРОКОМ», 2012. — 368 с. Содержание настоящей книги охватывает вузовский курс дискретной математики, включая перечислительную комбинаторику, булевы функции, графы, алгоритмы, помехоустойчивое кодирование и криптографию, а также ряд дополнительных тем. Принцип построения «от простого — к сложному» делает начальные разделы каждой главы доступными для старшеклассника, а заключительные — ценными для аспиранта. Для самостоятельного решения предлагается большое число задач различной сложности, снабженных ответами и указаниями. В книге рассказывается также об истории математических открытий и формулируются открытые проблемы дискретной математики. Книга состоит из двух томов. Во втором томе рассматриваются графы, алгоритмы в дискретной математике и теория кодирования (в том числе задачи сжатия информации, помехоустойчивого кодирования и криптографии). Первый том, в котором даются основные идеи и понятия дискретной математики, изучаются теория и методы перечисления, булевы функции, выходит одновременно со вторым в нашем издательстве. Написанная доступным языком, в яркой форме и с многочисленными примерами, книга будет полезна широкому кругу читателей, желающих познакомиться с основами дискретной математики. Издательство «Книжный дом "ЛИБРОКОМ"». 117335, Москва, Нахимовский пр-т, 56. Формат 60x90/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.