Сотрудники :: Носов Валентин Александрович :: Публикации Носова В.А.

Комбинаторика и теория графов.

Носов В.А.
Учебное пособие (116 страниц)

Скачать пособие полностью в формате PDF (1 МБ): combgraph.zip
Для просмотра Вам понадобится Adobe Acrobat Reader 4.x-5.x

Пособие содержит изложение основ комбинаторики и теории графов в соответствии с программой семестрового курса для студентов младших курсов, обучающихся по специальности "Прикладная математика"

ОГЛАВЛЕНИЕ

• ГЛАВА I. ВВЕДЕНИЕ В КОМБИНАТОРИКУ.
  • § 1. Множества. Отображения. 5
    • 1. Множества. 5
    • 2. Отображения. 7
    • 3. Алгебра множеств. 9
    • Упражнения. 11
  • § 2. Принципы перечисления и примеры. 13
    • Элементарные тождества. 13
    • Упражнения. 21
  • § 3. Бинарные отношения. 22
    • 1. Определения. 22
    • 2. Операции над отношениями. 23
    • 3. Свойства операций над отношениями. 24
    • Упражнения. 26
  • § 4. Специальные классы бинарных отношений. 28
    • 1. Отношения эквивалентности. 28
    • 2. Отношения толерантности. 30
    • 3. Отношения частичного порядка. 31
    • Упражнения. 34
  • § 5. Элементы теории подстановок. 36
    • Упражнения. 41
  • § 6. Порождение сочетаний и перестановок. 42
• ГЛАВА II. МЕТОДЫ ПЕРЕЧИСЛЕНИЯ.. 47
  • § 1. Метод включения-исключения. 47
  • § 2. Метод рекуррентных соотношений.. 55
  • § 3. Производящие функции и формулы обращения.. 60
  • § 4. Обращение Мебиуса. 68
  • § 5. Перманенты и их применение к перечислительным задачам. 72
  • Упражнения.. 78
• ГЛАВА III. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ. 80
  • § 1. Основные понятия теории графов. 80
  • § 2. Эйлеровы графы. 85
  • § 3. Гамильтоновы графы. 90
  • § 4. Кратчайшие пути. 94
  • § 5. Деревья. 96
  • § 6. Планарные графы... 104
  • § 7. Раскраска графов.. 108
  • § 8. Потоки в сетях. 110
  • Упражнения. 116
• ЛИТЕРАТУРА.. 117

ВВЕДЕНИЕ

Настоящее пособие подготовлено на основе лекций по одноименному семестровому курсу, читаемому в 2-м семестре для студентов, обучающихся по специальности "Прикладная математика".

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

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

Список литературы представлен в конце пособия. Нумерация утверждений и ссылок независима в каждом параграфе.

Автор выражает признательность всем прочитавшим рукопись пособия и сделавшим свои замечания по его улучшению.

Учебное пособие. Московский государственный институт электроники и математики. Москва, 1999.

Наверх