Stepik О курсе
Подробнее
Теория графов используется повсеместно в математике и компьютерных науках, поскольку изучает попарные связи между объектами. Мы познакомимся с основными понятиями теории графов (деревья, циклы, потоки, паросочетания, раскраски, укладки).
Вы увидите много применений теории графов в компьютерных науках (в частности, много кода на Python) и много примеров и визуализаций, а также решите более сорока задач. Мы поможем вам в этом: для каждой задачи мы приводим подробное решение, а также быстро отвечаем на вопросы на форуме.
Требования
Что нужно для старта
- Знание математики на школьном уровне.
Результат
Что вы получите
- Моделировать возникающие на практике задачи в терминах теории графов
- Пользоваться разными алгоритмами на графах
- Пользоваться графами в Python
- Оценивать разные параметры графов
Аудитория
Для кого этот курс
- Для всех, кто хочет разобраться в математических основах компьютерных наук. Несколько первых уроков курса открыты и помогут вам понять, будет ли курс вам интересен.
Содержание
8 занятийПрограмма курса
№ТемаЧто внутри
01О курсе
- Добро пожаловать!
02Что такое граф?
- Графы
- Определения
- Базовые графы
- Формула суммы степеней
- Компоненты связности
03Деревья
- Введение
- Минимальное остовное дерево
- Динамическое программирование
- Формула Кэли
- Матричная теорема о деревьях (опционально)
04Циклы
- Ациклические графы
- Компоненты сильной связности
- Эйлеровы графы
- Гамильтоновы графы
- Задача коммивояжёра
- Применение: Сборка генома
05Потоки и связность
- Связность
- Потоки
- Теорема Форда--Фалкерсона
- Теорема Менгера
- Паросочетания в двудольных графах
- Применение: Выбор проектов
- Применение: Сегментация изображений
06Паросочетания
- Независимые множества и покрытия: определения и соотношения
- Независимые множества
- Двудольные графы
- Вершинное покрытие
- Применение: Устойчивое паросочетание
07Раскраски
- Введение
- Раскраски и степень
- Раскраски и клики
- Нелокальность хроматического числа (опционально)
- Хроматический многочлен
- Применение: Алгоритмы нахождения раскраски (опционально)
08Планарные графы
- Планарные графы
- Формула Эйлера
- Непланарные графы
- Число пересечений
- Раскраска планарных графов
- Теоремы Куратовского и Вагнера
- Специальные укладки
01О курсе
- Добро пожаловать!
02Что такое граф?
- Графы
- Определения
- Базовые графы
- Формула суммы степеней
- Компоненты связности
03Деревья
- Введение
- Минимальное остовное дерево
- Динамическое программирование
- Формула Кэли
- Матричная теорема о деревьях (опционально)
04Циклы
- Ациклические графы
- Компоненты сильной связности
- Эйлеровы графы
- Гамильтоновы графы
- Задача коммивояжёра
- Применение: Сборка генома
05Потоки и связность
- Связность
- Потоки
- Теорема Форда--Фалкерсона
- Теорема Менгера
- Паросочетания в двудольных графах
- Применение: Выбор проектов
- Применение: Сегментация изображений
06Паросочетания
- Независимые множества и покрытия: определения и соотношения
- Независимые множества
- Двудольные графы
- Вершинное покрытие
- Применение: Устойчивое паросочетание
07Раскраски
- Введение
- Раскраски и степень
- Раскраски и клики
- Нелокальность хроматического числа (опционально)
- Хроматический многочлен
- Применение: Алгоритмы нахождения раскраски (опционально)
08Планарные графы
- Планарные графы
- Формула Эйлера
- Непланарные графы
- Число пересечений
- Раскраска планарных графов
- Теоремы Куратовского и Вагнера
- Специальные укладки
Организатор
Автор курса
Мнения учеников
Отзывы о курсе
Оставьте отзыв
Расскажите о качестве обучения, поддержке и результате. Это поможет другим выбрать организацию осознанно.
Оставьте заявку
Консультант ответит на вопросы о курсе «Теория графов» и поможет разобраться в деталях обучения.
Нажимая кнопку, вы даете согласие на обработку персональных данных
Направления:Математика
Информация обновлена 14 сентября 2026 г.
Продолжить выбор
Похожие курсы
Начать без затрат
