Двухсторонний график или нет

Question

Интересно, является ли этот график двудольным или нет. Как я обнаружил, B- C -J - цикл нечетной длины, однако, когда я рисую BFS, никакие ребра не соединяются со слоем samen. Спасибо

Answer 1

Это именно то, что вы сказали, BCJ делает цикл, поэтому он не может быть двудольным графом.

Есть и другие циклы, такие как EGAB C.

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