Теория графов

В книге представлены фундаментальные понятия для всестороннего рассмотрения ключевых тем дискретной математики. Приведены детальные примеры для облегчения восприятия вводимых теоретических понятий, а также темы для обсуждения, позволяющие закрепить техники представленных алгоритмов. Дается объяснение недостаточно известных методов, таких как задание множеств формулами и упрощение формул при помощи графов, применение метода Магу для определения параметров графа на основе использования методов алгебры логики. Издание дополняют 276 задач с подробным решением. Книга предназначена как для студентов, так и для специалистов, использующих методы дискретной математики в компьютерной технике, бизнес-исследованиях, экономике, менеджменте, логистике и связанных с ними разделах.

Настоящее пособие составлено на основе олимпиадных задач по математике преподавателями факультета ВМК МГУ имени М. В. Ломоносова. Пособие содержит теоретический материал, подборку задач, а также указания и решения к большинству задач. Рекомендуется школьникам 5–7 классов, интересующимся олимпиадными задачами, учителям математики, руководителям кружков и факультативов.

Учебное пособие содержит материал по разделу «Теория графов» в рамках курса «Дискретная математика» и включает разделы: «Введение в теорию графов», «Метрики и числа графов», «Специальные циклы графов». Каждый раздел пособия содержит теоретический материал курса лекций, примеры выполнения практических заданий и рекомендации для проведения практических занятий. С целью повышения эффективности самостоятельной работы студентов каждый раздел пособия завершается списком вопросов для самоконтроля, перечнем практических заданий для самостоятельной работы и рекомендациями для выполнения домашних заданий. Организационные особенности предложенного материала делают данное пособие полезным как преподавателям, так и студентам вузов. Пособие предназначено для студентов всех форм обучения по всем направлениям подготовки бакалавров и специальностям Института компьютерных технологий и информационной безопасности.

В книге более подробно, чем в большинстве учебников, излагаются три раздела, представляющие интерес для студентов всех специальностей, изучающих дискретную математику: перечислительная комбинаторика, теория графов и теория кодирования. Учебный материал иллюстрируется примерами, упражнениями и задачами, к некоторым из которых даны указания разной степени подробности. Книга будет интересна всем изучающим и преподающим дискретную математику и информатику.

В девятнадцатом выпуске серии «Математика в техническом университете» изложены теория множеств и отношений, элементы современной абстрактной алгебры, теория графов, классические понятия теории булевых функций, а также основы теории формальных языков, куда включены теории конечных автоматов, регулярных языков, контекстно-свободных языков и магазинных автоматов. В анализе графов и автоматов особое внимание уделено алгебраическим методам. Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана. Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам.