Экстремальные задачи теории графов и Интернет (Райгородский Андрей Михайлович) ; Интеллект групп, 2012

Лекция 1. Основные объекты теории графов
1.1. Введение
1.2. Основные объекты теории графов
1.2.1. Графы, орграфы и пр.
1.2.2. Маршруты в графах
1.2.3. Связность
1.2.4. Независимые множества и клики
1.3. Двудольные графы
1.3.1. Определение и мотививировка
1.3.2. Связь с задачей о покрытии
Лекция 2. Несколько базовых алгоритмов на
графах
2.1. Алгоритм Хопкрофта-Карпа
2.2. Алгоритм Дейкстры
2.3. Алгоритм Беллмана-Форда
2.4. Реализация последовательностей чисел
степенями вершин графа
Задачи к лекциям 1 и 2
Лекция 3. Системы общих представителей
3.1. Определение системы общих представителей
3.2. Верхняя оценка для размера минимальной с.о.п
3.3. Доказательство теоремы 3.2.1
3.4. Нижняя оценка для размера минимальной с.о.п
3.5. Доказательство теоремы 3.4.1
3.6. Уточнения теоремы 3.4.1
Лекция 4. Размерность Вапника-Червоненкиса
4.1. Размерность Вапника-Червоненкиса:
определение и примеры
4.2. Постановка задачи об Е-сетях
4.3. Формулировки результатов
4.4. Идея доказательства теоремы 4.3.1 и
комментарии
4.5. О покрытии графов более простыми графами
Задачи к лекциям 3 и 4
Лекция 5. Числа Рамсея
5.1. Числа Рамсея: определения и формулировки
результатов
5.2. Доказательство теоремы 5.1.2
5.3. Доказательство следствия 5.1.2
5.4. Конструктивные оценки чисел Рамсея
5.5. Доказательство теоремы 5.4.1
5.6. Доказательство следствия 5.4.1
5.7. Двудольные числа Рамсея
Лекция 6. Случайные графы
6.1. Случайные графы: определение
6.2. Случайные графы: простейшие свойства
6.3. Связность случайного графа
6.4. Хроматическое число случайного графа
6.5. Законы нуля и единицы
Задачи к лекциям 5 и 6
Лекция 7. Алгоритмы в некоторых "трудных"
задачах теории графов
7.1. О задачах отыскания хроматического числа,
числа независимости и кликового числа
7.2. Алгоритм Кривелевича-Ву: формулировки
результатов
7.3. Доказательство теоремы 7.2.1
7.3.1. Вспомогательные определения и факты
7.3.2. Построение алгоритма
7.3.3. Пояснения к работе алгоритма
Лекция 8. Рамсеевские алгоритмы
8.1. Еще об отыскании клик
8.2. Несколько слов о Рамсеевском алгоритме
8.3. Уточнение Рамсеевского алгоритма
Задачи к лекциям 7 и 8
Лекция 9. Обходы графов и их приложения
9.1. Эйлеровы графы
9.2. Эйлеровы графы и последовательности де
Брёйна
9.3. Гамильтоновы графы
9.3.1. Определение гамильтоновости и связь с
эйлеровостью
9.3.2. Необходимые и достаточные условия
гамильтоновости
9.3.3. Алгоритмы поиска гамильтоновых циклов
9.3.4. Гамильтоновы циклы в турнирах
9.3.5. Гамильтоновы циклы в случайных графах
Лекция 10. Задачи о пересечениях и проблема
изоморфизма
10.1. Графы пересечений
10.1.1. Постановка задачи и формулировки
результатов
10.1.2. Доказательство теоремы Эрдеша-Ко-Радо
10.1.3. Доказательство гипотезы Кнезера
10.2. Проблема изоморфизма графов
10.2.1. Определение изоморфизма и несколько
слов об истории вопроса
10.2.2. Проблема изоморфизма "почти
наверное": формулировка результата
10.2.3. Проблема изоморфизма "почти наверное":
вспомогательное утверждение
10.2.4. Доказательство теоремы 10.2.2.1
Задачи к лекциям 9 и 10
Лекция 11. Моделирование Интернета
Курсовые проекты
Список литературы