Лекция 1
Теоретико-множественное введение

Скачать Лекцию 1

Лекция 2
Определение графа. Вершины и ребра. Графическая интерпретация графа. Смежность и инцидентность. Локальная степень. Подграф. Полный граф. Матрицы смежностей и инциденций. Изоморфизм графов.

Скачать Лекцию 2

Лекция 3
Путь в графе и связные компоненты графа. Цепи, простые цепи, циклы, простые циклы. Операции удаления вершины, удаления ребра, подразбиения ребра. Дерево и его особенности.

Скачать Лекцию 3

Лекция 4
Эйлеров цикл и эйлеров граф. Условия существования эйлерова цикла. Задача о разбиении графа на минимальное число цепей.

Скачать Лекцию 4

Лекция 5
Гамильтонов цикл и гамильтонов граф. Условия Дирака, Оре и Поша, гарантирующие существование в графе гамильтонова цикла.

Скачать Лекцию 5

Лекция 6
Формулировка теоремы Менгера (вершинный и реберный варианты), теорема Холла о системах различных представителей и теорема Кёнига о независимых клетках в матрице. 

Скачать Лекцию 6

Лекция 7
Определение паросочений в графе и их разновидностей. Двудольные графы и алгоритм выбора наибольшего паросочетания в двудольном графе. Решение задачи о назначениях на узкие места.

Скачать Лекцию 7

Скачать Лекцию 8

Лекция 9
Планарные и плоские графы. Формулировки теоремы Понтрягина-Куратовского и теоремы Эйлера о соотношении чисел граней, ребер и вершин плоского графа.

Скачать Лекцию 9

Лекция 10
Раскраска графа. Формулировка теоремы о пяти красках. Хроматическое число и алгоритм Зыкова вычисления хроматического многочлена графа.

Скачать Лекцию 10

Лекция 11
Взвешенный граф. Кратчайшие пути во взвешенном графе и алгоритм Форда построения кратчайших маршрутов.

Скачать Лекцию 11

Лекция 12
Остов в графе и алгоритм Краскала поиска остова минимального веса во взвешенном графе.

Скачать Лекцию 12

Лекция 13
Ориентированный граф и его графическая интерпретация. Локальные степени. Матрица смежностей. Ориентированные пути и связность в ориентированном графе.

Скачать Лекцию 13

Лекция 14
Сети и потоки в сетях. Стационарные потоки. Алгоритм Форда-Фалкерсона поиска максимального стационарного потока.

Скачать Лекцию 14

Лекция 15
Перестановки, размещения и сочетания. Бином Ньютона и иллюстративные примеры.

Скачать Лекцию 15

Лекция 16
Метод включения-исключения перечисления элементов множества, не обладающих заданными свойствами. Задача о беспорядках и задача о встречах.

Скачать Лекцию 16

Лекция 17
Формальные степенные ряды и действия над ними. Производящие функции последовательностей.

Скачать Лекцию 17

Лекция 18
Линейные рекуррентные соотношения и их решение с помощью производящих функций. Числа Фиббоначчи.

Скачать Лекцию 18

Скачать библиографию и экзаменационные вопросы

Скачать весь материал в одном файле