О курсе
Матрица смежности, маршруты, дополнение и изоморфизм, расстояния и диаметр. Мосты, деревья, код Прюфера и формула Кэли, число остовных деревьев. Эйлеровы маршруты и задача почтальона, условия Дирака и Оре, гиперкуб и код Грея. Двудольные графы, теоремы Кёнига и Холла, устойчивые паросочетания. Раскраска вершин и рёбер, хроматический многочлен. Формула Эйлера, оценки числа рёбер, теорема Куратовского. Алгоритмы Беллмана — Форда и Флойда — Уоршелла, потоки и теорема Менгера, теоремы Мантеля и Рамсея. Продолжение дискретной математики.
Программа курса: 33 урока
Графы, матрицы, расстояния
- Матрица смежности и маршруты
- Дополнение и изоморфизм
- Расстояния, диаметр, радиус
- Контроль: матрицы, изоморфизм, расстояния
Связность и деревья
- Мосты и точки сочленения
- Деревья и лес
- Код Прюфера и формула Кэли
- Число остовных деревьев
- Контроль: связность и деревья
Эйлер и Гамильтон
- Эйлеровы маршруты и почтальон
- Гамильтоновы циклы: Дирак и Оре
- Гиперкуб и код Грея
- Контроль: Эйлер и Гамильтон
Двудольные графы и паросочетания
- Двудольные графы
- Паросочетания и вершинные покрытия
- Теорема Холла и дефицит
- Устойчивые паросочетания
- Контроль: двудольные графы и паросочетания
Раскраска
- Хроматическое число и оценки
- Хроматический многочлен
- Рёберная раскраска
- Контроль: раскраска
Планарность
- Формула Эйлера для плоских графов
- Оценки рёбер планарного графа
- Теорема Куратовского
- Контроль: планарность
Пути, потоки, экстремальные задачи
- Алгоритм Беллмана — Форда
- Алгоритм Флойда — Уоршелла
- Потоки: увеличивающие пути
- Теорема Менгера и связность
- Теоремы Мантеля и Рамсея
- Контроль: пути, потоки, экстремальные задачи
Итоговый тест
- Итоговый тест по теории графов