ДМ 2 курс - Теория графов - паросочетания, теорема Татта, формула Бержа

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

• Парсочетания в двудольных графах имеют хорошие алгоритмы на базе DFS.  

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

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

• На двух лекциях будет построена структурная декомпозиция Эдмонса-Галаи для произвольных графов.  

• Эта структура описывает все парсочетания в произвольном графе.  

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

• Вводятся понятия независимого множества и вершинного покрытия.  

• Независимое множество: множество вершин, где каждая пара вершин не связана ребром.  

• Вершинное покрытие: множество вершин, где у каждого ребра хотя бы один конец входит в это множество.  

• Альфа и бета связаны соотношением: альфа плюс бета равно количеству вершин.  

• Доказывается лемма, из которой следует теорема.  

• Вершинное покрытие и его дополнение образуют независимое множество.  

• Максимальное вершинное покрытие соответствует минимальному независимому множеству.  

• Сумма размеров вершинных покрытий и независимых множеств равна количеству вершин.  

• Независимое множество вершин - это множество, где никакие две вершины не соединены ребром.  

• Независимое множество на ребрах называется парасочетанием.  

• Парасочетание - это множество ребер, где никакие два ребра не имеют общих вершин.  

• Обозначения для реберных понятий аналогичны вершинным, но с штрихом.  

• Размер максимального парасочетания обозначается альфа-штрих.  

• Обобщение: вершинное покрытие на ребрах - это множество ребер, где каждая вершина покрыта хотя бы одним ребром.  

• Минимальное реберное покрытие обозначается бета-штрих.  

• Доказательство: максимальное парасочетание и минимальное реберное покрытие связаны.  

• Доказательство включает построение реберного покрытия из максимального парасочетания и добавление ребер для покрытия оставшихся вершин.  

• Минимальное реберное покрытие включает все ребра максимального парасочетания и дополнительные ребра для покрытия оставшихся вершин.  

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

• Теорема: альфа-штрих + бета-штрих = n.  

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

• Минимальное доминирующее множество минимизируется.  

• Клика - это множество вершин, где любые две вершины связаны ребром.  

• Размер максимальной клики обозначается омега.  

• Центром обсуждения является совершенное паросочетание.  

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

• Обсуждаются два свойства: четное число вершин и четное число связей.  

• Первое свойство верно: совершенное паросочетание имеет четное число вершин.  

• Вводится понятие чередующихся путей и циклов.  

• Чередующиеся пути и циклы имеют четное число ребер.  

• Существуют три вида чередующихся путей: заполняющие, сбалансированные и антидополняющие.  

• Заполняющие пути имеют на одно ребро больше, чем ребер из паросочетания.  

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

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

• Паросочетание М является максимальным, если не существует дополняющих путей.  

• Мощность паросочетания М равна альфа штриха дже.  

• Теорема верна для любых графов, а не только для двудольных.  

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

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

• Граф после симметрической разности состоит из чередующихся циклов и путей.  

• Степень каждой вершины не превышает двух, что позволяет разбить граф на циклы и пути.  

• Вершины, не покрытые ребрами, не могут быть покрыты другими ребрами.  

• Если существует дополняющий путь, то парасочетание не максимально.  

• Если дополняющего пути нет, то парасочетание максимально.  

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

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

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

• Это требует сложных манипуляций с графом.  

• В графе с четным числом вершин совершенное парасочетание может отсутствовать.  

• Удаление вершин может привести к нечетным компонентам, что исключает совершенное парасочетание.  

• Множество такта является сертификатом отсутствия совершенного парасочетания.  

• Если множество такта существует, то совершенного парасочетания нет.  

• Если множества такта нет, то совершенное парасочетание существует.  

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

• Предположим, что граф не содержит совершенного паросочетания и множества такта.  

• Рассмотрим граф с минимальным числом вершин и максимальным числом ребер.  

• Добавление ребра уменьшает количество нечетных компонент.  

• Объединение графов с ребром не содержит множества такта.  

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

• Добавление ребра не увеличивает количество нечетных компонент.  

• Граф с нечетным числом вершин не может быть полным.  

• Граф с четным числом вершин полный.  

• Граф без множества такта содержит полное паросочетание.  

• Лемма о графе, которого не существует, приводит к противоречию.  

• Граф без множества такта является объединением полных компонент.  

• Построение полного паросочетания в полном графе.  

• Доказательство леммы о свойствах несуществующего графа.  

• Граф без множества такта содержит полное паросочетание.  

• Построение полного паросочетания в полном графе.  

• Лемма касается графа, который является контрпримером к теореме Татта.  

• Граф имеет максимальное количество ребер среди всех контрпримеров.  

• Добавление любого ребра делает граф не контрпримером.  

• Добавление ребра y-z делает граф больше ребер, чем максимальный контрпример.  

• Появляется совершенное паросочетание.  

• Добавление ребра x-y-z также приводит к появлению совершенного паросочетания.  

• Рассматриваются два совершенных паросочетания: M1 и M2.  

• В графе нет путей, только циклы.  

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

• Ребра y-z и x-y-z лежат в разных компонентах.  

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

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

• Ребра y-z и x-y-z лежат в одной компоненте.  

• Построение паросочетания с использованием ребер из обоих паросочетаний.  

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

• Граф содержит полный граф.  

• Множество Татта указывает на отсутствие совершенного паросочетания.  

• Дефицит графа равен максимуму количества нечетных компонент минус мощность множества Татта.  

• Утверждается, что суммарная четность трех чисел равна нулю.  

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

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

• Мощность множества с равна м.  

• После удаления множества с остаются компоненты связности с вершинами к1, к2 и т.д.  

• Сумма мощностей компонент и множества с равна н.  

• Сумма мощностей компонентов и множества с имеет ту же четность, что и н.  

• Мощность с плюс-минус количество вершин без с имеет ту же четность, что и н.  

• Если максимум разности мощности множества с и количества вершин без с равен нулю, то граф совершенен.  

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

• Для графа с добавленными вершинами выполняется условие Татта.  

• В исходном графе существует парасочетание, покрывающее все вершины, кроме к.  

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

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

• Если дубль в содержит все добавленные вершины, то мощность множества с нечетная.  

• В графе с добавленными вершинами существует совершенное парасочетание.  

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

• Дефицит графа равен количеству добавленных вершин.  

• Обсуждение упрощения изложения и вопросов от зрителей.  

• Благодарность за просмотр и планы на создание единого ролика.