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

 

Название:

Размер: 1,94 Мб

Описание: Носов В. А. Комбинаторика и теория графов Учебное пособие, Московский государственный институт электроники и математики (Технический университет), Москва, 1999 Скачать бесплатно

Ссылка для скачивания файла:

 

 

Оглавление
ОГЛАВЛЕНИЕ .........................................................................................................2
ВВЕДЕНИЕ................................................................................................................0
ГЛАВА I. ВВЕДЕНИЕ В КОМБИНАТОРИКУ.................................................. 1
§ 1. МНОЖЕСТВА. ОТОБРАЖЕНИЯ. ..........................................................................1
1. Множества.....................................................................................................1
2. Отображения................................................................................................. 3
3. Алгебра множеств......................................................................................... 5
Упражнения........................................................................................................ 6
§ 2. ПРИНЦИПЫ ПЕРЕЧИСЛЕНИЯ И ПРИМЕРЫ...........................................................9
Элементарные тождества. .............................................................................9
Упражнения...................................................................................................... 17
§ 3. БИНАРНЫЕ ОТНОШЕНИЯ..................................................................................18
1. Определения. .................................................................................................18
2. Операции над отношениями. ...................................................................... 19
3. Свойства операций над отношениями. ..................................................... 21
Упражнения...................................................................................................... 22
§ 4. СПЕЦИАЛЬНЫЕ КЛАССЫ БИНАРНЫХ ОТНОШЕНИЙ..........................................24
1. Отношения эквивалентности. ...................................................................24
2. Отношения толерантности.......................................................................26
3. Отношения частичного порядка................................................................27
Упражнения. .....................................................................................................30
§ 5. ЭЛЕМЕНТЫ ТЕОРИИ ПОДСТАНОВОК. ...............................................................32
Упражнения. .....................................................................................................37
§ 6. ПОРОЖДЕНИЕ СОЧЕТАНИЙ И ПЕРЕСТАНОВОК.................................................38
ГЛАВА II. МЕТОДЫ ПЕРЕЧИСЛЕНИЯ .........................................................43
§ 1. МЕТОД ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ. ...............................................................43
§ 2. МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ .........................................................51
§ 3. ПРОИЗВОДЯЩИЕ ФУНКЦИИ И ФОРМУЛЫ ОБРАЩЕНИЯ ....................................56
§ 4. ОБРАЩЕНИЕ МЕБИУСА. ..................................................................................64
§ 5. ПЕРМАНЕНТЫ И ИХ ПРИМЕНЕНИЕ К ПЕРЕЧИСЛИТЕЛЬНЫМ ЗАДАЧАМ. ...........68
УПРАЖНЕНИЯ .........................................................................................................74
ГЛАВА III. ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ............................................... 76
§ 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ. ..........................................................76
§ 2. ЭЙЛЕРОВЫ ГРАФЫ. ..........................................................................................81
§ 3. ГАМИЛЬТОНОВЫ ГРАФЫ..................................................................................85
§ 4. КРАТЧАЙШИЕ ПУТИ.........................................................................................89
§ 5. ДЕРЕВЬЯ. .........................................................................................................91
§ 6. ПЛАНАРНЫЕ ГРАФЫ ........................................................................................99
§ 7. РАСКРАСКА ГРАФОВ ......................................................................................103
§ 8. ПОТОКИ В СЕТЯХ. ..........................................................................................105
УПРАЖНЕНИЯ. ......................................................................................................111
ЛИТЕРАТУРА ......................................................................................................112 
 

 

 

Книги в бумажном виде. Дискретная математика в Интернет-магазине:

 

Ключевые слова: теория графов, виды графов, скачать учебник бесплатно, скачать книгу бесплатно, учебное пособие, курс лекций, граф, графы