Stepik О курсе
Подробнее
Данный курс предназначен для тех слушателей, которые хотят прослушать полный курс графов в объеме, примерно соответствующем аналогичному курсу, читаемому студентам-бакалаврам 2-го курса, обучающихся по программе "Прикладная математика и информатика" на факультете "Санкт-Петербургская школа физико-математических и компьютерных наук". Курс охватывает все основные разделы теории графов, необходимые как программистам, так и математикам, работающим в области дискретной математики.
Содержание
12 занятийПрограмма курса
№ТемаЧто внутри
01Основные понятия теории графов
- Основные понятия и определения
- Маршруты, пути, циклы. Понятие связности. Двудольные графы.
- Подграфы. Основные операции над графами
- Изоморфизм и автоморфизм графов
02Деревья и их перечисление
- Деревья
- Формула Кэли для подсчета всех помеченных деревьев
- Подсчет остовных деревьев в графе
03Циклы в графах
- Эйлеровы графы
- Гамильтоновы циклы
- Графы Де Брейна
04Связность в графах - 1
- Вершинная и реберная связность
- Структура двусвязных графов
05Связность в графах - 2
- k-связные графы
- Потоки и сети
06Паросочетания в графах - 1
- Независимые множества и покрытия графа
- Паросочетания. Теорема Холла
07Паросочетания в графах - 2
- Совершенные паросочетания в произвольном графе
- Максимальные паросочетания в произвольном графе
08Раскраска графов - 1
- k-раскрашиваемые графы. Теорема Брукса
- Нижние оценки на хроматическое число
- Реберная раскраска графов
09Раскраска графов - 2
- Совершенные графы
- Хроматический многочлен графа
10Планарные графы - 1
- Критерии планарности графов
- Формула Эйлера
- Раскраска планарных графов
11Планарные графы - 2
- Критерии планарности графов
- Карты на поверхностях
12Теория Рамсея и экстремальная теория графов
- Принцип Дирихле
- Начала теории Рамсея
- Экстремальная теория графов
01Основные понятия теории графов
- Основные понятия и определения
- Маршруты, пути, циклы. Понятие связности. Двудольные графы.
- Подграфы. Основные операции над графами
- Изоморфизм и автоморфизм графов
02Деревья и их перечисление
- Деревья
- Формула Кэли для подсчета всех помеченных деревьев
- Подсчет остовных деревьев в графе
03Циклы в графах
- Эйлеровы графы
- Гамильтоновы циклы
- Графы Де Брейна
04Связность в графах - 1
- Вершинная и реберная связность
- Структура двусвязных графов
05Связность в графах - 2
- k-связные графы
- Потоки и сети
06Паросочетания в графах - 1
- Независимые множества и покрытия графа
- Паросочетания. Теорема Холла
07Паросочетания в графах - 2
- Совершенные паросочетания в произвольном графе
- Максимальные паросочетания в произвольном графе
08Раскраска графов - 1
- k-раскрашиваемые графы. Теорема Брукса
- Нижние оценки на хроматическое число
- Реберная раскраска графов
09Раскраска графов - 2
- Совершенные графы
- Хроматический многочлен графа
10Планарные графы - 1
- Критерии планарности графов
- Формула Эйлера
- Раскраска планарных графов
11Планарные графы - 2
- Критерии планарности графов
- Карты на поверхностях
12Теория Рамсея и экстремальная теория графов
- Принцип Дирихле
- Начала теории Рамсея
- Экстремальная теория графов
Организатор
Автор курса
Мнения учеников
Отзывы о курсе
Оставьте отзыв
Расскажите о качестве обучения, поддержке и результате. Это поможет другим выбрать организацию осознанно.
Оставьте заявку
Консультант ответит на вопросы о курсе «Теория графов» и поможет разобраться в деталях обучения.
Нажимая кнопку, вы даете согласие на обработку персональных данных
Направления:Математика
Информация обновлена 3 сентября 2026 г.
Продолжить выбор
Похожие курсы
Начать без затрат
