Основы теории графов: подсчет рёбер и степеней вершин. Илья Мещерин

• Проверка связи и видимости.  

• Объявление темы лекции: теория графов.  

• Теория графов редко обсуждается на олимпиадах, но полезна для понимания.  

• Теория графов часто связана с задачами о друзьях и знакомых.  

• Примеры задач: пары друзей, города и авиалинии.  

• Предупреждение: после лекции не научитесь решать задачи по теории графов.  

• Теория графов требует нестандартного подхода.  

• Нет стандартного метода решения задач.  

• Важно владеть терминологией и узнавать классические сюжеты.  

• Граф: набор точек, некоторые пары которых соединены.  

• Пример: пары знакомых или города и авиалинии.  

• Вершины и ребра: точки и отрезки соответственно.  

• Петли: вершины, соединенные с собой.  

• Кратные ребра: несколько ребер между одними и теми же вершинами.  

• Ориентированные графы: ребра с направлением.  

• Рассматриваются неориентированные графы без петель и кратных ребер.  

• Конечные графы и деревья.  

• Переход к простым задачам в этих терминах.  

• В любой компании количество людей с нечетным числом знакомых четно.  

• Это можно интерпретировать как количество людей, сделавших нечетное число рукопожатий.  

• Пример: в графе с 12 вершинами, у двух из них нечетное число соседей.  

• Подсчет количества знакомых и введение понятия степени вершины.  

• Сумма степеней всех вершин должна быть четной, что противоречит нечетному количеству вершин с нечетной степенью.  

• Это доказывает, что количество вершин с нечетной степенью четно.  

• В любой компании найдутся двое с одинаковым числом знакомых.  

• Компания может быть абстрактной, как граф, без ограничений на знакомства.  

• Пример: в графе с 12 вершинами всегда найдутся две вершины с одинаковой степенью.  

• Доказательство через принцип Дирихле.  

• Принцип Дирихле утверждает, что если есть n ящиков и n+1 шариков, то хотя бы два шарика попадут в один ящик.  

• Принцип Дирихле применим к различным задачам, включая распределение шариков по ящикам.  

• Принцип достоин отдельной лекции, так как имеет множество красивых приложений.  

• В компании из n человек у каждого может быть от 0 до n-1 знакомых.  

• Если у всех людей разное количество знакомых, то это противоречит принципу Дирихле.  

• Варианты распределения знакомых ограничены, что приводит к необходимости выбора одного из двух вариантов.  

• Лемма о рукопожатиях утверждает, что в графе с n вершинами и степенью каждой вершины 3 не может быть ровно 100 ребер.  

• Это аналогично принципу Дирихле, но использует делимость на 3.  

• Лемма о рукопожатиях не используется напрямую, но идея аналогична.  

• У Васи 28 одноклассников, и у любых двух из них разное число друзей.  

• Необходимо выяснить, сколько друзей у Васи.  

• Задача решается с использованием принципа Дирихле и идеи о том, что в компании не может быть у всех разное число знакомых.  

• Рассматриваются два случая: у одного одноклассника 28 друзей, у другого 0.  

• В любом случае, один одноклассник соединен с Васей, а другой нет.  

• Удаление одного из одноклассников приводит к противоречию, что подтверждает правильность решения.  

• Удаление первого человека уменьшило степени всех остальных на единицу.  

• Удаление последнего человека не изменило степени, так как он был знаком только с одним человеком.  

• Процесс повторяется до тех пор, пока не останутся только два человека.  

• Удаление каждого человека уменьшает максимальную степень на два.  

• В итоге Вася знаком с половиной людей, а другая половина не знакома с ним.  

• Процесс повторяется 14 раз, что приводит к тому, что Вася знаком с половиной людей.  

• В компании школьников у каждого мальчика и девочки есть по пять знакомых.  

• Нужно доказать, что количество школьников делится на четыре.  

• Используется лемма о рукопожатиях и двудольный граф.  

• Двудольный граф разбивает вершины на два множества, где ребра существуют только между этими множествами.  

• В задаче о школьниках ребра могут быть между мальчиками и девочками.  

• У каждого мальчика и девочки есть пять знакомых среди других мальчиков и девочек.  

• Количество мальчиков и девочек делится на два, так как у каждого есть пять знакомых.  

• Сумма четных чисел делится на четыре.  

• Мальчиков и девочек поровну, что подтверждает равенство их количества.  

• Сумма четных чисел делится на четыре, если они равны.  

• Решение задач требует интеллектуальных усилий и умения видеть факты.  

• Знание фактов помогает, но не решает задачу полностью.  

• Задачи могут быть сложными, простыми или бесполезными.  

• Для решения задач требуется интеллектуальная работа.  

• Пример задачи: каждый из 102 школьников знаком не менее чем с 68 другими.  

• Задача требует доказать, что найдутся четверо с одинаковым числом знакомых.  

• Используется принцип Дирихле.  

• Рассматриваются все возможные варианты числа знакомых у каждого человека.  

• Каждый человек может быть знаком с 68, 69, 70 и т.д. до 101.  

• Всего 34 варианта.  

• Если каждый вариант использован не более трех раз, то это приводит к противоречию.  

• Если каждый вариант использован не более трех раз, то каждый вариант использован ровно три раза.  

• Это приводит к нечетному числу людей с нечетным числом знакомых.  

• Лемма о рукопожатиях нарушается, что доказывает существование четверки с одинаковым числом знакомых.  

• Обсуждение использования принципа Дирихле и леммы о рукопожатиях.  

• Переход к следующей задаче о связности графа.  

• В стране есть столица и другие города.  

• Из столицы выходит 100 дорог, из остальных городов по 10 дорог.  

• Доказать, что можно закрыть 50 дорог из столицы, не нарушая связность графа.  

• Задача требует интеллектуального усилия.  

• На олимпиадах приличного уровня проверяющие знают базовые вещи, такие как лемма о рукопожатиях.  

• Теория графов не является базовой для школьной программы и ЕГЭ.  

• Она важна для олимпиадных задач и теории графов.  

• Рассматривается граф с столицей и другими городами.  

• Если убрать столицу, граф распадается на компоненты.  

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

• Если это так, можно удалить половину ребер, не нарушая связность.  

• Если компонента соединена со столицей одним ребром, в ней есть вершина степени девять.  

• Это противоречит лемме о рукопожатиях.  

• Теория графов полезна для практики, а не для теории.  

• Важно решать задачи, а не просто читать книги.  

• Рекомендуется использовать сайты с задачами для практики.