Курс на Stepik
Обложка курса «Основы теории графов» на Stepik
Бесплатно

Основы теории графов ★ 4.455

Открыть на
STEPIK.ORG

Лаборатория Алгоритмической математики. Курс создан с целью отработки базовых алгоритмов и теоретических знаний по теории графов, математической логики и теории алгоритмов.

Показатель Текущие показатели Рост
Значение 🏆 Рейтинг 3 дн 7 дн 30 дн
Количество учеников на курсе «Основы теории графов»Учеников на курсе 3 312
Сертификаты, выданные на курсе «Основы теории графов»Сертификатов выдано 0
Отзывы о курсе «Основы теории графов»Отзывов получено 11
Рейтинг курса «Основы теории графов»Рейтинг курса 4.455
Уроки в курсе «Основы теории графов»Количество уроков 37
Тесты в курсе «Основы теории графов»Количество квизов 74
Задачи с кодом в курсе «Основы теории графов»Количество задач с кодом 22
Время прохождения курса «Основы теории графов»Время прохождения курса —
Обновления курса «Основы теории графов»Обновления курса — —
Дата публикации курса «Основы теории графов»Дата публикации курса — ———
Последнее обновление курса «Основы теории графов»Последнее обновление — ———

Содержание курса

Разделы в курсе «Основы теории графов» 13 разделов Уроки в курсе «Основы теории графов» 37 уроков Тесты в курсе «Основы теории графов» 74 теста Задачи в курсе «Основы теории графов» 22 задачи Время прохождения курса «Основы теории графов» 1 ч. Последнее обновление курса «Основы теории графов» обн. 10 августа 2026

Введение

1 урок
1. Общая информация о курсе ↗

Графы и бинарные отношения. Поиск в глубину и в ширину

2 урока
1. Простейшие определения и свойства графов ↗
2. Поиск в глубину и в ширину ↗

Алгоритм Косарайю и Шарира. Алгоритм Флёри.

2 урока
1. Связность, поиск мостов и компонент связности. ↗
2. Эйлеров путь в графе. Необходимые алгоритмы. ↗

Деревья

3 урока
1. Свойства и определения. Теорема Кэли ↗
2. Обход дерева ↗
3. Код Прюфера ↗

Метод поиска с возвратом и метод ветвей и границ

2 урока
1. Метод поиска с возвратом ↗
2. Метод ветвей и границ ↗

Каркасы. Главные циклы и разрезы.

2 урока
1. Каркасы ↗
2. Главные циклы и разрезы ↗

Жадные алгоритмы Прима и Краскала.

4 урока
1. Остовные деревья ↗
2. Алгоритм Прима ↗
3. Алгоритм Краскала ↗
4. Смешанные задачи ↗

Двудольные графы. Теорема Кёнига, паросочетания.

3 урока
1. Двудольные графы ↗
2. Теорема Кёнига ↗
3. Паросочетания ↗

Планарность

4 урока
1. Изоморфность графов ↗
2. Теорема Эйлера ↗
3. Гомеоморфизм графов ↗
4. Раскраска графов ↗

Алгоритмы Форда-Беллмана, Дейкстры и Флойда.

5 уроков
1. Введение ↗
2. Алгоритм Дейкстры ↗
3. Алгоритм Беллмана-Форда ↗
4. Алгоритм Флойда-Уоршелла ↗
5. Алгоритм Ли (волновой алгоритм) ↗

Эвристические алгоритмы поиска: муравьиный алгоритм, алгоритм A*

2 урока
1. Муравьиный алгоритм ↗
2. Алгоритм A* ↗

Свойства бинарных отношений

5 уроков
1. Свойства бинарных отношений. Способы задания ↗
2. Отношения эквивалентности и толерантности, предпорядка и порядка ↗
3. Метод раскраски. Алгоритм топологической сортировки ↗
4. Операции над отношениями ↗
5. Частично упорядоченные множества, диаграмма Хассе ↗

Транзитивное замыкание бинарного отношения. Алгоритм Уоршелла.

2 урока
1. Транзитивное замыкание бинарного отношения ↗
2. Алгоритм Уоршелла ↗