Высшая математика: теория графов

О курсе

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

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

Графы, матрицы, расстояния

  1. Матрица смежности и маршруты
  2. Дополнение и изоморфизм
  3. Расстояния, диаметр, радиус
  4. Контроль: матрицы, изоморфизм, расстояния

Связность и деревья

  1. Мосты и точки сочленения
  2. Деревья и лес
  3. Код Прюфера и формула Кэли
  4. Число остовных деревьев
  5. Контроль: связность и деревья

Эйлер и Гамильтон

  1. Эйлеровы маршруты и почтальон
  2. Гамильтоновы циклы: Дирак и Оре
  3. Гиперкуб и код Грея
  4. Контроль: Эйлер и Гамильтон

Двудольные графы и паросочетания

  1. Двудольные графы
  2. Паросочетания и вершинные покрытия
  3. Теорема Холла и дефицит
  4. Устойчивые паросочетания
  5. Контроль: двудольные графы и паросочетания

Раскраска

  1. Хроматическое число и оценки
  2. Хроматический многочлен
  3. Рёберная раскраска
  4. Контроль: раскраска

Планарность

  1. Формула Эйлера для плоских графов
  2. Оценки рёбер планарного графа
  3. Теорема Куратовского
  4. Контроль: планарность

Пути, потоки, экстремальные задачи

  1. Алгоритм Беллмана — Форда
  2. Алгоритм Флойда — Уоршелла
  3. Потоки: увеличивающие пути
  4. Теорема Менгера и связность
  5. Теоремы Мантеля и Рамсея
  6. Контроль: пути, потоки, экстремальные задачи

Итоговый тест

  1. Итоговый тест по теории графов