Задание № 9 · ОГЭ

Двудольный граф

Как распознать граф, вершины которого разделяются на две доли

2 мин чтенияСложность: Обновлено 29 сентября 2026

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

Двудольный граф«Две доли» означают две группы вершин, на которые разделён граф.

Граф называется двудольным, если множество его вершин можно представить в виде объединения двух непересекающихся долей \(A\) и \(B\), причём каждое ребро имеет один конец в \(A\), а другой — в \(B\). Рёбра между двумя вершинами одной доли отсутствуют.

\[V=A\cup B,\qquad A\cap B=\varnothing,\qquad E\subseteq A\times B\]

Доли могут быть разного размера, а одна из них может быть пустой. Важно не то, сколько рёбер в графе, а возможность выполнить такое разделение. Один и тот же граф может иметь несколько подходящих разбиений.

№

Пример

Пусть \(A=\{1,3,5\}\), а \(B=\{2,4\}\). Рёбра соединяют только пары вида «вершина из \(A\) — вершина из \(B\)»: например, \(1-2\), \(1-4\), \(3-2\), \(5-4\). Тогда граф двудольный. Если добавить ребро \(1-3\), условие нарушится, потому что обе его вершины находятся в доле \(A\).

Не путайте с полным графом

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

Проверка

Является ли двудольным граф с рёбрами \(1-2\), \(2-3\), \(3-4\), \(4-1\)?

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

Главное за минуту

Главное

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