Основы дискретной математики

Санкт-Петербург, осень 2015

Описание

Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики.

Преподаватели

Список лекций

Элементарная комбинаторика

Основные комбинаторные величины и простейшие комбинаторные формулы. Числа размещения и сочетания (с повторениями и без повторений). Бином Ньютона и биномиальные коэффициенты. Простейшие соотношения на биномиальные коэффициенты. Треугольник Паскаля. Обобщение бинома Ньютона и мультиномиальные коэффициенты. Семейства подмножеств конечного множества.

Группа перестановок

Четность перестановки, разложение в произведение транспозиций, разбиение на циклы, четность цикла, классы сопряженных и циклический тип перестановки.

Разбиения числа в сумму слагаемых

Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Диаграммы Юнга. Рекуррентные соотношения для функций разбиения. Теоремы Харди- Рамануджана (б/д).

Рекуррентные соотношения. Числа Каталана и числа Белла

Рекуррентные соотношения. Числа Каталана и числа Белла. Различные интерпретации чисел Каталана.

Методы линейной алгебры в комбинаторике

Использование линейной алгебры для доказательства комбинаторных результатов. Различные примеры использования этого метода (неравенство Фишера, (n,k)-плотные множества, множества с двумя расстояниями и т.д.)

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

Графы и орграфы. Основные определения. Матрицы смежности и инцидентности. Маршруты, пути и циклы. Связность, компоненты связности. Деревья и их свойства. Двусвязные графы и блоки. Дерево блоков и точек сочленения.

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

Связность орграфов: различные виды связности, компоненты сильной связности, граф компонент. Турнирные графы. Гамильтоновы пути в турнирном графе. Теорема Редеи (б/д). Циклы в сильно связных турнирах. Теорема Муна.

Раскраски графов

Двудольные графы, критерий двудольности. Вершинные и реберные раскраски графа. Простейшие свойства раскрасок. Теорема Брукса. Теоремы Визинга и Гупты (б/д). Совершенные графы. Слабая и сильная гипотезы Бержа: доказательство слабой гипотезы.

Паросочетания и покрытия

Независимые множества и покрытия. Связь между ними. Паросочетания в двудольном графе: теоремы Холла и Кенига. Вывод теоремы Дилуорса из теоремы Кенига.