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

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

Описание

Целью курса является знакомство слушателей с основными понятиями и методами дискретной математики: основами математической логики, элементарной комбинаторикой и теорией графов.

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

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

Лекция 2

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

Лекция 3

Соотношения на биномиальные коэффициенты. Формула включений-исключений. Субфакториалы (задача о беспорядках). Формула обращения Мебиуса.

Лекция 4

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

Лекция 5

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

Лекция 6

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

Лекция 7

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

Лекция 8

Основы теории графов. Связность орграфов: различные виды связности, компоненты сильной связности, граф компонент. Диаметр и радиус графа. Дополнительный граф. Изоморфизм графов. Деревья и их свойства.

Лекция 9

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

Лекция 10

Паросочетания и покрытия. Независимые и доминирующие множества и связь между ними. Паросочетания в двудольном графе: теоремы Холла и Кенига. Максимальные покрытия. Теорема Галлаи. Чередующиеся цепи.

Лекция 12

Связность графов. Двусвязные графы. Дерево блоков и точек сочленения. Вершинная и реберная связность. Теорема Менгера. Структура минимальных k-связных графов: теорема Мадера о цикле и оценка количества вершин степени k. Редуцирование трехсвязных графов (теорема Татта о колесе).