5-часовой веб по ГРАФАМ

Бесплатная открытая неделя подготовки к к Перечневым олимпиадам: выполняй условия из поста https://vk.com/wall-215270197_1879 Материалы: https://1.shkolkovo.online/st/6/o/5-h... Курсы олимпиадной математики Перечень 10-11: https://shkolkovo.online/olymp-math/p... ВсОШ 8-9 класс: https://shkolkovo.online/olymp-math/v... ВсОШ 10-11 класс: https://2.shkolkovo.online/olymp-math... Кружок 4-7 класс: https://2.shkolkovo.online/olymp-math... Открытая неделя Перечня в апреле завершилась, но доступна в записи: https://vk.com/perechenolymp?w=wall-2... Открытая неделя курса ВсОШ в мае завершилась, но доступна в записи: https://vk.com/perechenolymp?w=wall-2... Телеграм Дмитрия Алексеевича👉🏻https://t.me/DA_shkolkovo Группа ВК по олимпиадной математике 👉🏻https://vk.com/perechenolymp Тайм-коды! 0:00 Что будет на этом вебе? Обязательно ли всем-всем сидеть 5 часов? 3:43 Графы. Вершины, рёбра, степень вершины 6:06 Задача 1. Граф государства. Вершины – города, рёбра – дороги. Подсчёт количества рёбер 8:09 Лемма о рукопожатиях. Общий случай подсчёта из предыдущей задачи 11:20 Задача 2. Рисуем графы-1. Граф шахматного коня. Цикл и изолированная вершина. Идея чередования цветов 21:10 Задача 3 [ОММО, 2020]. Рисуем графы-2. Кратные рёбра. Построение графа по степеням вершин и выкидывание готовых для удобного рисунка 32:35 Задача 4. Отрезки на плоскости и при чём тут графы. Вершины – отрезки, рёбра – пересечение отрезков. Противоречие с леммой о рукопожатиях 37:20 Задача 5. Граф из простых чисел с соответствующими степенями вершин. Единственное чётное простое 40:46 Задача 6. Связный граф. Удаление ребра и сохранение связности. Когда удобно решать от противного? 49:40 Задача 7. Полный граф. Раскраска полного графа. Идея посмотреть на все рёбра одного цвета 58:24 Задача 8. Мешочки со значениями степеней вершин, принцип Дирихле и спасающая лемма о рукопожатиях 1:06:44 Задача 9. Ищем конструкцию: полный граф на 4-ёх вершинах. Идея что-то начать набирать 1:17:19 Задача 10. Ищем конструкцию: цикл на 4-ёх вершинах. Произвольный Артём и проблемы с существованием Бориса 1:31:03 Задача 11 [Курчатов, 2017, 8 класс]. Двудольный граф и двойной подсчёт. Ищем конструкцию: два школьника, решившие всё. Вершина максимальной степени 1:43:50 Задача 12 [Высшая Проба, 2017, 9 класс]. Ориентированный граф. Двойной подсчёт стрелочек 1:50:24 Задача 13. Идея подсчёта треугольников: на каждом ребре 5 и посчитали всё 3 раза. Комба помогает доказать делимость! 1:59:17 Задача 14 [Ломоносов, 2016, 7–9 класс]. Отсутствие треугольников и 6 галочек на антиребре. Двойной подсчёт интересных нам конструкций с антиребром 2:21:18 Задача 15. Идея ранжирования графа – подвешиваем граф за вершину. Оценка количества вершин на каждом ранге и max вершин во всём графе 2:33:24 Задача 16. Удаление вершины в связном графе с сохранением связности. Удаляем вершину с последнего ранга! 2:38:57 Задача 17. Оценка количества вершин снизу на 2-ом ранге с помощью отсутствия каких-то циклов. Сложно догадаться до ранжирования! 2:45:40 Задача 18. Двудольный граф. Критерий двудольности об отсутствии нечётных циклов. Идея чередования долей и снова ранжирование 3:00:22 Задача 19 [Всеросс, 1993, округ, 11.8]. Минимальное количество рёбер в пути – намёк на ранжирование! Тройки рангов 3:16:16 Задача 20. Гуляем по графу-1. Граф, в котором степень каждой вершины = 2: вошли и вышли! 3:24:02 Задача 21. Гуляем по графу-2. Простой цикл. Из-за чего мы не можем продолжить путешествие? Самая ранняя вершина 3:36:34 Задача 23. Гуляем по графу-3. Существование чётного цикла. Работа с чётностью индексов в пути 3:46:40 Паросочетание. Определение. Перерывчик 4:00:01 Задача 24. Принцип крайнего: выбираем максимальное паросочетание. Работа с рёбрами от оставшихся вершин и общая оценка рёбер 4:05:56 Задача 25. Выделение паросочетания на всех вершинах. Вновь максимальное паросочетание. Две вершины не из паросочетания и количество рёбер из них 4:14:33 Задача 26 [Одна задача, чтобы стать призёром Турнира Городов-2009]. Максимальное паросочетание. Идём в вершину вне паросочетания, затем всегда ходить по рёбрам паросочетания 4:27:30 Задача 27 [Лемма Холла]. Критерий выделения паросочетания на всех вершинах одной доли двудольного графа. Неженатый парень, все девушки, с которыми он знаком, все их мужья и так далее – устраиваем переженитьбу! 4:52:36 Задача 28. Разбиение двух квадратов на равновеликие части, наложение и протыкание. Вершины – куски, рёбра – частичное наложение. Красивое применение леммы Холла! 5:03:25 Задача 30 [Самая сложная задача Всеросса–2006]. Размышления и анализ. Хотим покрасить, чтобы ВСЕ соседи были разных цветов. Что-то вроде ранжирования 5:20:17 Формальное решение. Убираем часть рёбер, чтобы степени остались от 20 до 70. Неожиданное появление леммы Холла! На кого влияет цвет пилотки пионера? Подсчёт запретов на цвет пионера. Фуууф!