是否二分图

Question

我想知道这个图是否是二分图。正如我发现 B-C-J 是一个奇数长度的循环，但是当我绘制 BFS 时，没有边连接到 samen 层。谢谢

Answer 1

正是你说的，BCJ是循环所以不可能是二部图

还有其他循环，例如 EGABC。

在二分图中不能有奇数长度的循环，因为这意味着同一侧的 2 个顶点会相互连接。