Деревья и графы

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

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

Теорема Кёнига. Граф двудольный тогда и только тогда, когда в нем нет циклов нечетной длины.

Разберем задачу “Банкет”. В этой задаче требуется рассадить персон за два стола так, чтобы никакая пара людей, которые не ладят друг с другом, не сидели за одним столом. Заметим, что получающийся граф может не быть связным. В этом случае следует проверить двудольность всех его связных компонент.

Алгоритм проверки графа на двудольность

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

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