Теория графов

Курс охватывает все основные разделы теории графов, необходимые как программистам, так и математикам, работающим в области дискретной математики. 

Теория графов
Бесплатно
31 урок31 урок
Сертификат гос. образцаСертификат гос. образца
РусскийРусский
Stepik

Описание:

Данный курс предназначен для тех слушателей, которые хотят прослушать полный курс графов в объеме, примерно соответствующем аналогичному курсу, читаемому студентам-бакалаврам 2-го курса, обучающихся по программе "Прикладная математика и информатика" на факультете "Санкт-Петербургская школа физико-математических и компьютерных наук". Курс охватывает все основные разделы теории графов, необходимые как программистам, так и математикам, работающим в области дискретной математики. 

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

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

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

Деревья и их перечисление

  1. Деревья
  2. Формула Кэли для подсчета всех помеченных деревьев
  3. Подсчет остовных деревьев в графе

Циклы в графах

  1. Эйлеровы графы
  2. Гамильтоновы циклы
  3. Графы Де Брейна

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

  1. Вершинная и реберная связность
  2. Структура двусвязных графов

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

  1. k-связные графы
  2. Потоки и сети

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

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

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

  1. Совершенные паросочетания в произвольном графе
  2. Максимальные паросочетания в произвольном графе

Раскраска графов - 1

  1. k-раскрашиваемые графы. Теорема Брукса
  2. Нижние оценки на хроматическое число
  3. Реберная раскраска графов

Раскраска графов - 2

  1. Совершенные графы
  2. Хроматический многочлен графа

Планарные графы - 1

  1. Критерии планарности графов
  2. Формула Эйлера
  3. Раскраска планарных графов

Планарные графы - 2

  1. Критерии планарности графов
  2. Карты на поверхностях

Теория Рамсея и экстремальная теория графов

  1. Принцип Дирихле
  2. Начала теории Рамсея
  3. Экстремальная теория графов