Курс «Теория графов» от платформы Stepik ориентирован на студентов технических специальностей, обучающихся программированию или имеющих в учебной программе дискретную математику.
Это подробный курс теории графов, включающий в себя все базовые разделы.
Вам подойдет этот курс, если вы:
- студент технической специальности;
- хотите познакомиться поближе с таким разделом математики, как теория графов;
- программист и желаете вспомнить теорию графов для работы.
Ключевые навыки, которые вы освоите на этом курсе:
- операции над графами;
- подсчет остовных деревьев в графе;
- подсчет циклов в графах;
- раскраска графов.
Учебная программа:
- базовые концепции теории графов; циклы, пути, маршруты, изоморфизм, автоморфизм, связность графов;
- деревья, подсчет остовных деревьев, формула Кэли;
- циклы на графах;
- связность графов. Часть I: двусвязные графы, реберная связность, вершинная связность;
- связность графов. Часть II: сети, потоки, k-связные графы;
- паросочетания в графах. Часть I: теорема Холла, независимые множества;
- паросочетания в графах. Часть II: совершенные и максимальные паросочетания;
- раскраска графов. Часть I: реберная раскраска, теорема Брукса, нижняя оценка для хроматического числа графа;
- раскраска графов. Часть II: хроматический многочлен, семейства совершенных графов;
- планарные графы. Часть I: раскраска, критерии, формула Эйлера;
- планарные графы. Часть II: критерии, графы на поверхностях;
- теорема Рамсея, принцип Дирихле, экстремальная теория.
Курс состоит из 12 модулей, туда входят интерактивные задачи, рисунки, конкретные примеры и тесты. Есть задачи на программирование.
По окончании обучения выдается сертификат.
Вступительное видео к курсу «Теория графов»: