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

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

ФорматОнлайн

Длительность5-8 часов в неделю

Объём6 занятий

По окончанииYes

О курсе

Подробнее

В представленном курсе излагаются основы теории графов — факты, понятия и утверждения, знать которые должен любой человек, занимающийся современным программированием или дискретной математикой. Теория графов считается достаточно сложным предметом. В ней нет каких-то базовых методов и подходов, изучив которые, можно научиться решать большинство задач этой науки. Мы, со своей стороны, постарались по возможности облегчить изучение теории графов, излагая материал максимально простым и понятным языком, с большим количеством рисунков и подробными доказательствами основных результатов.

Требования

Что нужно для старта

Нужно уверенно владеть школьным курсом математики.

Аудитория

Для кого этот курс

Студенты математических и IT-специальностей

Содержание

Программа курса

6 занятий

№ТемаЧто внутри

01Основные понятия теории графов

- Основные понятия и определения
- Маршруты, пути, циклы. Понятие связности. Двудольные графы.
- Подграфы. Основные операции над графами
- Изоморфизм и автоморфизм графов

02Деревья и циклы

- Деревья
- Эйлеровы графы
- Гамильтоновы циклы

03Связность в графах

- Вершинная и реберная связность
- Структура двусвязных графов
- k-связные графы
- Потоки и сети

04Паросочетания в графах

- Независимые множества и покрытия графа
- Паросочетания. Теорема Холла
- Паросочетания в произвольных графах

05Раскраска графов

- k-раскрашиваемые графы. Теорема Брукса
- Нижние оценки на хроматическое число
- Хроматический многочлен графа

06Планарные графы

- Основные свойства планарных графов
- Формула Эйлера
- Раскраска планарных графов

01Основные понятия теории графов

02Деревья и циклы

- Деревья
- Эйлеровы графы
- Гамильтоновы циклы

03Связность в графах

- Вершинная и реберная связность
- Структура двусвязных графов
- k-связные графы
- Потоки и сети

04Паросочетания в графах

- Независимые множества и покрытия графа
- Паросочетания. Теорема Холла
- Паросочетания в произвольных графах

05Раскраска графов

06Планарные графы

- Основные свойства планарных графов
- Формула Эйлера
- Раскраска планарных графов

Документ после выпуска

Yes

Организатор

Автор курса

Stepik

4.6Нет отзывов

Stepik — образовательная платформа и конструктор онлайн-курсов. Мы разрабатываем алгоритмы адаптивного обучения, сотрудничаем с авторами MOOC, помогаем в проведении олимпиад и программ переподготовки. Наша цель — сделать образование открытым и удобным. Stepik — широко известная российская образовательная платформа, основанная в 2013 году. На Stepik зарегистрировано более миллиона пользователей из России и стран СНГ. В настоящее время на Stepik представлены несколько тысяч учебных курсов на самые разные темы.

Подробнее об авторе

Мнения учеников