Обложка Райгородский А.М. Экстремальные задачи теории графов и интернет
Id: 165988
599 руб.

Экстремальные задачи теории графов и интернет

2012. 104 с. ISBN 978-5-91559-127-0.
  • Мягкая обложка

Аннотация

Настоящая брошюра посвящена изучению различных экстремальных задач теории графов, (хотя бы частичное) решение которых может быть полезно при анализе данных. Она возникла на основе семестрового курса лекций, прочитанных автором в Школе Анализа Данных Яндекса.

Рассмотрим одну естественную конструкцию, которая послужит своего рода мотивировкой для всей нашей дальнейшей деятельности. Современный Интернет — это огромная и крайне нетривиально устроенная... (Подробнее)


Оглавление

Лекция 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.

11.1. Курсовые проекты

Литература