Кулешов А. Краткий конспект лекций по дискретной математике

СПб.: Санкт-Петербургский университет, 2019. — 193 с.Доказательства
Существование
Можно ведь просто предъявить объект?
А можно доказать, что объект существует, не предъявляя его?
Как доказать, что нужного объекта не существует?
Оптимальность
Универсальность
Обязательно ли начинать c самого начала?
Что такое полная индукция?
А можно по индукции доказать, что чего-то не существует?
Усилить утверждение, если не доказывается — разве это может помочь?
Что может быть не так с доказательством по индукции?
Перебор
Подмножества
Коды Грея: как перечислить все двоичные последовательности, каждый раз меняя один бит?
Перестановки
Скобочные последовательности
Оптимизация перебора
Перебор с возвратом: как заранее отсекать ненужные варианты?
Метод ветвей и границ: как оптимизировать перебор при решении оптимизационных задач?
Динамическое программирование: как передавать в рекурсивный вызов только то, что реально нужно?
Подсчёт
Размещения
Размещения с повторениями: сколько есть слов определённой длины?
Подмножества: сколько есть способов выбрать команду?
Размещения без повторений: сколько есть способов выстроить троих человек в очередь?
Сочетания
Подмножества из двух элементов: сколько игр в турнире?
Сочетания: сколько есть способов выбрать команду определённого размера?
Треугольник Паскаля: ещё один способ посчитать количество команд
Бином Ньютона: как быстро раскрыть скобки в (a+b)n?
Какой биномиальный коэффициент самый большой?
Перестановки с повторениями и полиномиальные коэффициенты: сколько есть способов раздать карты на четверых?
Сочетания с повторениями: сколько есть способов разделить монеты?
Резюме: размещения и сочетания
Рекуррентные соотношения
Разбиения
Числа Каталана
Первое доказательство: отражение
Второе доказательство: циклические сдвиги
Разные проявления чисел Каталана
Графы
Деревья
Почему деревья?
Алгоритмы Прима и Крускала: как максимально дёшево связать данные объекты?
Формула Кэли: сколько есть помеченных деревьев?
Динамическое программирование: при отрезании корня дерево разваливается на куски
Циклы
Графы зависимостей: когда граф можно упорядочить?
Компоненты сильной связности: сколько частей в ориентированном графе?
Эйлеровы графы: как проехать по всем дорогам города?
Гамильтоновы графы: как проехать по всем перекрёсткам города?
Задача коммивояжёра: как быстрее всего посетить все города?
Графы де Брюйна: как собирать геномы?
Потоки
Связность: что считать параметром надёжности коммуникационной сети?
Потоки: сколько товара можно перевозить с завода в магазин?
Разрезы: как убедить начальника, что больше товара перевезти не удастся?
Паросочетания
Двудольные графы: связи между двумя разными множествами
Устойчивое паросочетание: как переженить всех так, чтобы все браки были надёжны?
Числа Рамсея: среди восемнадцати человек всегда есть четверо знакомых или четверо незнакомых?
Раскраски
Почему раскраски?
Как быстро покрасить граф?
Если нужно много цветов, то обязательно есть большая клика?
Если нужно мало цветов, то степень маленькая?
Как много рёбер может быть в графе без больших клик?
Как быстро можно найти правильную раскраску?
Планарность
Почему планарные графы?
Формула Эйлера: как связаны числа вершин, рёбер и граней у многогранников?
Какие графы не являются планарными?
Если граф не является планарным, то с каким минимальным количеством пересечений рёбер его можно нарисовать?
Во сколько цветов можно раскрасить планарный граф?
Теоремы Куратовского и Вагнера: критерии планарности графа
Сколько источников света нужно для освещения всей комнаты?
Всегда ли у планарного графа есть укладка, в которой все рёбра являются отрезками?