В этом видео мы обсудим двудольные графы. В некоторых задачах на графы вершины естественным образом разбиваются на две части. И при этом все ребра соединяют вершины одной части с вершинами другой части. Например, как это может возникать? Вершины — это пользователи и видеоролики, а ребра — посмотрел ли пользователь данный видеоролик. Естественно, вершины разбиваются на две части: пользователи и видеоролики, и ребра соединяют только одну часть с другой. Или вершины — это абитуриенты и университеты, и ребра — это поступил ли абитуриент в данный университет или нет. Такие графы называются двудольными. А если говорить формально, то граф двудольный, если его вершины можно разбить на два непересекающихся множества A и B так, что у каждого ребра один конец лежит в A, а другой конец лежит в B. И множества A и B при этом называются долями графа. Оказывается, в двудольных графах нет циклов нечетной длины. Почему это так? Пусть у нас A и B — это доли, и каждое ребро, давайте заметим, что оно ведет из A в B или наоборот. И если мы хотим цикл, если мы хотим вернуться в начальную вершину, нам придется сделать четное число шагов, потому что при каждом шаге у нас меняются доли, в которой мы находимся. Если мы хотим вернуться в изначальную, то придется сделать четное число шагов. Если мы начали с доли A, то нам придется вернуться к доле A. Таким образом, в двудольных графах нет циклов нечетной длины. Но оказывается, что верно и обратное, оказывается, что граф двудольный тогда и только тогда, когда в нем нет циклов нечетной длины. Таким образом, двудольные графы можно охарактеризовать через циклы. Мы уже доказали, что в двудольных графах нет циклов нечетной длины, и чтобы доказать теорему, нам осталось проверить, что всякий граф без циклов нечетной длины тоже является двудольным. Идея тут такая. Возьмем произвольную вершину v и покрасим ее в красный цвет, а дальше сделаем следующее: для всякой вершины u, если в нее из v ведет путь четной длины, то мы тоже покрасим ее в красный цвет, а если нечетной — то покрасим в синий. Давайте рассмотрим пример, давайте возьмем, начнем с вершины A, покрасили ее в красный цвет. Тогда все ее соседи, в них ведет путь из A нечетной длины, длины один, и мы можем покрасить их в синий цвет. Дальше есть оставшиеся вершины, и в них из A ведет путь длины два, давайте покрасим их в красный цвет. Продолжая таким образом, мы можем покрасить все вершины графа. Хорошо, почему это хорошая раскраска, почему она не приводит к противоречию? Давайте убедимся, что в этой раскраске красные вершины не могут быть соединены. Действительно, пусть у нас были соединены две красные вершины какие-нибудь, вот H и F, например. Но тогда из A в H есть путь четной длины, и из A в F тоже есть путь четной длины, и тогда два эти пути вместе с новым ребром образовали бы цикл нечетной длины, а мы договорились, что в нашем графе нет циклов нечетной длины, так что такого ребра быть не может. И аналогично для синих: если две синие вершины оказались соединены ребром, то у нас есть путь из A в B нечетной длины, есть путь из A в С нечетной длины, и вместе с новым ребром они образуют цикл нечетной длины. Это противоречие, потому что у нас нет циклов нечетной длины в графе, так что ни красные вершины между собой не могут быть соединены, ни синие вершины также не могут быть соединены между собой. Получается, что раскраска образует разбиение вершин на доли, соединены могут быть только вершины синие и красные. Получается, что теорема доказана? Не совсем так. Есть одна тонкость, то есть в целом почти все рассуждение закончилось, но есть одна тонкость. Заметим, что мы покрасили все вершины, в которые есть путь из вершины A. При этом мы не обязательно покрасили все вершины. Есть еще, может быть, вершины, в которые нет пути из A. На самом деле, что мы сделали? Мы разбили на доли только компоненту связности, в которой лежит A. Но легко понять, как это починить. Достаточно просто рассмотреть все остальные компоненты связности и в каждой из них отдельно провести разбиение на доли. Это даст разбиение на доли всего графа.
