На практике встречается ряд задач, где фундаментальные знания математического анализа не дают существенных результатов.
Но при этом содержание таких задач как правило злободневно. Что же делать? Нужно уметь распознавать в таких задачах модели с графом.
Курс по Теории графов научит вас это делать.
О курсе
писать алгоритмы на языке Python для решения этих задач.
Для успешного завершения курса каждый студент должен выполнить лабораторную работу по нескольким темам, включающую решение задачи и написание программного кода.
⠀⠀⠀⠀• Основные понятия и определения теории графов
⠀⠀⠀⠀• Маршруты, пути, циклы в графе. Связные графы и орграфы
⠀⠀⠀⠀• Изоморфизм и автоморфизм графов
⠀⠀⠀⠀• Основные свойства деревьев
⠀⠀⠀⠀• Пересечение деревьев. Формула Кэли
⠀⠀⠀⠀• Подсчет остовных деревьев в графе. Матричная теорема о деревьях
⠀⠀⠀⠀• Эйлеровы циклы
⠀⠀⠀⠀• Гамильтоновы циклы
⠀⠀⠀⠀• Линейное пространство ребер. Циклы и разрезы
⠀⠀⠀⠀• Циркуляции и напряжения. Электрические сети
⠀⠀⠀⠀• Вершинная и реберная связность графа
⠀⠀⠀⠀• Двусвязные графы
⠀⠀⠀⠀• k-связные графы. Теорема Менгера
⠀⠀⠀⠀• Теорема Форда-Фалкерсона
⠀⠀⠀⠀• Понятие паросочетания. Теорема Бержа. Независимые множества и покрытия
⠀⠀⠀⠀графа
⠀⠀⠀⠀• Паросочетания в двудольных графах. Алгоритм Куна поиска максимального
⠀⠀⠀⠀паросоче тания в двудольном графе
⠀⠀⠀⠀• Совершенные паросочетания в произвольном графе. Теорема Татта
⠀⠀⠀⠀• Максимальные паросочетания в произвольном графе. Структурная теорема
⠀⠀⠀⠀Галлаи Эдмондса. Алгоритм Эдмондса
⠀⠀⠀⠀• k-раскрашиваемые графы. Теорема Брукса. Нижние оценки на хроматическое
⠀⠀⠀⠀число. Теорема Турана. Совершенные графы
⠀⠀⠀⠀• Реберная раскраска графов
⠀⠀⠀⠀• Хроматический многочлен графа
⠀⠀⠀⠀• Планарные графы и их свойства
⠀⠀⠀⠀• Формула Эйлера для плоских графов
⠀⠀⠀⠀• Критерии планарности графов. Теорема Куратовского.
• Основные понятия и определения теории графов
• Маршруты, пути, циклы в графе. Связные графы и орграфы
• Изоморфизм и автоморфизм графов
• Основные свойства деревьев
• Пересечение деревьев. Формула Кэли
• Подсчет остовных деревьев в графе. Матричная теорема о деревьях
• Эйлеровы циклы
• Гамильтоновы циклы
• Линейное пространство ребер. Циклы и разрезы
• Циркуляции и напряжения. Электрические сети
• Вершинная и реберная связность графа
• Двусвязные графы
• k-связные графы. Теорема Менгера
• Теорема Форда-Фалкерсона
• Понятие паросочетания. Теорема Бержа. Независимые множества и покрытия графа
• Паросочетания в двудольных графах. Алгоритм Куна поиска максимального
паросоче тания в двудольном графе
• Совершенные паросочетания в произвольном графе. Теорема Татта
• Максимальные паросочетания в произвольном графе. Структурная теорема
Галлаи Эдмондса. Алгоритм Эдмондса
• k-раскрашиваемые графы. Теорема Брукса. Нижние оценкина хроматическое число. Теорема Турана. Совершенные графы
• Реберная раскраска графов
• Хроматический многочлен графа
• Планарные графы и их свойства
• Формула Эйлера для плоских графов
• Критерии планарности графов. Теорема Куратовского.
