Магазинов: 1, Цена: от 1382 руб. посмотреть все

Лекции посвящены некоторым современным тесно связанным между собой разделам теории графов и гиперграфов. Особый акцент делается на экстремальные задачи, возникающие в этих разделах. Серьезное внимание уделяется алгоритмическому аспекту. Многие темы имеют приложения к исследованиям сети Интернет. В брошюре описаны как классические задачи экстремальной теории графов, так и самые последние наработки в области. Рассказано и о совсем недавних достижениях, впервые излагаемых в русскоязычной литературе. Среди них рамсеевские алгоритмы, свидетельствующие о неожиданной и плодотворной связи между классической теорией Рамсея и задачами отыскания таких "трудных" экстремальных характеристик графа, как, например, размер наибольшей клики. Среди них и алгоритмы, эффективно работающие на случайных графах. Среди них, наконец, и моделирование Интернета как графа. Книга рассчитана на всех, кто интересуется современными приложения­ми математики в области анализа данных. Она будет полезна студентам и аспирантам технических ВУЗов, а также исследователям и разработчикам больших сетей - Интернета, биологических и социальных сетей.

  My-Shop - 1382 руб.

Лекция 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. Моделирование Интернета
Курсовые проекты
Список литературы