Двудольный граф и цикл четной длины

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

Можно ли также сказать, что если в графе G все циклы четной длины, то он двудольный?

Я придумал один граф цикла четной длины, и он оказался недвудольным.

     1----------2
     |          |
     |          |
     |          |
     |          |
     3----------4

graph bipartite
person Vini    schedule 14.06.2013    source источник
comment
Этот граф двудольный - U = (1, 4}, V = {2, 3}.   -  person lopek    schedule 14.06.2013

Ответы (1)


arrow_upward
3
arrow_downward

Если в графе G все циклы четной длины, то он двудольный.

Примените алгоритм BFS к графу G. Он делит вершины G на слои. Множество U состоит из вершин нечетных слоев, V — из вершин четных слоев. Предположим (от противного), что существует ребро e, соединяющее некоторые две вершины x, y из U. Пусть r — корень дерева определяется алгоритмом BFS. Затем путь от x до r, от r до y и край e являются циклами нечетной длины - противоречие, так как граф G не содержит циклов нечетной длины. (то же самое с множеством V).

person lopek    schedule 14.06.2013