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

Основы перечислительной комбинаторики

Первый семестр

  1. Принцип Дирихле и его обобщение. Пример Эрдёша и Секерёша (о делимости).
  2. Теорема Эрдёша-Секерёша о монотонных последовательностях.
  3. Основные правила перечислительной комбинаторики. Диаграммы Эйлера-Венна.
  4. Принцип включения и исключения.
  5. k-сочетания без повторений. Биномиальные коэффициенты. Формулы суммирования по верхнему индексу и по диагонали. Знакопеременная сумма биномиальных коэффициентов.
  6. k-сочетания с повторениями. Выражение через сочетания без повторений. Принцип биекции.
  7. k-перестановки из n элементов (с повторениями и без них). Биекция со словами фиксированной длины.
  8. Урновые схемы и схемы раскладки предметов по ящикам. Примеры.
  9. Подсчет количества отображений конечных множеств. Количество сюръективных отображений. Явная формула через принцип включения и исключения. Формулы обращения.
  10. Подсчет количества разделений и упорядоченных разбиений множества. Разделения с фиксированным количеством элементов в каждом блоке (мультиномиальные коэффициенты). Перестановки с повторениями.
  11. Раскладки различимых предметов по неразличимым ящикам. Числа Стирлинга 2-го рода, рекуррентное соотношение для них. Связь с сюръективными отображениями.
  12. Числа Белла, их комбинаторный смысл, выражение через числа Стирлинга 2-го рода, рекуррентное соотношение для чисел Белла.
  13. Рекуррентные соотношения. Основные определения: линейность, однородность, характеристическое уравнение. Методы решения, не использующие производящие функции. Формулы для решения рекуррентных соотношений второго порядка, включая случаи корня кратности два, комплексных корней. Числа Фибоначчи.
  14. Производящие функции числовых последовательностей. Обыкновенные и экспоненциальные производящие функции. Формальные степенные ряды, их сложение и умножение. Производные производящих функций.
  15. Ряды Тейлора для некоторых элементарных функций (e^x, 1/(1-a*z)^k). Доказательство формулы обращения с помощью ряда для e^x.
  16. Построение решений линейных рекуррентных соотношений с постоянными коэффициентами с помощью обыкновенных производящих функций.
  17. Построение решений линейных рекуррентных соотношений с переменными коэффициентами с помощью экспоненциальных производящих функций. Учёт начальных условий, сведение к задаче Коши.
  18. Нелинейные рекуррентные соотношения. Числа Каталана. Рекуррентное соотношение и производящая функция для чисел Каталана.
  19. Различные задачи, связанные к числами Каталана: количество бинарных деревьев, триангуляций, слов Дика. Доказательство Андрэ явной формулы для чисел Каталана.
  20. Дискретная вероятность, основные определения: элементарный исход, событие, вероятность, совместность событий, вероятностное пространство, независимость событий, условная вероятность.
  21. Формула полной вероятности, формула Байеса. Нахождение наиболее вероятной гипотезы.
  22. Случайные величины, их независимость. Характеристики случайных величин: математическое ожидание и дисперсия. Их свойства. Использование производящих функций для их вычисления. Неравенство Чебышёва.
  23. Схема Бернулли. Распределение Пуассона.
  24. Цепи Маркова, основные определения. Аналогия с конечными автоматами. Использование производящих функций для вычисления вероятностей обнаружить марковский процесс в некотором состоянии.

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

  1. Основные понятия теории графов (граф, орграф, мультиграф, подграф; дополнение к графу; изоморфизм, автоморфизм; пути, маршруты; расстояние, эксцентриситет, радиус, диаметр). Теорема о связи суммы степеней вершин и количества рёбер. Сильная и слабая связность в орграфах. Граф компонент сильной связности.
  2. Деревья. Несколько эквивалентных определений дерева.
  3. Формула Кэли и её доказательство с помощью кода Прюфера.
  4. Эйлеровы и гамильтоновы циклы. Основные определения. Необходимое и достаточное условие существование эйлерова цикла в графе. Следствие об эйлеровом пути.
  5. Лемма о достаточном условии существования в графе гамильтонова цикла.
  6. Теоремы Оре и Дирака.
  7. Два подхода к поиску кратчайшей циклической строки, содержащей все строки данной длины над данным алфавитом. Граф де Брёйна.
  8. Критерий двудольности графа.
  9. Раскраски графов, основные определения. Хроматическое число. Примеры задач, в которых возникает необходимость его поиска. Жадный алгоритм раскраски. Следствие о связи хроматического числа и наибольшей степени вершины.
  10. Теорема Брукса.
  11. Нижняя оценка хроматического числа. Графы без треугольников с большими хроматическими числами. Обхват графа. Теорема Эрдёша (без доказательства).
  12. Совершенные графы. Интервальные графы. Сильная и слабая гипотезы Бержа (без доказательства). Теорема Визинга (без доказательства).
  13. Хроматический многочлен. Рекуррентная формула для вычисления и доказательство того, что такая функция — действительно многочлен. Утверждения о коэффициентах. Кратность корня, равного нулю.
  14. Теория Рамсея, основные определения. Теорема Эрдёша-Секерёша и верхние оценки чисел Рамсея.
  15. Обобщения простейшей формулировки теоремы Рамсея. Применения теоремы Рамсея: теорема Эрдёша-Секерёша (о существовании в наборе точек выпуклого n-угольника), другие примеры.
  16. Связность графов, основные определения (различные типы связности; разрезы, разделяющие множества). Теорема: вершинная связность не больше рёберной.
  17. Двусвязность. Эквивалентные определения двусвязности (с доказательством эквивалентности). Блоки и точки сочленения. Мосты. Разложения графов на ручки и замкнутые ручки.
  18. Вершинная теорема Менгера.
  19. Следствия теоремы Менгера: теорема Уитни, утверждение о k-веере.
  20. Потоки в сетях, основные определения. Теорема Форда-Фалкерсона.
  21. Рёберная теорема Менгера.
  22. Паросочетания, основные определения. Теорема Бержа. Примеры задач, связанные с поиском паросочетаний.
  23. Теорема Холла.
  24. Теорема Кёнига-Эгервари. Переформулировка в матричном виде.