Дискретный анализ 2. (n, r, s)-граф. Клики

00:00 Формулировка неравенств с прошлого раза 4:00 Cледствия из неравенств 14:00 Теорема о тождестве С из n по [an] 15:49 Формула стирлинга 19:17 Упражнение на асимптотику 21:18 Определение (n, r, s)-графа 27:18 Рассматриваем граф (n, n/2, n/4) 30:37 Определение регулярного графа 46:46 Определение клики в графе 52:04 Клики, независисмые множества и хроматические числа 58:29 Связь кликового числа и числа независимости 1:03:14 Равносильность тому, что в G нет нечётных циклов 1:04:27 Двудольный граф 1:07:15 Задача о 4 красках Дата лекции: Лектор: Райгородский Андрей Михайлович Оператор: Тарасова Ю. Монтажер: Андреев Я. Плейлист: