graph-algorithm - 检测二分图

Question

我只是在创建一个算法来检测二分图，但我想到了一些我不确定是否算作二分图的图，尽管我的算法说它是。

图表就像

(A)--(B)

(C)

所以这有 3 个节点，但只有A和之间有 1 条边B。这真的是双向的吗？

Answer 1

是的，您的示例图确实是二分的。

参见，例如，在介绍性句子中陈述的维基百科文章......

在图论的数学领域中，二分图（或二分图）是一个图，其顶点可以分为两个不相交的集合 U 和 V，使得每条边都将 U 中的一个顶点连接到 V 中的一个顶点；也就是说，U 和 V 都是独立的集合。等效地，二分图是不包含任何奇数长度循环的图。

有两种方法可以划分此图（“{A,C}, {B}”或“{B,C}, {A}”），这将满足二分图所需的条件。

二分图不需要是连通图。