我只是在创建一个检测二部图的算法,但我想到了一些我不确定是否属于二部图的图,尽管我的算法说它是二部图。
该图如下所示
(A)--(B)
(C)因此,这里有3个节点,但只有A和B之间有1条边。这真的是二分的吗?
发布于 2013-04-06 03:44:33
是的,你的样例图确实是二分的。
例如,请看Wikipedia article,它在开场白中表示...
在图论的数学领域中,二部图(或二重图)是这样的图,其顶点可以被分成两个不相交的集合U和V,使得每条边都将U中的一个顶点连接到V中的一个顶点,即U和V都是独立的集合。等价地,二部图是不包含任何奇数长度圈的图。
有两种方法可以划分这个图("{A,C},{B}“或"{B,C},{A}"),它们将满足二部图所需的条件。
二部图不要求是连通图。
https://stackoverflow.com/questions/15725189
复制相似问题