Комбинаторика и теория графов (CS)

Примерная программа экзамена

  1. Граф, ориентированный граф. Вершины, ребра, степени вершин. Сумма степеней вершин.
  2. Отношение экивалентности и классы эквивалентности. Компоненты связности графа и сильной связности ориентированного графа.
  3. Деревья. Несколько определений дерева. Остовное дерево графа.
  4. Матричная теорема о деревьях. Теорема Кэли о числе помеченных деревьев.
  5. Двусвязность. Блочная структура графа.
  6. Связность: теоремы Геринга и Менгера.
  7. Паросочетания. Лемма о девушках (теорема Холла). Обобщенная лемма о девушках, теорема Кенига.
  8. Теорема Дилуорса.
  9. Паросочетания в недвудольном графе. Теорема Татта, формула Бержа.
  10. Эйлеровы пути и циклы. Необходимые и достаточные условия существования в терминах четностей степеней вершин.
  11. Гамильтоновы пути и циклы. Теорема Дирака.
  12. Раскраски графа. Критерий двудольности графа.
  13. Теорема Брукса.
  14. Хроматический многочлен. Подсчет числа ациклических ориентаций.
  15. Покраска ребер. Теорема Визинга.
  16. Плоские и планарные графы. Формула Эйлера.
  17. Оценка числа ребер через число вершин в планарном графе и в планарном графе без треугольников. Непланарность $K_5$ и $K_{3,3}$.
  18. Задача Сильвестра (о конфигурациях прямых и точек.)
  19. Теорема о пяти красках.
  20. Теорема Рамсея.
  21. Следствия теоремы Рамсея: теорема Шура, теорема Эрдеша-Секереша.
  22. Нижнице оценки диагональных чисел Рамсея.
  23. Большие антиклики в графах без треугольников.
  24. Графы с большим обхватом и большим хроматическим числом.
  25. Локальная лемма Ловаса.
  26. Комбинаторная теорема о нулях.
  27. Теорема Коши-Дэвенпорта.
  28. Списочное хроматическое число. Списочное хроматическое число двудольного планарного графа не превосходит 3.
  29. Матроид. Определение матроида через независимые множества. Жадный алгоритм. Примеры матроидов.
  30. Базы, циклы, ранговая функция матроида.
  31. Двойственный матроид. Ранговая функция двойственного матроида.
  32. Прямая сумма матроидов. Образ матроида. Объединение матроидов.
  33. Теорема Радо о независимой трансверсали. Обобщение.
  34. Ранговая функция образа матроида. Ранговая функция объединения матроидов. Теорема Нэша-Уильямса о покрытии графа лесами.

Литература

  • Р. Грэхем, Д. Кнут, О. Паташник. Конкретная математика. Мир, 1998.
  • Т. Кормен, Ч. Лейзерсон, and Р. Ривест. Алгоритмы: построение и анализ. МЦНМО, 2000.
  • М.В. Волков and Н.Н. Силкин. Кого послать на Марс? Квант, 8:51-57, 1988.
  • Н. Алон, Дж. Спенсер. Вероятностный метод. БИНОМ, Лаборатория знаний, 2007.
  • С. Ленг. Алгебра. 1968.
  • В. Липский. Комбинаторика для программистов. Мир, 1988.
  • И.В. Романовский. Дискретный анализ. Невский диалект, 2000.
  • С.К. Ландо. Лекции о производящих функциях. МЦНМО, 2002.
  • Noga Alon. Combinatorial Nullstellensatz. Comb. Probab. Comput., 8(1-2):7-29, 1999.
  • J.A. Bondy and U.S.R. Murty. Graph theory with applications. University of Waterloo, 1982.
  • Peter Bro Miltersen. Handbook on Randomization, volume II, chapter 19. Derandomizing Complexity Classes. Kluwer Academic Publishers, July 2001.