В этом видео мы обсудим примеры двудольных графов. Часто бывает, что двудольный граф задан так, что вершина заранее разбита на доли, но, на самом деле, не всегда это так. Вполне бывает такое, что граф двудольный, но изначально это совершенно неочевидно. Давайте рассмотрим пару примеров. Такой граф, как на картинке, называется двумерной решеткой. По сути, это очень похоже на клетчатую бумагу, вершины у нас на пересечении вертикалей и горизонталей, и ребрами мы соединяем соседние вершины по горизонтали или по вертикали. Тут нарисована картинка восемь на восемь, но такая решетка может быть любого размера. И оказывается, что вот этот граф на картинке — двудольный, и чтобы это легко заметить, достаточно сопоставить это с шахматной доской, неожиданным образом. Давайте нарисуем шахматную доску на этой картинке, и какое здесь сопоставление? По сути, вершины — это клетки шахматной доски, и мы соединяем ребрами те клетки, которые граничат по ребру, по стороне. Хорошо. Почему же это сопоставление удобно? Потому что шахматная доска уже раскрашена, и это раскраска задает разбиение на доли. Светлые поля соответствуют одной доле, а темные поля соответствуют другой доле. И видно, что ребра соединяют вершины разного цвета, поэтому это разбиение на доли, то есть наш граф изначально был двудольным. Хорошо, давайте рассмотрим еще один пример, и в качестве множества вершин мы рассмотрим множество всех последовательностей из нулей и единиц произвольной фиксированной длины n, и ребрами мы соединим те последовательности, которые отличаются только в одной координате, то есть все координаты у них одинаковые, но одна — разная. Вот пример для n, равного трем, и, например, мы соединяем ребром вершину "ноль ноль ноль" и вершину "ноль ноль один", или, например, мы соединяем вершину "один ноль один" и "один один один", они отличаются только во второй координате. Хорошо. Но у этого графа, на самом деле, есть естественный смысл — это единичный куб в n-мерном пространстве. Мы можем рассмотреть n-мерное пространство, можем рассмотреть там единичный куб, и тогда вершины этого куба — это вершины нашего графа, а ребра — это ребра нашего графа. И на картинке нарисован пример для трехмерного пространства — это просто трехмерный кубик, и вот это соответствует нашему графу. Ребрами мы соединяем вот ровно то, что должно быть ребром в нашем кубике, и это обобщается на n-мерный случай тоже. С другой стороны, этот же граф является часто встречающимся объектом в computer science, так что его полезно немножко проанализировать. И вот этот граф оказывается двудольным. Давайте объясним, как это увидеть. Достаточно просто описать, как устроены доли. В одну долю мы поместим те вершины, в которых четное число единиц в строке, а в другую — те, в которых нечетное число единиц. Вот мы на картинке покрасили вершины в два цвета. И легко заметить, что ребра соединяют только вершины из разных долей. Действительно, если у нас ребро соединяет две вершины, то эти вершины отличаются в одной координате, то есть в одной координате у одной вершины ноль, а у другой — единица, а все остальные координаты совпадают. И, таким образом, у нас четность числа единиц в этих вершинах — она разная, они отличаются одной единичкой, а все остальное совпадает, поэтому ребра могут соединять только вершины из разных долей. Хорошо. На этой неделе мы начали обсуждать графы, и обсудили, откуда они берутся, и обсудили какие-то базовые их свойства и параметры. На следующей неделе мы обсудим важный класс графов — деревья, а также мы обсудим ориентированные графы, а на последней неделе мы применим эти знания к анализу социальных сетей.