Двудольные графы — Теория графов

Двудольный граф — это граф, вершины которого можно разбить на две части. При этом ребра будут проходить только между частями, но никогда внутри одной из них.

Так выглядят двудольные графы:

Вершины графа разбиты на две части — верхнюю и нижнюю. Пересечения возможны только между двумя частями, но не внутри них. При этом верхняя и нижняя части — независимые множества.

Обычно двудольные графы рисуют так, чтобы множество располагалось сверху, а множество — снизу. Несмотря на это, не все двудольные графы рисуются именно так. Например, ниже показаны двудольные сетки:

Чтобы определить двудольный граф, начните с любой вершины и пометьте ее буквой . Каждую из ее соседей пометьте буквой , а далее снова пометьте каждую из соседей буквой . Продолжайте помечать вершины и их соседей противоположными метками.

Если получится, что у двух соседних вершин одинаковые метки или какая-то вершина окажется помеченной и , и , значит, граф — не двудольный. Если это не произошло, граф — двудольный. Пример показан ниже:

Предположим, мы попробуем алгоритм на треугольнике . Начнем с того, что обозначим вершину . Затем две соседние вершины обозначим . Далее появляется проблема, так как эти вершины — смежные. Аналогичная проблема возникает и :

Такое происходит только с нечетными циклами, поэтому у двудольных графов их не бывает. Нечетные циклы — это единственное, чего не может быть у двудольных графов. Докажем это.

Если граф двудольный, то у любого цикла должна быть четная длина. Чтобы убедиться в этом, начнем с предположения, что два двусоставных множества называются и . Выберем любой цикл в графе и пометим вершины и .

Предположим, мы начинаем трассировку с вершины . Тогда вторая, четвертая, шестая и следующие четные вершины находятся в , а остальные — в . Когда мы вернемся в начальную вершину, пройдем четное количество шагов. Это значит, что у цикла четная длина:

Предположим, что у нас есть граф, в котором нет нечетных циклов. Выберем любую компоненту графа и любую вершину в ней. Пусть — все вершины компоненты на четном расстоянии от , а — все вершины компоненты на нечетном расстоянии от .

Мы утверждаем, что это образует двудольное разбиение компоненты. Для этого покажем, что нет ребер ни внутри , ни внутри .

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

Напомним, что расстояние между вершинами — это длина кратчайшего пути между ними. Рассмотрим кратчайшие пути из и из . Пусть — последняя общая вершина этих путей. Путь , за которым следует ребро , а затем путь образует цикл.

Его длина — это сумма слагаемых:

При этом сумма этих слагаемых будет четной. Внутри и внутри не может быть ни одного ребра. Таким образом, и образуют двудольное разбиение компонента. Мы можем проделать тот же процесс для каждой компоненты, чтобы получить двудольное разбиение всего графа.

Пример нечетного цикла, который создали во второй части доказательства:

Теперь нужно выбрать вершину и разбить граф на две группы:

Это основная идея доказательства. Во многих теоремах в теории графов есть одна большая идея, вокруг которой вращается доказательство.

У двудольных графов есть еще один класс — полные двудольные графы. У них есть возможные ребра между двумя частями. обозначает полный двудольный граф, одна часть которого состоит из вершин, а другая — вершин. Например:

Мы разобрали, что такое двудольные графы и как они выглядят. Теперь вы знаете, как провести доказательство того, что граф двудольный и какие его свойства указывают на это.