Графы и комбинаторика: от жемчужин теории к современным приложениям

Модули и структура курса

1 Основные понятия и классические задачи теории графов 7 лекций

Видеолекции 7

• Введение 0:00
• Задача о Кенигсбергских мостах 0:00
• Определение графа 0:00
• Примеры графов 0:00
• Маршруты в графе 0:00
• Эквивалентные определения дерева 0:00
• Эйлеровские графы 0:00

Тест к модулю

2 Графы.Первые задачи 8 лекций

Видеолекции 8

• Деревья Кэли 0:00
• Как закодировать дерево 0:00
• Как раскодировать граф 0:00
• Проблема четырёх красок 0:00
• Задача о рукопожатиях 0:00
• Числа Рамсея 0:00
• Кликовое число и число независимости 0:00
• Раскраска плоскости 0:00

Тест к модулю

3 Вероятность и графы 9 лекций

Видеолекции 9

• Классическое определение вероятности. 0:00
• Совпадут ли дни рождения? 0:00
• Независимые события и условная вероятность. 0:00
• Испытания Бернулли. 0:00
• Биноминальные коэффициенты. 0:00
• Случайный граф - что это такое? 0:00
• Случайная величина и её математическое ожидание. 0:00
• Линейность математического ожидания. 0:00
• Неравенства Маркова и Чебышёва. 0:00

Домашнее задание

Тест к модулю

4 Треугольники в случайном графе 6 лекций

Видеолекции 6

• Есть ли у случайного графа треугольники? 0:00
• Пределы 0:00
• Когда треугольников почти наверное нет 0:00
• Когда треугольники почти наверное есть. Начало 0:00
• Когда треугольники почти наверное есть. Второй момент 0:00
• Победа – треугольники всё-таки есть! 0:00

Тест к модулю

5 Числа Рамсея и связность графа 7 лекций

Видеолекции 7

• Связен ли наш граф 0:00
• О пользе железных дорог 0:00
• Когда граф связен 0:00
• Фазовый переход от связности к несвязности 0:00
• Когда граф несвязен 0:00
• Числа Рамсея - они быстро растут 0:00
• Графы, которых никто не видел 0:00

Тест к модулю

6 Хроматическое число 6 лекций

Видеолекции 6

• Какая оценка лучше? 0:00
• Кто быстрее 0:00
• Коротких циклов не слишком много 0:00
• Девушки и ожерелья 0:00
• Больших независимых множеств нет 0:00
• Как удалить циклы? 0:00

  7 Интернет-графы 6 лекций

Видеолекции 6

• Как устроен веб-граф ? 0:00
• Два удивительных наблюдения 0:00
• Степенной закон распределения степеней вершин 0:00
• Надо ли менять модель? 0:00
• Каков закон распределения вершин в модели Эрдеша-Реньи? 0:00
• Модель Боллобаша-Риордана 0:00

  8 Выходим на приложения 3 лекции

Видеолекции 3

• Теоремы на основе исследований Боллобаша и Риордана? 0:00
• Работаем с оговоркаи и ограничениями 0:00
• Приложение теории для поисковых систем 0:00

Цель изучения курса

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

Необходимый уровень подготовки

Необходимо знать основы комбинаторики, т.е. числа сочетаний и бином Ньютона, а также полезно иметь представление о том, что такое квантор ("для любого", "существует"), что бывают взаимно однозначные соответствия между множествами.

Результаты изучения курса

Слушатель познакомится с некоторыми объектами теории графов, с несколькими наиболее яркими задачами теории, а также узнает о приложениях теории в современных информационных технологиях и не только в них.